How to validate a connect X game (Tick-Tak-Toe,Gomoku,…)?

Question

Currently I am working on a Gomoku AI (or generally Connect-X games).

Implementing the search tree was no problem, but then I got to the point where I had to implement the value function and was surprised how difficult this is to make with a decent performance.

My question is what is the most efficient algorithm to check for a win in a connect-x game.

So basically I tried 2 things:

Firstly I created an Array where I saved all board coordinates (at compile time) into a 1D Array. This means all rows,cols and diagonals point for point and traversing this array and checking the corresponding on the actual board until (if any) a X long sequence was found.

My second approach was to calculate all patterns (horizontal,vertical,diagonal) with X points each at compile time (with Template-Meta-Programming) and traversing only those for each point played on so far and terminating if any member of the sequence was missing.

The first approach was way too slow and the second one was too complex for this problem I think.

What algorithm suites this problem best?

Answer 1

One approach that may be useful is to represent your field by a matrix and use a matrix vector product to test whether there is a winning position. Suppose we are playing connect $3$ and are testing whether player $A$ wins by a horizontal row, in this field:

A A A _ B
B _ _ B _
B B _ B A
A A _ A A

Construct a matrix $M$ by representing player $A$'s pieces by $1$, player $B$'s pieces and empty fields by $0$:

$M = \begin{pmatrix} 1 &1&1&0&0\\ 0 &0&0&0&0\\ 0 &0&0&0&1\\ 1 &1&0&1&1\\ \end{pmatrix}$

Now, multiply the matrix by the vector $v=(1,2,4,8,16)^T$:

$Mv = (7,0,16,27)^T$. As we are looking for adjacent $1$'s, we see that there is a value in $Mv$ equal to $7$ ($=1+2+4$), $14$ ($=2+4+8$), $28$ ($=4+8+16$), $15$ (=$1+2+4+8$), $30$ ($=2+4+8+16$) or $31$ ($=1+2+4+8+16$).

Since the first entry of $Mv$ is equal to $7$, we know there is a row of three $1$'s there.

In general, for a $k\times n$ size grid, we take the vector $v=(1, 2,4,\ldots , 2^i,\ldots, 2^n)^T$ and know that there is a connected line of length at least $x$ when any of the values $\{\sum_{i=j}^{j+y} 2^i \mid 0\leq j \leq n-y, x\leq y< 2x\}$ are present in the vector $Mv$. (we can take $y<2x$ as when $y\geq 2x+1$, there must have been a row of length $x$ already on the field)

To test for columns, we can simply take the transpose of the matrix.

To test for diagonals, rotate the field such that they become rows and add padding to construct a rectangle: e.g. given our playing field above, a rotation for a diagonal would be:

_ B _ _
_ _ _ _
A B A _
A _ B A 
A _ _ A 
_ B B _ 
_ B A _
_ A _ _

(Note that it doesn't matter whether we place the padding to the left or the right, as we only check rows)