Chess Problem Solver Project Chris Brown EECC 756 Spring 1999 5 20 99 1 Abstract The goal of this paper is to demonstrate a simple implementation of a parallel chess problem solving program A solution to a chess problem means that one or more set of moves exist such that a player can force checkmate on the opponent regardless of the moves the opponent makes during their turn The program as designed should efficiently accommodate a fairly large number of processors estimated in the range of a few to several hundred assuming a reasonably large problem size It has also been designed to accommodate future enhancements such as dynamic load balancing and a hierarchical group based approach Efficiency factors of the basic system and the enhanced system will be discussed along with a demonstration of the results of several problems 2 Problem Characteristics The chess solver problem is an example of a very large computation with an extremely small amount of inter process data dependencies In other words the communication to computation ratio is extremely low for even smaller problems with few moves to search The simplest approach to solving this problem is by using a search tree The problem is successively broken down using all possible moves for any given position until all possible results of each branch is determined At that time each of the branches can be examined to determine the overall result of the root node The result determination method will depend on whose turn it is at the root node If it s the solving players turn then any branch representing a possible solution is a valid solution for that root node No solutions at any of the branches means that the root node does not represent a possible solution If it s not the solving players turn then all branches underneath the root node must result in possible solutions in order for the root to represent a valid solution The reason behind the different algorithms for the players is because it is assumed that the solving player will always make the proper move in order to achieve checkmate and the opponent will always make the proper move in order to avoid checkmate To implement this system a message passing master slave process approach using PVM was chosen Also distributed task queues were chosen to keep communication to a minimum and to enable low overhead dynamic load balancing Due to the size of the computations the tasks will be coarse grain again to keep communication to a minimum The system is also designed for future flexibility The specifics will be discussed in detail in the following sections 3 Basic Software Requirements Three basic items were required to implement the system a basic data unit to describe a problem a basic software function to break down a problem and a tree search routine to find the result of a problem The basic data unit used will be referred to as a problem or a task interchangeably It contains all the necessary information about the state of a given chess position These include whose turn it is to move what player the problem is being solved for the maximum number of moves to search the move that was made to get to the position and the status of the pieces on the board The status of the pieces on the board refers to not only the pieces and their locations but also whether or not they have moved for castling purposes and whether or not the piece is able to be captured en passent The basic software function was created to break down a given problem It takes a given problem and breaks it into a list of new problems using all possible moves Each new problem will simply be a copy of the original with only a few changes it reflects the branching move and the maximum search level remaining counter is decremented by one As will be discussed this function is used to create the levels and branches in the search tree The basic tree search routine was created to examine each problem node in the tree and determine the necessary action There are only two possibilities the problem represents an end node or further investigation of the problem is necessary To be an end node the problem must represent either a possible or an impossible solution A possible solution means that the solving player has checkmated the opponent An impossible solution means that either a stalemate has occurred the opponent has checkmated the solving player or further investigation is still necessary but the remaining search levels has reached zero The following figure illustrates the tree branching data structure used in software Each branch level in the tree is simply stored as a singly linked list An array of pointers keeps track of each of the branch levels with a start of list pointer and a pointer to the current node being examined The root node of any given branch is the current task being examined at the next higher tree level When a search is complete on the lowest tree level the obtained result possible solution impossible solution is passed up to its root node The lowest tree level is then destroyed the current task pointer is advanced at the next higher level and if further investigation of the node is required then another level of the tree will be created representing all of the branches of that root 4 PVM Implementation A standard master slave program using PVM was used to take advantage of the high degree of parallelism inherent in this type of problem It s important to note that since spawning slave processes is very time consuming this design reuses slave processes during the course of the computation Only when the program is complete does the master kill the slave processes The only cost tradeoff with this method is a single value added in the message from the master to the slave that indicates the command type A very profitable tradeoff The master process is responsible for getting the initial problem from a text format and converting it to an original problem task The text file includes the desired number of processes the maximum number of moves to search the player who has the initial move who is also the solving player and the initial status of pieces on the board All necessary slave processes are created first The master must then break the original problem into a list of tasks using the break down problem function The tasks will then be handed out to idle slave processes one task per process until all tasks have been completed and the results returned by the slaves This means that when a process has completed a task