I'm designing a 3D Tic-Tac-Toe game and finding time to be a limit in how deep my Minimax algorithm can go. While depths up to 6 are largely inconsequential time wise (<1s), for higher depths it does take time.
>Depth 7 = 6 seconds
>Depth 8 = 49 seconds
>Depth 9 = 314 seconds
//player is -1 for human, +1 for AI
function minimax(board_state, depth, player)
if depth <= 0 or board == full //full board means no further states
return score * player
bestScore = -1000;
foreach possible move
if valid move
bestScore = max(bestScore, minimax(board_state, depth-1, -player)
depth = 1
depth = 8
First consider how much you can speed up on a 8-core system ... that is 8 times (unless your problem is memory bound in which case you can get a little better). Read on Amdahl's law and Gustafson's law
Your problem looks like its a !N problem, it explodes in time. You need to consider changing your code to significantly cull the amount of options.
You already seem to be going the game theory way with your minmax algorithm.
As soon as you in one depth of the tree have found a winning move for the opposite player, you don't need to test the rest possible move and can return the winner for that partial tree.