Calculating slot machine payout

Question

A slot machine has 5 reels and displays 3 symbols per reel (no spaces or "empty" symbols).

Payout can occur in a number of ways. Some examples...

• A special diamond symbol appears
• 3 Lucky 7's appear
• All five symbols in the payline are identical
• All five symbols are the same number, but different color
• Etc.

There are also multiple paylines that need to be checked for a payout.

What is the most efficient way to calculate winnings for each spin? Or, is there a more efficient way than brute force to apply each payout scenario to each payline?

Answer 1

Every payout besides the paylines seem trivial. For the three lucky 7s, just iterate over the visible squares and count the 7s. Same for checking for a diamond. If we let h be the number of rows and w be the number of columns, this operation is O(hw*), which for practically sized slot machines is pretty low.

The paylines, though, are more interesting. Theoretically the number of paylines (m from here on out) is much, much larger than *h ** w*; before throwing out illegal paylines that jump m = h^w which is much larger than *h ** w. More importantly, they appear to share a lot of similarity. For example, line 2 and line 6 in your example both require matching top left and top middle-left squares. If these two don't match, then you can't win on either line 2 or line 6.

To represent paylines, I'm going to use length w arrays of integers in the range [1, h], such that payline[i] = the index in the column (1 indexed) of row i in the solution. For example, payline 1 is [1, 1, 1, 1, 1], and payline 17 is [3, 3, 2, 1, 2].

To this end, a suffix tree seems like an applicable data structure that can vastly improve your running time of checking all of the paylines against a given board state. Consider the following algorithm to construct a suffix tree that encapsulates all paylines.

Initialize: 
    Create a root node at column 0 (off-screen, non-column part of all solutions)
    root node.length = 0
    root node.terminal = false
    Add all paylines (in the form of length w arrays of integers ranging from 1 to h) to the root nodes' "toDistribute set"
    Create a toWork queue, add the root node to it

Iterate: while toWork not empty:
    let node n = toWork.pop()
    if n.length < w
        create children of n with length n.length + 1 and terminal = (n.length + 1 == w).
    for payline p in n.toDistribute
        remove p from n.toDistribute
        if(p.length > 1)
            add p.subArray(1, end) to child of n as applicable.
    add children of n to toWork

Running this construction algorithm on your example for lines 1-11 gives a tree that looks like this:

The computation of this tree is fairly intensive; it involves the creation of sum i = 1 to w of h ^ i nodes. The size of the tree depends only on the size of the board (height and width), not the number of paylines, which is the main advantage of this approach. Another advantage is that it's all pre-processing; you can have this tree built long before a player ever sits down to pull the lever.

Once the tree is built, you can give each node a field for each match criteria (same symbol, same color, etc). Then, when evaluating a board state, you can dfs the tree, and at every new node, ask (for each critera) if it matches its parent node. If so, mark that criteria as true and continue. Else, mark it as false and do not search the children for that criteria. For example, if you're looking specifically for identical tokens on the sub array [1, 1, ...] and find that column 1's row 1 and column 2's row 1 don't match, then any payline that includes [1, 1, ...] (2, 6, 16, 20) all can't be won, and you don't have to dfs that part of the tree.

It's hard to have a thorough algorithmic analysis of how much more efficient this dfs approach is than individually checking each payline, because such an analysis would require knowing how much left-side overlap (on average) there is between paylines. It's certainly no worse, and at least for your example is a good deal better. Moreover, the more paylines you add to a board, the greater the overlap, and the greater the time savings for checking all paylines by using this method.