AQ Squares is a simple strategy game with game play similar to that of Ataxx. The rules of the games are simple. A player can move up to two cells away from their selected location. If they move to a cell immediately next to the starting cell, they duplicate. If they move two cells, they jump. Any cell next to the new location owned by the player's opponent will be taken over. Play continues until there are no more moves left. The player with the most cells wins the game.
This game was developed for the purpose of implementing the algorithm Minimax with Alpha- beta pruning. It is more for demonstration purposes of technique than game play, although the game is functional.
Source code for the game will compile for Linux system as long as the freeglut libraries are installed.
Binaries for Windows are provided that should run on any 32 or 64-bit system.
Game play is fairly obvious—you'll figure it out.
Archives signed by Andrew Que. Keys are generated yearly and can be found on the MIT PGP Public Key Server by doing a search for Andrew Que. They can also be downloaded directly from DrQue.net.
Released November 25, 2016.
SHA256: 58a216cf6005810355430d8bd7a7c00aa447346be1331a6e6bae42bb68337910
SHA256: 8985efb51d3ab0ebeab9a2eb3f2fa152e01df3c4aecbd0c5266bfe126eeeeec2
SHA256: a2a197b93db23a32d801016f0585f267067bde89bf707dfd621c08cb9d9c0a21
SHA256: 66cb6c1dbbba77457f8ad9a2eafc1d2d660423a39a5514086a34ba4a2f27454c
Released November 11, 2016.
SHA256: 916316a7874070b8aacdb3f73dc0461473ce45eb10c8ce0f56ac52595348895d
SHA256: c6ac9eb1480db94e0290c59f5aa797fddf19bc1d415c3837ee111df3dfea623a
Only the source code is distributed with 1.0. Designed for POSIX (i.e. Linux-like) environments. It requires ncurses which is used for the user interface.
To compile, unpack and run make.
7z e aqSquares_v1.0.7z
make
The game's source code is written in portable C compliant with the C99 standard. The user interface requires ncurses. This the UI functions are wholly contained such that if the UI functions are rewritten the game could use some other system.
The heart of the game is field.h. This is a set of inline C functions that govern how the playing field works and is stored. For speed, the playing field is contained in two 64-bit words, one for each player. Each bit of the word defines if the cell for that location is occupied. The 64-bit word id divided into 7 rows and 8 columns. The 8th column is not used, but define this way to make the math for converting row/column into a linear index faster (shift rather than multiply). Playing logic is done by shifts, ANDs, and OR. Making these functions as fast as possible allows the AI to evaluate moves more quickly.
The artificial intelligence unit is in ai.c uses Minimax with Alpha- beta pruning. Each possible move for a player is evaluated to a given depth, and the move with the best gains is made. Currently the depth is set to 5 levels for the computer.
Random numbers are generated using xorshift algorithm, seeded from /dev/urandom. This PRNG was chosen because of it's long period (2128) and extremely fast performance. This algorithm could easily be changed by adding hooks to a different algorithm in random.c. Random numbers are used to select the AI's move should multiple moves produce the same gains.
Unit tests are provided. They can be compiled using a target of tests during build.
make tests
Currently the following unit tests are implemented:
Code coverage can also be checked by building with the target of coverage. It requires that lcov be installed. Code coverage analysis is then placed in HTML files in a directory called coverage.
Profiling can also be done. It requires perf as well as gprof2dot. Using the target aiProfile will profile the AI unit and produce results in aiProfile.png.
Leave a comment if you find this program useful.
AQ Squares is is free, open-source software released under the GNU license. Game play is a clone of Ataxx.
AQ Squares is written and maintained by Andrew Que. To get in touch with Andrew Que, visit his contact page.
(C) Copyright 2016-2017 by Andrew Que.