In the traditional deterministic approach to programming abstract games the question would be "what exactly do humans do when they play this game?" One thing seemed certain: they think. And that's still a human prerogative. But it's no longer enough to beat AI at Havannah.
The Zillions game machine, a program that can play hundreds of games, is very apt at chess variants and elimination games, but predictably it plays Havannah like a moron. This is no fault of this magnificent program and a specific deterministic havannah program might still do not much better.
Ironically it is the absence of a lot of things that makes Havannah so easy to understand for humans and so hard for computers:
- no material imbalance
- no movement
- no general direction
- no capture
- no promotion
Goals are very easy to understand, but very hard to implement in a program. Threats to win in two or three moves could be noticed, but many are irrelevant in a strategic sense and Havannah is decided on a strategic level.
But programs using the Monte Carlo method have made significant progress on smaller boards, and are creeping upwards fast.
Havannah is a pencil and paper game: it can be played with two distinct markers and a pen for move numbers. Completed games are implicitly their own notation. In the summer 2002 I put €1000.- prize money on a program that could beat me one out of ten games on a base-10 board within the next decade. In 2012 I won 7-3 so I lost the challenge. Given recent developments, no abstract strategy game seems safe from being overtaken by AI.
- From the 24th of September till the 2nd of October 2010 the 15th Computer Olympiad took place in the city of Kanazawa in Japan. There were five enties for Havannah and 'Castro', by the then 18yo programming prodigy Timo Ewalds has won. Runner-up was 'Wanderer' by Richard Lorenz.
Havannah © MindSports