Pentominoes: A First Player Win
Hilarie K. Orman · 1997
This article reports on a search-based computer proof that the game of pentominoes is a first-player win. Three search strategies were used in this proof, with dramatically different effects on the running time of the search. The two most effective strategies are compared and discussed. The Short History of Pentominoes Pentominoes is a two-player game involving twelve pieces—the regular 5- ominoes shown in Figure 1—and an 8 x 8 board. Players alternate placing pieces on the board, covering whole squares and without overlap. The player who cannot make a move loses. The game was first proposed by Solomon W. Golomb in the mid-fifties. Martin Gardner [1959] popularized it, also citing Golomb's work [1954] about polyominoes and checkerboards. See also [Golomb 1962; 1965]. In 1971, it was suggested that the game could be solved by computer search [Beeler et al. 1972], but no attempts to implement such a solution are known to me. In 1975 I wrote a computer program that played pentominoes, and used a PDP-11/45 computer to investigate the feasibility of a complete solution. Although the program was an excellent player against human opponents, at that time a complete solution was unattainable. Today, high-speed workstations have changed the picture. A new search program exhaustively examined the game subtrees arising from certain two first moves. One of the moves was proved to be a win, and this assertion was verified by an independent program. The winning move was determined in about two weeks of execution time on a 64-bit 175 MHz DEC Alpha processor. The verification was done on a Sun IPC Sparestation in about five days.