Chess Problem Solver ProjectEECC-756Chess Problem Solver ProjectChris BrownEECC-756Spring 19995/20/991. AbstractThe goal of this paper is to demonstrate a simple implementation of a parallel chess problem solvingprogram. A solution to a chess problem means that one or more set of moves exist such that a player canforce checkmate on the opponent, regardless of the moves the opponent makes during their turn. Theprogram as designed should efficiently accommodate a fairly large number of processors estimated in therange of a few to several hundred assuming a reasonably large problem size. It has also been designed toaccommodate future enhancements such as dynamic load balancing and a hierarchical group-basedapproach. Efficiency factors of the basic system and the enhanced system will be discussed, along with ademonstration of the results of several problems.2. Problem CharacteristicsThe chess solver problem is an example of a very large computation with an extremely small amount ofinter-process data dependencies. In other words, the communication to computation ratio is extremely lowfor even smaller problems with few moves to search. The simplest approach to solving this problem is byusing a search tree. The problem is successively broken down using all possible moves for any givenposition until all possible results of each branch is determined. At that time, each of the branches can beexamined to determine the overall result of the root node. The result determination method will depend onwhose turn it is at the root node. If it’s the solving players turn, then any branch representing a possiblesolution is a valid solution for that root node. No solutions at any of the branches means that the root nodedoes not represent a possible solution. If it’s not the solving players turn, then all branches underneath theroot node must result in possible solutions in order for the root to represent a valid solution. The reasonbehind the different algorithms for the players is because it is assumed that the solving player will alwaysmake the proper move in order to achieve checkmate and the opponent will always make the proper movein 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 overheaddynamic load balancing. Due to the size of the computations the tasks will be coarse grain, again to keepcommunication to a minimum. The system is also designed for future flexibility. The specifics will bediscussed in detail in the following sections.3. Basic Software RequirementsThree basic items were required to implement the system: a basic data unit to describe a problem, a basicsoftware 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 thenecessary 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 wasmade to get to the position, and the status of the pieces on the board. The status of the pieces on the boardrefers to not only the pieces and their locations, but also whether or not they have moved for castlingpurposes 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 andbreaks it into a list of new problems using all possible moves. Each new problem will simply be a copy ofthe original with only a few changes: it reflects the branching move and the maximum search levelremaining counter is decremented by one. As will be discussed, this function is used to create the levelsand branches in the search tree.The basic tree search routine was created to examine each problem node in the tree and determine thenecessary action. There are only two possibilities: the problem represents an end node, or furtherinvestigation of the problem is necessary. To be an end node, the problem must represent either a possibleor 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 thesolving 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 thetree is simply stored as a singly linked list. An array of pointers keeps track of each of the branch levelswith a start-of-list pointer and a pointer to the current node being examined. The root node of any givenbranch is the current task being examined at the next higher tree level. When a search is complete on thelowest 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 iffurther investigation of the node is required, then another level of the tree will be created representing all ofthe branches of that root.4. PVM ImplementationA standard master/slave program using PVM was used to take advantage of the high degree of parallelisminherent in this type of problem. It’s important to note that since spawning slave processes is very timeconsuming, this design reuses slave processes during the course of the computation. Only when theprogram is complete does the master kill the slave processes. The only cost tradeoff with this method is asingle value added in the message from the master to the slave that indicates the command type. A veryprofitable tradeoff.The master process is responsible for getting the initial problem from a text format and converting it to anoriginal problem task. The text file includes the desired number of processes, the maximum number ofmoves to search, the player who has the initial move (who is also the solving player), and the initial statusof pieces on the board. All necessary slave processes are created first. The master must then break theoriginal problem into a list of tasks using the “break down