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?