I need to solve 4x4 tic tac toe using alpha beta pruning, I have solved 3x3 tic tac toe using minimax, and it works very well, but in 4x4 minimax takes lot of time as search space is too big, so I am applying alpha beta pruning but I am not getting clear idea, that upto what depth I should go and what evaluation function should I write in order to give perfect game play, heuristic may also lead to false results and not perfect game play, so how do I ensure perfect game play for 4x4 using fast approach?? Any suggestions or approach will help me a lot. Looking forward to get some inputs.

  • 1
    The first thing is googling for the following keywords:
    perfect tic tac toe 4x4
    There are quite some hits also on SO. You read those and think about them.
  • 1
    I did that first, and on the basis of that have developed alpha beta pruning, but it is not fast, and too much time, I need some pointers here.
  • 1
    @punsa Alpha-beta works only well if you have a good move ordering, so that's a key feature.

    Usually, you iterate in the main depth loop with increasing depth, preserving the PV from the previous iteration. So you search with main depth 1, 2, 3, ... until time over.

    In PV nodes, the next PV move is the first candidate. In non-PV nodes, you can do internal iterative deepening with something like 1/3rd of the remaining search depth just to get the probably best move.

    Next would be hash tables so that you don't search the same position twice, or where you get at least the previously calculated best move in case your remaining depth is higher than the draft from the hash table hit.

    Perfect fast play requires a completely different approach - retrograde analysis of all legal end positions, and then backing up to previous moves. That gives you a table base for lookup. In chess, this is known as "endgame tables".
  • 0
    @punsa For basic move sorting, piece square tables could be helpful. Centre is better than rim, long diagonal squares are better than others.

    Since the game doesn't have zugzwang problems, nullmove reduction would be easy to add in. If a nullmove threat is found (that is, unless all response moves fail low), that can be used for move sorting.

    Search extension when threatening to complete a line of 4 would also make sense because that's a threat that the opponent must react to.
Add Comment