An autonomous robot playing the board game checkers

International Journal of Electrical Engineering Education, Jan 1998 by Zribi, M, Sung, E

It should be noted that after the camera captures the pre-focused image of the object, the image is pre-processed to improve the quality and accuracy of the captured image. Three common techniques can be used to pre-process images: noise elimination, contrast stretching and connectivity1. After the enhancement process is completed, the image, which is a 640 x 480 block of pixels, is ready for colour classification. By analysing each and every pixel, and manipulating blocks of pixels between the host's (personal computer) memory and the memory of the DT3851 board, the task of differentiating the black and white seeds, the game board, as well as the borders of the game board is accomplished.

The vision module (EYE) was completed successfully. This module identifies a move made by a human player and subsequently sends this move to the BRAIN. The BRAIN will then determine the next move and instruct the HAND to move appropriately.

3 THE CHECKERS SOFTWARE MODULE (BRAIN)

The checkers software program forms the brain of the entire system. Figuring out a good strategy to play checkers is probably the most challenging part of the project. The students needed to familiarise themselves with some concepts from artificial intelligence and then write a checkers program whose main task is to generate the best move to be made by the robot. The C language is used for programming purposes.

Two-player board games such as checkers and chess are known as discrete prefect information games4. This is because the number of configurations the board can assume is finite. Also, both players have the same information about the game in progress as all the pieces and their positions are visible to both players during a game of checkers4. One important characteristic that needed to be considered when figuring out a good strategy to play board games such as checkers and chess is the `looking ahead' at future positions property4.

One of the algorithms that can be used while playing board games is the MINIMAX algorithm. This algorithm attempts to maximise the player's advantage and minimise the opponent's advantage. The MINIMAX algorithm is applied in searching game trees to determine the best move to be made by the current player of a game4. The game tree consists of all moves available to the current player. The starting position is represented by the root of the tree; the branches of the tree represent possible moves that the player could make. The final positions of the game are represented by the leaves. Due to the computational limitations, it is impractical to have a tree of all possible moves to the end of the game. Thus, a static evaluator is used. Instead of creating the whole tree of a game, the program will create a tree up to a maximum depth, called the search depth. For example, a search depth of two will create a tree starting with all the possible moves available to the first player (black) followed by all possible moves by the second player (white) in response to black's move. If the game is evaluated at a leaf of a tree, then the projected status of the game after that sequence of moves is executed can be obtained4. As the search depth gets bigger, the computer will be able to 'look' further into the game. A bigger search depth of the game tree yields more information about possible advantages or disadvantages and hence results in a better move. However, the search depth needs to be chosen carefully so that the game can be implemented practically on a personal computer.