is 4x4 Havannah solved?

By any chance is 4x4 Havannah solved?

I'm not aware that it is... but by gosh, one might suspect it should be by now.

There's only 37 cells and since pieces once played are never moved or captured, the branching tree gets smaller after each move. Also, I believe there are only 7 possible first moves. (All others are simply a mirror image.) And after that first move, depending upon what it is, there might be only about 21 unique replies, (or as few as 6) since all other replies are also just mirror images.

I just seems like this small version could be solved by now, by someone who is good at writing code to solve games like this.

I don't often play 4x4 at all. I've probably played less than 50 games in my whole life, and none very recently.

I ask all of this because I taught this 4x4 game to a friend of mine this past weekend. He caught on to it rather quickly. While playing some games with him, I realized I had forgotten how tactical this 4x4 version is! (Compared to 8x8 and 10x10, the two sizes I'm much more accustomed to.)

With each move, I felt as if I was stepping into a mine field... meaning each and every play might prove fatal... a losing move.

It also got me wondering if there existed an opening move database for Havannah 4x4, like there is for chess.

It also got me wondering how good the bots are at this version.

Finally, what's the percentage of 4x4 games that end in a draw? I know with 8x8 and 10x10 that percentage is VERY small... almost nonexistent. But I suspect with 4x4 it's not nearly as small and I was wondering what it was.

Thanks in advance for those who take the time to reply.

Brute force would be insufficient for "only 37" cells though: There are 37! ~ 10^43 possible situations. Taking symmetries into account I count possible situations after 1 put: 6 (not 7, 1 corner, 1 edge, the second edge being mirrored, 3 inner cells and 1 center), after 2 puts: 123, after 3 puts: 3937, after 4 puts 131069, after 5 puts: 4300401. That is better and still 32! ~ 10^35 is some order of magnitude too large... To solve it one either needs a clever program that prunes the tree by a lot and/or clever argumentation.

Saying that, I once solved Havannah-3 and made a perfect player. Download it here: https://github.com/mrahn/play.2

Actually it should only be 3^37, which is still too big, even taking into account the roughly 12-fold symmetry.

Say black moves first.Actually there are only 6 unique first moves. 4 are on a line from a corner to the center, one more is on the edge adjacent to a corner, and one is in the center of each of the six order 4 triangles. You can further reduce how many white responses there are by symmetry considerations if black played in one of the first 4 cells, but I ignore that for these calculations.

Each position with exactly 8 tokens (4 white, 4 black) is the same position regardless of the order in which the moves were made. So I can count the black tokens first.
B = (6*36*35*34)/6 = 42840
W = (33*32*31*30)/24 = 40920
B*W = 1753012800 which is actually larger than the true count.

IF you could somehow evaluate all these 8-token positions as win loss or draw, then build a database in RAM, you could work out all the positions with fewer tokens until you reach the blank board. This would give you a swap map and a solution to the game.

Of course I am glossing over the evaluation engine.

Sorry my text must have triggered some markup notation. But hopefully my message is still decipherable.

Did some counting in the game tree:

• There are 3878360 normal boards with 6 tokens placed. None of them can contain a winning position. "Normal" means it is a minimal board among the 12 symmetries.

• There are 30037713 undecided normal boards with 7 tokens placed and 2751 normal boards with 7 tokens that contain a winning position (a bridge).

• There are 225210572 undecided normal boards with 8 tokens placed and 20533 normal boards with 8 tokens that contain a winning position. (again, bridges)

So, David's estimation was pretty good and the "only" task remaining is to evaluate the ~225 million positions with 29 open fields...

Timo Ewalds, the author of Castro_bot, solved 4x4 Havannah back in 2012. See his master's thesis:
https://era.library.ualberta.ca/items/8d4dd716-0669-4258-8724-013d90dda80d