HQ

I've been experimenting with adding some AI techniques to a two-player, imperfect information, continuous motion game that I call HQ. The game is written in C++ and runs on UNIX machines with X-windows. My first effort was to see how well a program would play using a traditional alpha-beta search.

I find that the program plays very well in tactical situations, but is easily defeated using simple strategic moves. This was no big surprise. I was pleased to find out that even a 5-ply search can be performed in a reasonable length of time. For example, a 66MHz 486 searches 5-ply in about two minutes, and an Ultrasparc or 200 MHz Pentium Pro will do the search about 10 times faster.

Although the lion's share of the work has been on representation and search issues, I have worked a little on an X-window interface that allows either a person to play the machine, or the machine to play itself. Here is a position from the middle of a game I played.

Here is an mpeg movie showing me (the blue player) against the computer (the orange player). The computer is performing a three ply search. The orange pieces are only visible when they are within sensor range of one of the blue pieces. Here is what really happened during this game.