Is it feasible to solve Dots and Boxes game?

Question

The game that I am trying to prove computability for is Dots and Boxes.

However, instead of using theorems I am trying to do so by creating an AI that is supposed to have 100% winrate in that game for either player 1 or player 2. If creating an 100% winrate AI is impossible, then my goal is to create one that's at least better than all the other AI's. As of right now I am writing everything in PHP because I am competing against another AI's that are written in scripting language as well.

This whole thing is recursive and the basic logic is: Compute the ENTIRE TREE of ALL possible moves If it is my AI's turn, then pick the route with maximum number of points for AI player. If it is opponent's AI's turn, then pick the route with minimum number of points for my AI. Aka compute number of guaranteed points at each node.

After computing the entire tree, pick the route with the highest number of guaranteed points. On Even points, pick randomly.

This whole computation process will take roughly forever to compute on 15x15 board, however for now all i am going for is computing it on 3x3 matrix. I will store best possible moves for first 6-8 moves in a database in order to now have to re-compute them again, this changing the complexity of each computation from 24! to 18!.

Is this whole thing doable? And Is there a problem with the way I compute my moves? Is there a better way to do this?

Answer 1

The problem has a very large search space, for a 4x4 grid, we have something like 40 edges and so 2^40 states in the search space. For this reason is completely impossible to solve the entire game for a larger map.

What are the solutions? First you can take a look to the work Solving Dots-And-Boxes of Barker and Korf. It is the state of the art for this kind of problem (in 2012 and maybe also now, I'm not sure). They used a combination of the classic Alpha-Beta pruning algorithm with a bunch of problem specific solutions.

You can also try to apply Monte Carlo Tree Search to the problem. I'm not aware of works in this directions but Monte Carlo has been proven successful for the Go game (that is similar to your problem in some sense).