Havannah (board Game)
   HOME

TheInfoList



OR:

Havannah is a two-player
abstract strategy Abstract may refer to: *"Abstract", a 2017 episode of the animated television series ''Adventure Time'' * ''Abstract'' (album), 1962 album by Joe Harriott * Abstract algebra, sets with specific operations acting on their elements * Abstract of ti ...
board game A board game is a type of tabletop game that involves small objects () that are placed and moved in particular ways on a specially designed patterned game board, potentially including other components, e.g. dice. The earliest known uses of the ...
invented by
Christian Freeling Christian Freeling (born 1 February 1947, in Enschede, Netherlands) is a Dutch game designer and inventor of abstract strategy games, notably Dameo, Grand Chess, Havannah, and Hexdame. Freeling's designs cover a range of game types. Several o ...
. It belongs to the family of games commonly called
connection game A connection game is a type of abstract strategy game in which players attempt to complete a specific type of connection with their pieces. This could involve forming a path between two or more endpoints, completing a closed loop, or connecting all ...
s; its relatives include Hex and
TwixT TwixT is a two-player Abstract strategy game, strategy board game, an early entrant in the 1960s 3M bookshelf game series. It became one of the most popular and enduring games in the series. It is a connection game where players alternate tu ...
. Havannah has "a sophisticated and varied strategy" and is best played on a base-10 hexagonal board, 10 hex cells to a side. The game was published for a period in Germany by
Ravensburger Ravensburger AG is a German game, puzzle and toy company, publishing house, and market leader in the jigsaw puzzle market. History The company was founded by Otto Robert Maier in Ravensburg, a town in Upper Swabia in southern Germany. He began ...
, with a smaller, base-8 board suitable for beginners. It is nowadays only produced by Hexboards.


Game rules

One player plays as black; the other plays as white. White starts, after which moves alternate. The rules are as follows: * Each player places one stone of their color on the board per turn. * Stones are never moved, captured, or otherwise changed. * A player wins when they complete one of three different structures from unbroken lines, or paths, of connected stones, all of their colour: ** A ''ring'' is a loop around one or more cells (no matter whether the encircled cells are occupied by any player or empty); ** A ''bridge'', which connects any two of the six corner cells of the board; ** A ''fork'', which connects any three edges of the board; corner points are not considered parts of an edge. An example of all three winning combinations is shown above. The structure in the centre of the board is a ring; the structure on the left-hand side is a fork; the structure on the right-hand side is a bridge. Since the first player to move in Havannah has a distinct advantage, the
pie rule The pie rule, sometimes referred to as the swap rule, is a rule used to balance abstract strategy games where a first-move advantage has been demonstrated. After the first move is made in a game that uses the pie rule, the second player must sel ...
is generally implemented for fairness. This rule allows the second player to choose whether to switch positions with the first player after the first player makes the first move. Players of different strength can still play an interesting game when the weaker player (as white) is allowed to place two or more stones on the first turn.


Difference compared to Hex

In Hex, when the board is completely filled, exactly one player will have a winning connection; in Havannah a completely filled board will have usually more than one winning structures (but the game ends with first winning structure). Unlike in Hex, in Havannah draws are technically possible, in practice they are extremely rare. There has been one known draw between human players. Tactics are much easier to master than strategy, and differences in playing level are considerable.


Computer Havannah

In 2002 Freeling offered a prize of 1000 euros, available through 2012, for any computer program that could beat him in even one game of a ten-game match. For many years, computer programs lagged far behind human players. However, since 2010 several Havannah-playing programs have applied
Monte Carlo tree search In computer science, Monte Carlo tree search (MCTS) is a heuristic search algorithm for some kinds of decision processes, most notably those employed in software that plays board games. In that context MCTS is used to solve the game tree. MCTS ...
techniques resulting in some notable improvement in playing strength. The "Havannah Challenge 2012" was held October 15–19, 2012 during which Freeling played ten games against three of the strongest Havannah-playing programs available, playing (at least) one game as black and one as white against each opponent. Freeling lost the challenge when he had to resign a game with white against the Lajkonik program. Until 2019, the best humans were still by far stronger than computers. However
MetaTotoro
based on Polygames (an open-source project, initially developed by Facebook Artificial Intelligence Research and several universities), won four times in a row on the board of size 8 against the human player with the best ELO rank o
LittleGolem
who was also the winner of various tournaments. This result was achieved by the same program as the one used for beating best humans at Hex. It is a zero-learning based algorithm, as in AlphaZero, but with novelties: boardsize invariance thanks to fully convolutional neural networks (as in U-Net) and global pooling. This allows growing architectures, meaning the program can learn on a small board, and then extrapolate on a large board. Havannah is a recurring game at the
Computer Olympiad The Computer Olympiad is a multi-games event in which computer programs compete against each other. For many games, the Computer Olympiads are an opportunity to claim the "world's best computer player" title. First contested in 1989, the major ...
. It is played on a base-8 board and sometimes also on a base-10 board. During this competition the pie rule is used.


Computational complexity

Solving Havannah is
PSPACE-complete In computational complexity theory, a decision problem is PSPACE-complete if it can be solved using an amount of memory that is polynomial in the input length (PSPACE, polynomial space) and if every other problem that can be solved in polynomial sp ...
with respect to the size of the input graph. The proof is by a reduction from
generalized geography In computational complexity theory, generalized geography is a well-known PSPACE-complete problem. Introduction Geography is a children's game, where players take turns naming cities from anywhere in the world. Each city chosen must begin with the ...
and is based on using ring-threats to represent the geography graph. In detail, since Lichtenstein and Sipser have proved that generalized geography remained PSPACE-hard even if the graph is only bipartite and of degree at most 3, it only remains to construct an equivalent Havannah position from such a graph, which is accomplished by constructing various gadgets in Havannah.


Reviews

*'' Jeux & Stratégie'' #9


References


External links


Official site
MindSports.nl
Havannah
article on
Sensei's Library Sensei's Library (commonly referred to as SL among Go-players) is an Internet website and wiki A wiki ( ) is a form of hypertext publication on the internet which is collaboratively edited and managed by its audience directly through a ...
* {{bgg, 2759, Havannah Board games introduced in 1981 Abstract strategy games Connection games Ravensburger games