A Perfect Qubic-Playing Program

by Roberto Waldteufel

The game of Qubic is a 3-dimensional version of the familiar game of Noughts & Crosses (Tic Tac Toe in America). Unlike its trivial 2-dimensional sibling, Qubic is a difficult and moderately complex game. The aim is to get 4 in a row in any direction within a 4x4x4 cube.

The game was studied by Oren Patashnik, who published "Qubic: 4x4x4 Tic-Tac-Toe", in Mathematics Magazine, 53(4):202--216, September 1980, proving that Qubic is a first person win when played perfectly. In 1992 Victor Allis and Patrick Schoo wrote the first Qubic computer program guaranteed to win when playing first under tournament conditions. This 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.

In September 2004 your webmaster independantly solved the game of Qubic and wrote the program offered here. It playes perfectly in the sense that it always wins when it goes first, but it does not necessarily find the shortest win. The ZIP file is about 2 MB, and the unzipped files will occupy about 5 MB of hard disc space. Simply unzip and run the file Qubic.exe.

Enjoy :o)

Download QUBIC