gator - 11 months ago 64

C++ Question

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

I haven't the time (hah!) to check higher depths. The maximal depth is 22 which would let my AI analyze every possible game state from Move 1 and never result in a user win.

I want to implement threading in my Minimax function but am relatively new to threading. My Minimax function is like below:

`//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

/* */

make_move()

bestScore = max(bestScore, minimax(board_state, depth-1, -player)

undo_move()

/* */

return bestScore

I'd like something where the bits between

`/* */`

`depth = 1`

`depth = 8`

Answer Source

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.