DOC PREVIEW
UW-Madison ECE 539 - GENETIC PROGRAMMING FOR CHECKERS PLAY

This preview shows page 1-2 out of 7 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 7 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 7 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 7 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Slide 1Slide 2Slide 3Slide 4Slide 5ConclusionsSlide 7GENETIC PROGRAMMING FOR CHECKERS PLAYDustin ShutesAbstract:This project uses genetic programming to develop a program that plays the game of checkers. Unlike games like tic-tac-toe checkers is an unsolved game, meaning that there is not yet a known way to always win. Most programs that are designed to play games against human opponents are developed with expert knowledge. They use databases of human knowledge to determine what appropriate play should be. Instead this program uses machine learning through genetic programming to decide moves.Legal MovesFor regular pieces on the board a legal move is one where the checker moves forward one row, and to the right or left one column into an unoccupied square. If one of those legal-move-squares is occupied by the opponent and the next square along the diagonal line is unoccupied, a ‘jump’ is performed where the opponent’s piece is removed and the unoccupied square becomes occupied by the checker making the move. If there is another legal jump from this square it will be performed in the same manner. Jumps can be chained together in this manner as long as there continues to be legal jumps. If a checker is in a position to make a legal jump it must take it. If a checker reaches its opponents back row, it becomes a ‘king’. King’s are special pieces that are allowed to move both forward and backward.Copyright © 1997, Pui Yee Chan, Hiu Yin Choi, Zhifeng Xiao. Move SelectionTo do this the program first generates a ‘game-tree’, where each node of the tree represents a possible future board configuration, and the root of the tree is the current board configuration. The child nodes of the root are the board configurations after the computer has done all of its legal moves. For each of these new board configurations all the legal countermoves are performed and are stored as children of their respective nodes. To determine what the best move is the program uses a recursive minimax search algorithm, with alpha-beta pruning.Mapping board to input of networkMapping 3x3 areas to the networkThe input layer of the network takes all of the 3x3 areas of the board and all of the 4x4 areas of the board as well as another 32 inputs that take the un-spatially configured board values. The network uses this input configuration to learn the spatial layout of the board. There are 2 hidden layers and a single output neuron that gives the value of the board for evaluation. The pieces are represented as -1 (for competitors piece) or +1 (for friendly piece) or +- K, the variable value assigned to kings.LearningThe program was started with 32 different, randomly generated, network weight configurations. For every generation 128 games are played with the two competitors randomly selected from the field of 32. Those strategies with winning records become parents for the next generation. Strategies reproduce through mutation with the following code for(i=1;i<=362;i++){ N = (double)(((double)rand())/RAND_MAX); //random number from 0 to 1 w.sigma[i] = w.sigma[i]*exp(.15694977*N);//update adaptation rate w.L2[i] = w.L2[i] + w.sigma[i]*(N-0.5);//update weight } for(i=1;i<=61;i++){ N = (double)(((double)rand())/RAND_MAX);//random number from 0 to 1 w.sigma[i+362] = w.sigma[i+362]*exp(.15694977*N);//update adaptation rate w.L3[i] = w.L3[i] + w.sigma[i+362]*(N-0.5);//update weight } for(i=1;i<=61;i++){ N = (double)(((double)rand())/RAND_MAX);//random number from 0 to 1 w.sigma[i+423] = w.sigma[i+423]*exp(.15694977*N);//update adaptation rate w.L4[i] = w.L4[i] + w.sigma[i+423]*(N-0.5);//update weight }Each strategy also has its king value updated in the following fashion: N = (double)( ( (double)rand() )/(RAND_MAX)/2)-0.25;//random number from -0.25 to 0.25 w.king = w.king + N;//update king if (w.king > 4) w.king = 4;ConclusionsAlthough it would be difficult to develop a checkers playing program through machine learning that would be able to compete with a program like Chinook (currently the worlds leading checkers playing program), given enough time and some experiments with network size and configuration winning strategies for the game of checkers could be developed through the use of genetic programming. In addition to time constraints for the learning process, the amount of memory available to form a large enough game tree to do adequate move look ahead is a large factor in the performance of the program.References:J. Maynard Smith, Evolution and the theory of Games. Cambridge, U.K.:Cambridge University Press, 1982Chellapilla, Kumar and Fogel, David, Evolution, Neural Networks, Games, and Intelligence.Banzhaf, Nordin, Keller, and Francome, Genetic Programming An Introduction. San Francisco, CaliforniaMorgan Kaufmann Publishers, Inc.Simon Haykin, Neural Networks: A Comprehensive Foundation, Prentice Hall, New Jersey, second edition, 1999.Vajda, S, An introduction to linear programming and the theory of games. London Notes produced for the McGill University, Montreal Canada, were also used in the development of this


View Full Document

UW-Madison ECE 539 - GENETIC PROGRAMMING FOR CHECKERS PLAY

Documents in this Course
Load more
Download GENETIC PROGRAMMING FOR CHECKERS PLAY
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view GENETIC PROGRAMMING FOR CHECKERS PLAY and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view GENETIC PROGRAMMING FOR CHECKERS PLAY 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?