[A couple of corrections edited in 1998/06/14; Thanks Oren!-- djr]
=============================================================================
From: Mark Bassett <markb@iisc.co.uk>
Newsgroups: rec.games.abstract
Subject: Re: [Help] Qubic
Date: Thu, 14 Dec 95 09:56:44 PDT

In article <4anrlj$44o@vixen.cso.uiuc.edu>, <kwok@symcom.math.uiuc.edu> 
writes:
> 
> I think Qubic is a.k.a. 4x4 tic-tac-toe.
> 
> I heard that this games is solved.  Is the solution a consequence
> of Hales-Jewitt's Theorem?  What is the solution?
[sig deleted - djr]

Qubic is actually 4 x 4 x 4 tic-tac-toe ( i.e. three-dimensional ).
Alas, while Hales-Jewitt's theorem is very lovely, it wasn't used to solve
the game. The solution was discovered twice: initially [by Oren Patashnik -djr]
using a combination of (quite a lot of) human experience and a tree-searching
computer program; later [by Victor Allis -djr] using a more advanced collection
of algorithms which enabled a computer to solve the game "on its own".

The techniques used in the second attempt are called db-search and pn, or 
proof-number, search. pn-search in particular is a very elegant technique.
If you can do a web-search for "proof number search" you will find the 
thesis of the algorithms' inventor, and a description of their application 
to Qubic and other games. Alternatively, send me email and I will look up 
my copy of the thesis and let you know how to get hold of a copy. Right 
now I can't even remember the thesis' author - how annoying!

Regards,

Mark
markb@isc.co.uk
==============================================================================

From: cazenave@laforia.ibp.fr (CAZENAVE Tristan 40.44.62.29 Thesards de Pitrat)
Newsgroups: rec.games.abstract
Subject: Re: [Help] Qubic
Date: 14 Dec 1995 11:03:43 GMT

Victor Allis Thesis :

http://www.cs.vu.nl/~victor/thesis.html