A Perfect Qubic-Playing Program

The game has a long history of exercising the minds of computer scientists. In 1972 The MIT Artificial Intelligence Lab produced a document called HAKMEM with a list of computational problems which the authors considered worth working on. The list included some problems which were considered unfeasible, such as the games of Chess and Go. The two hardest problems among those deemed feasible were draughts (checkers in America) and Qubic. In the context of feasability, we must remember the computing technology at this time was very feeble by today's standards.

In the final year of his degree at Yale University in 1976 the game was studied by Oren Patashnik, who set out to prove that Qubic was, under optimal play, a win for the first player. Although he graduated without solving Qubic, he continued to work on the game in the following year using the University's PDP-10 machine when it was not busy, usually in the middle of the night. Patashnik estimated that, at commercial rates for machine time, his work on Qubic during this time would have cost some $50 million! Finally early in the morning of 24th May 1977 his program completed a much condensed form of a complete search tree for the game proving that the first player wins with optimal play. This condensed form consisted of an opening book which, it was claimed, led to end nodes where a forcing sequence leading to a win were always present.

Martin Gardner wanted to announce Patashnik's Qubic proof in his Mathematical Games column in Scientific American Magazine if he could get someone to verify the proof. Any mathematical result needs verification, and for this result in particular he had previously received many claims of proof that did not stand up to scrutiny. Eventually Elwyn Berlekamp, who was working on the combinatorial games book Winning Ways with co-authors John Conway and Richard Guy, and who wanted to include the result in the book, enlisted Ken Thompson at Bell Labs to examine Patashnik's game-tree data and verify that it was indeed correct and complete. Ken was one of the creators both of the Unix operating system and also of the historic chess program Belle, which won the World Computer Chess Championship in 1980.

So Oren gave Ken a "dictionary" containing 2929 “strategic” moves — a very succinct distillation of the game tree — and he finished the verification in October 1978. Martin Gardner's announcement was a few months later in his January 1979 column (Scientific American, volume 240, number 1, pages 18–28), and Berlekamp, Conway, and Guy included the result in Winning Ways (chapter 22, Academic Press, 1982). Oren Patashnik's own paper in Mathematics Magazine (volume 53, pages 202–216, September 1980) describes the proof.

It was another 12 years before Dutch computer scientists Victor Allis and Patrick Schoo wrote the first Qubic computer program guaranteed to win when playing first under tournament conditions in 1992. They solved the game without access to, or knowledge of Patashnik's work, using proof number search to generate their own book of strategic moves, whereas Patashnik had laboriously selected his strategic moves by hand and used a depth first search program that searched only forcing moves to verify the status of the leaf nodes as first player wins. Proof number search was at this time a new tool in the armory of game programming and Allis used it to solve several other games around this time, notably Go-Moku, Awari and Connect-Four. This Qubic playing program has never been made public, but has competed in the Computer Games Olympiad, winning all the games where it played first and also about half the games where it played second, which was sufficient to win a gold medal. Subsequently they published their paper on solving the game, and it was removed from the list of games at future Olympiads.

After another 12 years had elapsed, in September 2004 your webmaster, without access to the work of either Oren Patashnik or Victor Allis and Patrick Schoo, independently solved, or so I thought, the game of Qubic using a Pentium desktop computer over several weeks while living on the remote Hebridean Isle of Jura, and wrote a program called Qubic for the Windows platform. My method was to develop a set of heuristics to guess the best strategic moves and then use a powerful depth first search algorithm with a large transposition table in memory to verify the forcing wins at the leaf nodes. I was unfamiliar with proof number search at this time, but had written strong draughts and chess playing programs based on another depth first search algrithm, MTDF, first developed by Aske Plaat. I believed that this Qubic program played the game perfectly in the sense that it would always win when it goes first, but it would not necessarily find the shortest win. However, unlike Patashnik's work, my analysis has never been independently verified by anybody else.

In Spring 2007 I became a full time nomad, technically homeless, but living on the road in an old bus. I lost most of my possessions from my house-dwelling days, including my desktop computer with the source code to this and many other programs I had written, as well as my compiler and other software tools that I used to use to develop AI projects, but by chance in late 2017 after over a decade on the road, during which time I had done no programming at all, I stumbled upon Oren Patashnik's old opening book for the game on the internet, which piqued my interest. I don't often have enough electricity to spend the sort of time on my laptop needed to write artificial intelligence programs, but nevertheless I downloaded an open source free compiler and used this opening book to write another Qubic program called Oxo, which also always wins when it goes first, but is much leaner in that it only occupies about a quarter of a megabyte unpacked compared to over 5 MB for Qubic, and the zip file is under 100 kilobytes, compared to 2 MB for Qubic. The graphics are not quite as nice as the first version, but in strength they were about equal. In fact, since Oxo uses Oren Patashnik's independently verified opening book guaranteeing a first player win, whereas Qubic only used my own unverified analysis to achieve that result, it could be argued that Oxo is the more reliable of the two programs. Simply unzip and run the file oxo.exe.

Enjoy :o)