Quarto!

You need a java-capable browser to play quarto.

Click here to download the source of the Quarto applet. The zip file includes the sources for the Java applet, the Java standalone version and the C version.

Rules

There are 16 different pieces with 4 different characteristics: tall or short, round or square, light or dark, solid or hollow. Each player in turn selects and gives a piece to his opponent who must place it on an empty square on the board. The winner is the player who, by positioning a piece , creates a line of 4 pieces having at least one characteristic in common.

About the code

The standalone Java version is the easiest to read. The kernel of the algorithm can be found in the file "Board.java". We use the classic minimax algorithm. The most important optimization we did is that we do not search for a winning move. From the moment we find a move that garantees a draw, we stop searching and just do the move. The reason is that we calculated the game completely and it is impossible to win with a perfect opponent. I.e. It is always possible to reach a draw. It is easy to adapt the algorithm to make it search for a winning move. The C version is a highly optimized version and is VERY difficult to read without further explanation. It does not contain a user interface and needs to be used by providing an input file describing the current board position and a parameter describing the depth you want to calculate. It was used to calculate Quarto completely based on the symmetries of positions to cut down on the calculation work. The main optimizations in this version are:

The minimax algorithm was unfolded for three moves. That means that if a position is evaluated, the return value indicates the best value you can hope for whatever you do in the following three moves. This is faster as it avoids recursive function calls.
Every piece has a bit representation (01010101 = black,small,hollow,round and 10101010 = white,big,filled, square and 00000000 = empty) and we have tables containing the sum of every possible quarto, speeding up the evaluation considerably.
The evaluation function searches for loose or draw only. I.e. as long as you are not lost the game is consi
The program was ported to C.