COMPSCI 557
Search - Game Playing
Implement the game DotDot. Your implementation should incorporate alpha-beta
pruning with the search depth configurable at run time. You may
use any static evaluator you see fit. In fact, you may use different evaluators
for different search depths. Your program will play against the user of
your program, so you should provide a way for the user to review the current
state of the game and to input his or her next move.
We will run a series of tournaments to see whose program is best.
The top n/2 programs in a single tournament
will be awarded n/2 + 1 - r extra credit
points, where n is the number of competing programs and r
is the rank of the program. Three tournaments with search depths limited
to 2, 5, and 10 plies will be run. To run tournaments, your program should
be configurable so that either it or the user may start first. The board
size must also be configurable. For the tournament, each move should be
made in under 15 seconds.
The programs should have a garphical user interface (the code will be
provided). For the tournament, the programs will have
to connect to a server to establish a connection with another program
that wants to play. The details will be provided in due course of time.
The Usual Rules
DotDot is a simple game . The game starts out with a rectangular grid of
dots, as in...
. . . . .
.
. . . . .
.
. . . . .
.
. . . . .
.
. . . . .
.
The players, x and o, take turns connecting two dots. The
dots must be adjacent horizontally or adjacent vertically.
. . . . .
.
|
|
.---. .---. .---.
| |
|
. .---. . . .
|
. . . . .
.
|
. . . . .
.
If a player completes a square such that each corner of the square is adjacent
horizontally and vertically to two other corners of the square (this is
just a fancy way of saying a square whose sides do not contain any dots
other than the endpoints (this is just a fancy way of saying the smallest
possible square on the grid)), the player marks an x or an o,
as appropriate, in the middle of a square and gets to move again.
. .---. . .---.
| | |
| x |
.---. .---. .---.
| x | | |
.---.---. . . .
| x | |
|
.---. .---.---.---.
| o | |
.---.---. . .---.
When no more moves are possible, the player with the most marked squares
wins.
The COMPSCI 557 variant
In order to reduce the branching factor, we will add one requirement:
-
when connecting two dots, at least one of the dots must previously have
been connected (except for the first move)