How to solve a game with repeating positions (Teeko)

Question

I have been trying to find a algorithm to strongly solve the game Teeko. The game is played on a 5x5 board were each player has 4 pieces and attempts align them in any direction or create a square out of them. (assume there is no drop phase)

I have tried solving the game by using a negamax with alpha beta pruning and other optimizations like a transposition table but that has not seemed to have worked because the solver would usually get stuck in loops were neither player wants to deviate from there strategy as it would result in them loosing. From my research I have found stuff like Nash Equilibrium as a potential solution but I cant figure out how to implement it. Furthermore, I have found that the game has been solved and found that the with prefect play it result in a draw previously: https://pcarrier.com/teeko/text/teeko.results.txt

Are there any algorithms that might be able to give the same result as minimax and hanlde repeating positions and how could I implement it and are there any other algorithms that give the same result as minimax?

Answer 1

Minimax (or Negamax) is well capable of handling repeating positions using transposition tables, as you mention in your question. Transposition tables are complicated to implement though so maybe you have a bug?

The problem with minimax is that you either:

1. NEed to solve it until the game is completed to get a score. This is possible for simple games like tic-tac-toe, but not for more complicated games like chess.

2. Score each node using some heuristic function, which is the case for e.g. chess.

I am not sure about Teeko, is it possible to get to all leaf nodes with minimax and alpha beta pruning? Could you do other things to reduce the search tree, like transpotision tables or other cut offs? If so then minimax is a great option.

Is it possible to create some kind of evaluation function for this game? It seems hard to me, but maybe that is because I know too little about the game. Is it better to have central squares? Better to get 2 in a row than to spread out pieces? Evaluation function is something you could have a look at if you are a good player of the game, or find good sources online.