Threading within Minimax algorithm

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 /* */ are new threads, but a problem arises: even with depth = 1, that's 8 threads. For depth = 8, that's 16534863 threads. What are the limitation on threads? Is it linked to how many physical cores my CPU has?

Answer 1

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.