Havannah
Rules
Havannah is a connection game invented by Christian Freeling in 1979. It is related to the game Hex, but the winning condition is different and the board is a hexagonal hexgrid.
The game starts on an empty board. Players move in turn to place one stone on an empty cell.
The game is won by the player who is able complete one of the following winning structures with his stones:
- a fork or
- a bridge or
- a ring,
which are defined as follows:
- A fork is a chain linking 3 sides (corners do not belong to sides).
- A bridge is a chain of stones linking 2 corners.
- A ring is a chain of stones around at least one cell (regardless of its being vacant or not).
A draw is theoretically possible, but very unlikely. Here is a drawn position on a base-6 board. It is an artificial position, meant to illustrate the possibility. Players can still move, but neither can win against intelligent counterplay.
The Pie Rule may be used to compensate for the first player advantage. Player one in that case makes the first move, while player two next decides to play with that move or against it.
Usual board sizes are 8 (faster games) and 10.
Playing Site 1: mindsports.nl
This is the official site. It supports only turnbased play, base-10.
http://www.mindsports.nl/index.php/arena/havannah/
- players section http://mindsports.nl/index.php/players-section/
- see sections for unfinished / finished games (spectators sections), and tutorials
Playing Site 2: littlegolem.net
Now the best place to play.
http://www.littlegolem.net littlegolem.net
Only turnbased play is possible. Board sizes 8 and 10 available.
Playing Site 3: iggamecenter.com
Now the best place to play live.
http://www.iggamecenter.com/ iggamecenter.com
Only live play is possible. Board sizes 4 to 10 available.
Playing Site 4: havannah.vying.org
http://havannah.vying.org/ havannah.vying.org
New, simple server for live playing, as java applet. Board sizes 4...10 supported. No registration is necessary (nor is it possible, yet). Finished games are available.
Playing Site 5: Ludoteka
http://www.ludoteka.com/jokolabur?joko=hava
Turnbased play base-8 and base-10, free registration.
Playing Site 6: itsyourturn.com
http://www.itsyourturn.com itsyourturn.com
Only turnbased play is possible. Board size is 8 here.
Forums
- http://www.littlegolem.net/jsp/forum/forum2.jsp?forum=50 LittleGolem Hex/Havannah forum: has some discussion about Havannah/Havannah programs
- http://www.grappa.univ-lille3.fr/icga/phpBB3/index.php ICGA computer games forum: has a Havannah subforum, but it seems to be inactive
Strategy
- The strategic goal is connecting three sides, the other "goals" of connecting 2 corners or making a ring often exist only as tactical threats.
- Some tactical structures appear similar to Hex (because it is also a connection game on a hexagonal board), but virtual connections play a much smaller role, and there are other elements, due to different rules.
- Strategic moves during the opening (whole board overview), and counting of moves+threats during the endgame.
- a "virtual" connection in the last phase of the game, in contrast to hex, is not automatically winning: the opponent could have a "faster" virtual connection. Thus the players might end up racing to complete their connections during the endgame (counting the remaining moves plus all threats for both players is necessary).
Similarities to other games
- Hex has some nice mathematical properties, compared to Havannah:
- Hex: In a certain board state, at most one player can have a winning (virtual) connection (the other player is disconnected); in Havannah both players could have virtual connections toward a winning structure, but only the faster one will win.
- Hex: When the board is completely filled exactly one player will have a connection; in Havannah a completely filled board will have usually more than one winning structures (but the game ends with first winning structure of course)
- Hex: no draw is possible; Havannah: draw is (theoretically) possible
Computer Opponents for Havannah
The Challenge
"The inventor has, in the summer 2002 issue of Abstract Games, put a $1000 prize money on a program that can beat him one out of ten games within the next decade."
In 2013, the computers won this challenge, though Freeling still won a majority of games, and there are several active players stronger than him.
http://www.littlegolem.net/jsp/forum/topic2.jsp?forum=1&topic=1944
- hav-ai1, written in Java (same author as HavannahGui, see download address there), still quite simple, only for demonstration of first moves (but does complete the game usually)
- fico ( http://bettong.net/articles/2005/04/10/fico-version-0-1-0) an Havannah Ai in Ruby (or rather a framework); only the ai part is currently missing :)
- castro a monte carlo bot that was one of the ones that won against Freeling.
Hex Definitions
Both Hex and Havannah have the concept of virtual connections (VCs): Two cells on the board, which can be considered connected for a certain player even if the opponent is allowed to move first locally. The (minimal) area of empty cells where such a fight takes place is called the "carrier" of the VC.
By formal definition, the VC consists of the 2 endpoints (can even be empty fields), and the "carrier" (set of empty fields on the board). The 2 endpoints are never included in the "carrier".
The smallest VC's are 2-VC's (where the carrier consists of only 2 empty cells).
Strategies for a Havannah playing program
Monte Carlo evaluation in Havannah/Hex?
Recent use of Monte Carlo methods/UCT in 9x9 Computer Go raises the question: can similar methods be applied to other games? (especially Hex and Havannah)
Monte Carlo Evaluation for Hex/Havannah would mean the board is filled with black and white stones until one player has a winning connection.
2 arguments, why it wouldn't work (without adaptions) for Hex/Havannah:
1) In a real game, before one player wins he usually has a "chain" of VC's, which he must then "only" connect to win.
If an MC-evaluation is done, the probability that the player who has such an (immediately winning) 2-VC actually gets to CONNECT it, is not 100% but only 75% - because the opponent may occupy both empty cells through the choice of the random move generator.
If the player has a chain of 2 or more 2-VC's which he must connect, the probability that the opponent can break at least one of them raises quickly (soon larger than 50%).
2) Another argument is (Havannah only), it is also not ensured, that the winning connection is made *FAST* enough, the opponent could make a connection elsewhere on the board, while player 1 makes useless random moves. In this case the initially "winning" player 1 has failed to materialize his win also.
It is thus not clear how random moves could help in the evaluation of Hex/Havannah positions.
hk: I don't think I agree. If you do a straightforward (no UCT) MC search in Hex until convergence, and play the best moves according to that, my hypothesis is that you'll get a player functionally identical to Shannon's Hex machine. And that wasn't at all bad - current top programs are based on the same concepts.
Another thing is that you can the all-moves-as-first heuristic - in Go it's a true heuristic, something that is usually true but not always. In games where pieces aren't moved or removed, however, it is a rock-solid principle.
For every N move win, there are N! other wins, just consisting of the same moves in a different order. When updating the winning percentages, you can act as if all these playouts were also made: add a win for all the winner's moves (as if they were first). MC playouts will converge much faster when you use this, and unlike in Go, in Hex and Havannah you know the heuristic is sound (it will converge to the same as if it had not been used).
For such games (no moving pieces, no removals) it's also much more feasible to take clever mathematical shortcuts, figuring out what random playouts would converge at without doing random playouts at all, like I believe Shannon's Hex machine is in effect doing.
Hyperpape: I believe MCTS is the current tack taken by top Havannah bots.
Virtual connections
Somehow it should be possible to extend virtual connections (like used in Hex programs), to be useful in Havannah:
- attach a number (depth) to each virtual connection, that says: how many turns does it take the owner of the VC to actually connect that virtual connection
- if there is a ring threat (or other threat) during the connection of a VC, which the opponent has to answer, for each such threat one move is subtracted from the "depth of the VC" - because the opponent loses a move too!
- then: if for both players the depth of their smallest VC is known, the winner is clear.
- additionally: it is necessary to allow VCs which not only have two endpoints, but three endpoints (because three sides need to be connected) - it could be handled with a 12-bit bitfield (6 corners, 6 sides) attached to each VC.
Havannah / Subgames
see that thread for an introduction: http://www.littlegolem.net/jsp/forum/topic2.jsp?forum=50&topic=365
Subgames are considered, which are completly independent (i.e. either in a separate part of the board, or they can even be on different boards).
A player can move in one of the subgames when it is his move; and a win of a subgame means the win of the whole game.
Calcuate for each subgame:
- n_w = the minumum number of white moves that are necessary for a white win in that subgame, white playing first, minus one for each time black has to defend locally
- if white cannot win in that subgame, when playing first, n_w=infinity
- e.g. white moves 100 times, black defends 99x, but white wins with his 100th move, it would be n_w=100-99=1
- n_b = "the minumum number of *black* moves that are necessary for a black win in that subgame, *black* playing first, minus ..." (same as above)
So, for n subgames, we have 2*n numbers.
Claim: "The player to move (white) wins, if the lowest of his numbers for the subgames is smaller than or equal all numbers for black moving first in one of the other subgames."
To win, white moves in the subgame with lowest n_w ("subgame 1"). Then, black can move in different places, as follows in (1)..(2b):
- (1) play in the *same* subgame (e.g. answer white threat, continue a own connection)
- (2) play in *another* subgame
- (2a) try a own connection there
- (2b) make a threat in another subgame (which white will answer)
what will happen:
- (1) playing in the same subgame as white will not work,
white will win, according to the definition of n_w; so, white will improve his position in that subgame, or at least keep it as good (Note 1), while the other subgames stay unchanged; and it is white's turn again (-> "GOTO :begin").
- (2) see 2a + 2b:
- (2a) black will simply be not fast enough; white just continues to play in subgame 1
- (2b) white will answer the black threat in the other subgame, however after
that white is still better off: he has made progress in subgame 1 (n_w--), while black just has played a threat and got an answer, which does not decrease the number n_b in the other subgame. Black now has one free move anywhere, but the best he can do is decrease n_b in some subgame, or play in subgame 1 (will also lose).
Note 1: It is important to note, that threats, which are correctly answered in the next move, do not decrease (or change) the number n for the player who plays the threat; the only difference is that the board fills up, and a threat is lost.
Note 2: Moves which do not include a threat (no need to answer for the opponent) "just" decrease the number n by one.
Note 3: No claim is made for a draw as the result of the game, only for "when white can win"
Note 4: draws in a subgames are handled by setting n=infinity (as defined above)
Note 5 (simplification): after deciding which one "subgame 1" is, we can already discard the other n_w's (white is only interested in subgame 1 from this point on); for black we need to keep the other n_b's, except for "subgame 1"
HavannahGui
- HavannahGui (hgui): a GUI for Havannah, based on GoGui, written in Java
- loading/saving/editing of havannah games (.sgf-files) possible, variations are also possible
- supports attaching up to two computer players (GTP protocol)
- Download: http://mgame99.funpic.de/havannah.php
- http://en.wikipedia.org/wiki/Havannah_(game) wikipedia article
- http://www.iwriteiam.nl/Havannah.html mathematical formalisation of the game
See also
Other Games Considered Unprogrammable
Connecting Techniques (in Go)
Connection Games
Lambda Search