Minimax / Alpha Beta Algorithm - Finding the AI's move in Gomoku

Question

I understand that a Minimax decision tree is a good approach to implementing an AI for a board game. Currently, I am trying to implement a game called Gomoku (5 in a row). But there is one thing that I am confused about:

I've looked around and it seems that almost all Minimax/AlphaBeta algorithms return an integer. Specifically for me, the return value of eval(bestGomokuBoard). How am I supposed to find the coordinate of the winning board?

Here is what I have done so far: I have a 20x20 Array of integers, representing an empty space(0), computer(1), and player(2). To reduce overhead, each node in the Minimax Tree is a 9x9 array representation of the larger array (a smaller frame of reference). My eval function returns an int, my minimax/alphabeta algorithm returns an int. How do I find the coordinates of the AI's move?

And thank you in advance!

Answer 1

You can make two slightly different max-functions. One which returns only an integer (the score), and another max-function (e.g. maxWithBestMove or rootMax), which returns the score and the best move. The recursive call order would than be:

maxWithBestMove --> min --> max --> min --> max....

Have a look at Note #2 in the Negamax Framework on the chessprogramming wiki. A similar answer I gave here.