How to efficiently detect a tie early in m,n,k-game (generalized tic-tac-toe)?

Question

I'm implementing an m,n,k-game, a generalized version of tic-tac-toe, where m is the number of rows, n is the number of columns and k is the number of pieces that a player needs to put in a row to win. I have implemented a check for a win, but I haven't figured out a satisfactory way to check before the board is full of pieces, if no player can win the game. In other words, there might be empty slots on the board, but they cannot be filled in such a way that one player would win.

My question is, how to check this efficiently? The following algorithm is the best that I can think of. It checks for two conditions:

A. Go over all board positions in all 4 directions (top to bottom, right to left, and both diagonal directions). If say k = 5, and 4 (= k-1) consecutive empty slots are found, stop checking and report "no tie". This doesn't take into account for example the following situation:

OX----XO    (Example 1)

where a) there are 4 empty consecutive slots (-) somewhere between two X's, b) next it is O's turn, c) there are less than four other empty positions on the board and no player can win by putting pieces to those, and d) it is not possible to win in any other direction than horizontally in the shown slots either. Now we know that it is a tie because O will eventually block the last winning possibility, but erroneously it is not reported yet because there are four consecutive empty slots. That would be ok (but not great). Checking this condition gives a good speed-up at the beginning when the checking algorithm usually finds such a case early, but it gets slower as more pieces are put on the board.

B. If this k-1-consecutive-empty-slots-condition isn't met, the algorithm would check the slots again consecutively in all 4 directions. Suppose we are currently checking from left to right. If at some point an X is encountered and it was preceded by an O or - (empty slot) or a board border, then start counting the number of consecutive X's and empty slots, counting in this first encountered X. If one can count to 5, then one knows it is possible for X to win, and "no tie" is reported. If an O preceded by an X is encountered before 5 consecutive X's, then X cannot win in those 5 slots from left to right starting from where we started counting. For example:

X-XXO    (Example 2)
12345

Here we started checking at position 1, counted to 4, and encountered an O. In this case, one would continue from the encountered O in the same way, trying to find 5 consecutive O's or empty slots this time. In another case when counting X's or empty slots, an O preceded by one or more empty slots is encountered, before counting to 5. For example:

X-X-O    (Example 3)
12345

In this case we would again continue from the O at position 5, but add to the new counter (of consecutive O's or empty slots) the number of consecutive empty slots that preceded O, here 1, so that we wouldn't miss for example this possible winning position:

X-X-O---X    (Example 4)

In this way, in the worst case, one would have to go through all positions 4 times (4 directions, and of course diagonals whose length is less than k can be skipped), giving running time O(mn).

The best way I could think of was doing these two described checks, A and B, in one pass. If the checking algorithm gets through all positions in all directions without reporting "no tie", it reports a tie.

Knowing that you can check a win just by checking in the vicinity of the last piece that was added with running time O(k), I was wondering if there were quicker ways to do an early check for a tie. Doesn't have to be asymptotically quicker. I'm currently keeping the pieces in a two-dimensional array. Is there maybe a data structure that would allow an efficient check? One approach: what is the highest threshold of moves that one can wait the players to make before running any checks for a tie at all?

There are many related questions at Stack Overflow, for example this, but all discussions I could find either only pointed out the obvious tie condition, where the number of moves made is equal to the size of the board (or they checked if the board is full), or handled only the special case where the board is square: m = n. For example this answer claims to do the check for a tie in constant time, but only works when m = n = k. I'm interested in reporting the tie as early as possible and for general m,n and k. Also if the algorithm works for more than two players, that would be neat.

Answer 1

Actually the constant time solution you referenced only works when k = m = n as well. If k is smaller then I don't see any way to adapt the solution to get constant time, basically because there are multiple locations on each row/column/diagonal where a winning consecutive k 0's or 1's may occur.

However, maintaining auxiliary information for each row/column/diagonal can give a speed up. For each row/column/diagonal, you can store the start and end locations for consecutive occurrences of 1's and blanks as possible winning positions for player 1, and similarly store start and end locations of consecutive occurrences of 0's and blanks as possible winning positions for player 0. Note that for a given row/column/diagonal, intervals for player 0 and 1 may overlap if they contain blanks. For each row/column/diagonal, store the intervals for player 1 in sorted order in a self-balancing binary tree (Note you can do this because the intervals are disjoint). Similarly store the intervals for player 0 sorted in a tree. When a player makes a move, find the row/column/diagonals that contain the move location and update the intervals containing the move in the appropriate row column and diagonal trees for the player that did not make the move. For the player that did not make a move, this will split an interval (if it exists) into smaller intervals that you can replace the old interval with and then rebalance the tree. If an interval ever gets to length less than k you can delete it. If a tree ever becomes empty then it is impossible for that player to win in that row/column/diagonal. You can maintain a counter of how many rows/columns/diagonals are impossible to win for each player, and if the counter ever reaches the total number of rows/columns/diagonals for both players then you know you have a tie. The total running time for this is O(log(n/k) + log(m/k)) to check for a tie per move, with O(mn/k) extra space.

You can similarly maintain trees that store consecutive intervals of 1's (without spaces) and update the trees in O(log n + log m) time when a move is made, basically searching for the positions before and after the move in your tree and updating the interval(s) found and merging two intervals if two intervals (before and after) are found. Then you report a win if an interval is ever created/updated and obtains length greater than or equal to k. Similarly for player 0. Total time to check for a win is O(log n + log m) which may be better than O(k) depending on how large k is. Extra space is O(mn).

Answer 2

I would reduce the problem of determining a tie to the easier sub-problem:
Can player X still win?

If the answer is 'no' for all players, it is a tie.

To find out whether Player X can win:

• fill all blank spaces with virtual 'X'-pieces
• are there k 'X'-pieces in a row anywhere?
  • if there are not --> Player X cannot win. return false.
  • if there are, find the row of k stones with the least amount of virtual pieces. Count the number of virtual pieces in it.
  • count the number of moves player X has left, alternating with all other players, until the board is completely full.
  • if the number of moves is less than the amount of virtual pieces required to win, player X cannot win. return false.
  • otherwise, player X can still win. return true.

(This algorithm will report a possible win for player X even in cases where the only winning moves for X would have another player win first, but that is ok, since that would not be a tie either)

If, as you said, you can check a win just by checking in the vicinity of the last piece that was added with running time O(k), then I think you can run the above algorithm in O(k * Number_of_empty_spots): Add all virtual X-Piece, note any winning combinations in the vicinity of the added pieces.

The number of empty slots can be large, but as long as there is at least one empty row of size k and player X has still k moves left until the board is filled, you can be sure that player X can still win, so you do not need to run the full check.

This should work with any number of players.

Answer 3

Let's look at one row (or column or diagonal, it doesn't matter) and count the number of winning lines of length k ("k-line") it's possible to make, at each place in the row, for player X. This solution will keep track of that number over the course of the game, checking fulfillment of the winning condition on each move as well as detecting a tie.

1 2 3... k k k k... 3 2 1

There is one k-line including an X in the leftmost slot, two with the second slot from the left, and so on. If an opposing player, O or otherwise, plays in this row, we can reduce the k-line possibility counts for player X in O(k) time at the time of the move. (The logic for this step should be straightforward after doing an example, needing no other data structure, but any method involving checking each of the k rows of k from will do. Going left to right, only k operations on the counts is needed.) An enemy piece should set the possibility count to -1.

Then, a detectably tied game is one where no cell has a non-zero k-line possibility count for any player. It's easy to check this by keeping track of the index of the first non-zero cell. Maintaining the structure amounts to O(k*players) work on each move. The number of empty slots is less than those filled, for positions that might be tied, so the other answers are good for checking a position in isolation. However, at least for reasonably small numbers of players, this problem is intimately linked with checking the winning condition in the first place, which at minimum you must do, O(k), on every move. Depending on your game engine there may be a better structure that is rich enough to find good moves as well as detect ties. But the possibility counting structure has the nice property that you can check for a win whilst updating it.

Answer 4

If space isn't an issue, I had this idea:

For each player maintain a structure sized (2mn + (1 - k)(m + n) + 2(m - k + 1)(n - k + 1) + 2(sum 1 to (m - k))) where each value represents if one of another player's moves are in one distinct k-sized interval. For example for a 8-8-4 game, one element in the structure could represent row 1, cell 0 to 3; another row 1, cell 1 to 4; etc.

In addition, one variable per player will represent how many elements in their structure are still unset. Only one move is required to set an element, showing that that k-interval can no longer be used to win.

An update of between O(k) and O(4k) time per player seems needed per move. A tie is detected when the number of players exceeds the number of different elements unset.

Using bitsets, the number of bytes needed for each player's structure would be the structure size divided by 8. Notice that when k=m=n, the structure size is 4*k and update time O(4). Less than half a megabyte per player would be needed for a 1000,1000,5 game.

Below is a JavaScript example.

var m = 1000, n = 1000, k = 5, numberOfPlayers = 2

  , numberOfHorizontalKIs = m * Math.max(n - k + 1,0)
  , numberOfverticalKIs = n * Math.max(m - k + 1,0)
  , horizontalVerticalKIArraySize = Math.ceil((numberOfHorizontalKIs + numberOfverticalKIs)/31)                  
  , horizontalAndVerticalKIs = Array(horizontalVerticalKIArraySize)
  , numberOfUnsetKIs = horizontalAndVerticalKIs
  , upToM = Math.max(0,m - k) // southwest diagonals up to position m
  , upToMSum = upToM * (upToM + 1) / 2
  , numberOfSouthwestKIs = 2 * upToMSum //sum is multiplied by 2 to account for bottom-right-corner diagonals
                         + Math.max(0,n - m + 1) * (m - k + 1)
  , diagonalKIArraySize = Math.ceil(2 * numberOfSouthwestKIs/31)                  
  , diagonalKIs = Array(diagonalKIArraySize)
  , numberOfUnsetKIs = 2 * numberOfSouthwestKIs + numberOfHorizontalKIs + numberOfverticalKIs

function checkTie(move){
    var row = move[0], column = move[1]

    //horizontal and vertical
    for (var rotate=0; rotate<2; rotate++){
        var offset = Math.max(k - n + column, 0)

        column -= offset

        var index = rotate * numberOfHorizontalKIs + (n - k + 1) * row + column
          , count = 0
        while (column >= 0 && count < k - offset){
            var KIArrayIndex = Math.floor(index / 31)
              , bitToSet = 1 << index % 31

            if (!(horizontalAndVerticalKIs[KIArrayIndex] & bitToSet)){
                horizontalAndVerticalKIs[KIArrayIndex] |= bitToSet
                numberOfUnsetKIs--
            }
            index--
            column--
            count++
        }

        //rotate board to log vertical KIs
        var mTmp = m
        m = n
        n = mTmp
        row = move[1]
        column = move[0]
        count = 0
    }

    //rotate board back
    mTmp = m
    m = n
    n = mTmp

    // diagonals
    for (var rotate=0; rotate<2; rotate++){
        var diagonalTopColumn = column + row

        if (diagonalTopColumn < k - 1 || diagonalTopColumn >= n + m - k){
           continue
        } else {
            var offset = Math.max(k - m + row, 0)

            row -= offset
            column += offset

            var dBeforeM = Math.min (diagonalTopColumn - k + 1,m - k)
              , dAfterM = n + m - k - diagonalTopColumn
              , index = dBeforeM * (dBeforeM + 1) / 2
                      + (m - k + 1) * Math.max (Math.min(diagonalTopColumn,n) - m + 1,0)
                      + (diagonalTopColumn < n ? 0 : upToMSum - dAfterM * (dAfterM + 1) / 2)
                      + (diagonalTopColumn < n ? row : n - 1 - column)
                      + rotate * numberOfSouthwestKIs
              , count = 0

            while (row >= 0 && column < n && count < k - offset){
                var KIArrayIndex = Math.floor(index / 31)
                  , bitToSet = 1 << index % 31

                if (!(diagonalKIs[KIArrayIndex] & bitToSet)){
                    diagonalKIs[KIArrayIndex] |= bitToSet
                    numberOfUnsetKIs--
                }
                index--
                row--
                column++
                count++
            }
        }
        //mirror board
        column = n - 1 - column
    }

    if (numberOfUnsetKIs < 1){
        return "This player cannot win."
    } else {
        return "No tie."
    }
}