Qubic

In General Interest, Anecdotes by Steve Sliwa

Background:

Qubic is a 4 x 4 x 4 tic-tac-toe game.

Wikipedia reports:

Qubic is the brand name of a four-in-a-row game played in a 4×4×4 matrix sold by Parker Brothers starting in 1953. The original box, and the 1972 reissue, described the game as “Parker Brothers 3D Tic Tac Toe Game”. Players take turn placing pieces to get four in a row horizontally or diagonally on a single board—or vertically in a column or diagonal line across four boards. The four boards were made of clear plastic with circular playing pieces that resembled small poker chips in red, blue, and yellow; each player used a single color. Markers could be placed in any unoccupied position, rather than stacked in a pile on a square as in Score Four. The game is no longer manufactured. Either two or three players could participate in a game. In two-person play, the first player will win if there are two optimal players. There are 76 winning lines. The 16 positions lying at the 4 space diagonals are equivalent and each involved in 7 winning lines; the other 48 positions are also equivalent, each being involved in four winning lines.

The game was weakly solved by Eugene Mahalko in 1976, Oren Patashnik in 1980 and then solved again by Victor Allis using proof-number search.

  • Eugene D. Mahalko, A Possible Win Strategy for the Game of Qubic, Computer Science Master’s Thesis, Brigham Young University, 1976
  • Oren Patashnik, Qubic: 4 x 4 x 4 Tic-Tac-Toe, Mathematics Magazine 53 (1980) 202–216
  • L .V. Allis, P. N. A. Schoo, Qubic solved again, in: H. J. van den Herik, L. V. Allis (Eds.), Heuristic Programming in Artificial Intelligence 3: The Third Computer Olympiad. Ellis Horwood, Chichester, 1992, pp. 192–204.

Robert Waldteufel of WylieDraaughts.com reports:  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 publically available; 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 independently solved the game of Qubic and wrote the program offered here. It plays perfectly in the sense that it always wins when it goes first, but it does not necessarily find the shortest win.


When I was a junior at Princeton I used to sneak downstairs in the EE department to work (or play) on one of the first UNIX computers.  It was PDP-8 or so and the UNIX system was being developed at Bell Labs down the road.  I was able to get an account because one of my soaring students was the computer administrator.  I used it to solve homework problems and, in particular, it helped me solve a touch structural design problem.

Exploring the various directories I discovered a program called qubic.  It didn’t really have directions, but I deduced it was some sort of 3-d tic-tac-toe program.  I would type in a random number like 1-1-1 and the computer would instantaneously reply with its own 3 digit sequence.  After several of these, it would respond with something to the effect:

“I have a forced win!  The following moves complete the game.  blah-blah-blah.  Then in it would end with QED.

Well the QED would really set me off.  See the anecdote related to QED.

So I would come in between classes and started playing the program more and more.  Always with the computer instantaneously responding and then having a closing QED gambit when it had forced win.  Did I mention QED?

One time, I must have stumbled into something because the computer actually took about 10 seconds to respond.  It ultimately did win with a QED.  But I thought there must be a way to beat the computer if it really had to think.  Plus the only way the game worked, the operator goes first.  I couldn’t imagine a game where going second was better than going first.

I told my former suitemate, Evan Flatow.  We actually cut classes for 3 days and got about 5 days into playing Qubic.  In fact, we finally mastered the game.  As reported above, it is a forced win for whom ever goes first.  We didn’t mathematically prove it, but we worked out a logic tree for all possible responses to our moves and developed a set of strategies and tactics to make them memorable for a person.  Basically, there are about half-dozen winning patters and about a dozen rules.

The big day came.  We had about 15 people come to the computer lab to watch me take on the computer.  I entered the first few moves and the computer responded as expected.  At about the eighth move the computer started to slow down.  It was having trouble escaping the trap.  The 10th move took about 2 minutes.  But unfortunately, on about the 12th move the computer disappeared, hung and never came back.  Apparently, it hadn’t been programmed to lose.  Darn!

I really wanted to type QED!

 

Print Friendly, PDF & Email

Share this Post