Overview of Program Design
Our program to play Anti-chess was designed with the following criteria in mind:
- Modularity: the code should be modular, enabling several people to work on it simultaneously with a minimum of interference once the interfaces have been defined.
- Simplicity: the module interfaces should be designed to facilitate clean, simple code with a minimum of unnecessary "baggage" and a maximum of readability. This will make creating and maintaining the code much easier.
- Extensibility: it should be easy to modify the software to incorporate reasonable modifications to the specifications.
According to the above criteria, the program was split into several main modules.
- chess_board: this data structure is the central repository for the much of the information on the (anti)chess game. It stores the current positions of the pieces on the board, and handles all changes to the chess board, including checking whether moves are legal. This data structure is passed back and forth between the various modules to describe the state of the game.
- user_interface: the user interface of the program was broken off into this module, which is designed to implement the interface with as little knowledge of the game as possible (without sacrificing efficiency or functionality). All interaction with the user goes through this data structure, although user_interface's code is often unaware (in principle) as to the actual meaning of the interaction that it is facilitating. In this way, changes to the behavior of the program, modifications to the specifications, etcetera, can be implemented with minimal repercussions on this code (hopefully requiring changes only in one or two places in the main program).
- computer_player: implementation of a computer anti-chess player which, given the current state of a game, will return the computer's move. machine_player will be implemented as a wrapper around this and the chess_board data structures. The reasons that we did not use the machine_player data structure itself internally in our program are outlined below.
- static_evaluator: artificial intelligence algorithms for playing chess (such as a min-max search) generally require at their root a "static evaluator" which, given the current state of the game, returns a heuristic number describing how favorable the game is for a given player. This behavior is broken off into a separate module in our program for a special reason: we would like to play the computer_player against itself, using different static evaluators, in order to determine an optimal strategy. In particular, the specifications for this data structure include procedures to facilitate the use of so-called "genetic algorithms" to search for the best strategy.
- main: Finally, we have a main program module, which calls all of the other modules and is responsible for the flow of control of the program, determining the order, content, and meaning of user interactions and so on. By putting most of the control of the program here, it should be relatively easy to implement reasonable changes. In addition, maximal isolation between the separate modules is maintained by minimizing the extent to which they call one another directly.
computer_player vs. machine_player
There were several reasons that we used our own computer_player data structure inside the program, rather that the provided machine_player interface. The machine_player interface will still be implemented in order that our program may participate in the tournament--its implementation will be as a "wraparound" of the computer_player and chess_board data structures.
The reasons that we did this were as follows:
- Better Abstraction Barriers:
- The machine_player interfaces specify that data be passed back and forth with it in the human-readable format of the user interface. This breaks down the abstraction barrier between the interface and the computer strategy modules.
- machine_player must maintain a completely redundant copy of all the state information for the game, and in addition has to check whether moves are legal, etc. Thus, the barrier between the strategy and arbiter modules is destroyed.
- Cleaner Code: The above two problems with machine_player not only violate abstraction barriers, they also make for "unclean," difficult to read code--they require continual conversions back and forth from human-readable formats when calling machine_player, and also require maintenance of redundant code and data structure copies.
- Ease of Optimization: We would like to be able to optimize the computer strategy by playing the computer against itself with many slight variations in strategy, possibly utilizing genetic algorithms. This would be impossible with the machine_player data structure, since it doesn't allow us to pass it any information regarding a specific strategy to be used (e.g. a static evaluator).
The program specifications have been revised and elaborated in various ways, as described in the attached document.