To: Dr. Marion Ben-Jacob
From: Robert C. Radcliffe
RE: Checkers Agents
This paper presents a novel agent-based approach to building an automatic checkers-player. Each piece has four agents representating the four possible directions of movement. Each agent "bids" for permission to move/jump, if possible, based on the agent's point of view of the world (obtained from another agent) and a shared, standardized evaluation mechanism. An additional agent arbitrates the bids and determines the order of play.
My ideas for this approach are based on John H. Holland's book Emergence: from chaos to order (Holland 1998), although Holland's proposal differed in using board-based (not piece-based) cellular automata. The key insight is the use of simple autonomous agents to generate emergent complex behavior. Holland discusses Samuel's original checkers player in depth (Samuel 1959).
Checkers playing rules are from According to Hoyle (Frey 1970).
Note: The tables in this report are best viewed in Netscape v4.7+.
Each piece has four agents representating the four possible directions of movement. I will label them LF (left front), RF (right front), LR (left rear) and RR (right rear). Due to symmetry considerations (see below), left agents are presented a reversed left-right view of the world from the corresponding right agent. Black agents are presented a top-bottom reversed view of the world from white agents. Bidder agents "know" whether they are front or rear, but not whether they are left or right. This is because front and rear have non-symmetrical meaning in the game.
Each Bidder agent is in one of three states:
Blocked
Since (uncrowned) "single men" can only move forward, their LR and RR agents are always Blocked, until they become "kings." An agent may be Blocked by a board edge or certain combinations of other pieces. In short, if a Bidder agent is not in one of the other two states, it is in the Blocked state.
CanMove
If the immediate next diagonal space in the Bidder agent's direction (LF, RF, etc.) is vacant and the single-man rule does not apply, the agent is in the CanMove state.
CanJump
If the immediate next diagonal space in the Bidder agent's direction (LF, RF, etc.) is occupied by one of the opponent's pieces (king or single man), and if the next diagonal space beyond that piece is vacant, the agent is in the CanJump state.
Each agent "bids" for permission to move/jump, if possible, based on the agent's point of view of the world (the tailored board position obtained from another agent, the Accountant). Evaluation is provided by a mechanism "shared", either explicitly or implicitly by all the player's Bidder agents, perhaps by a neural net or the genetic algorithm: see details below.
A simple agent (the Auctioneer) arbitrates the bids and determines order of play. The rules of checkers require a jump if possible, so CanJump agents always submit bids to the Auctioneer agent, which selects the highest bidder to determine the next move. Only if there are no CanJump agents for a player, the Auctioneer sends messages to all the CanMove agents to submit bids, of which the highest is selected. Otherwise, of course, the player loses and the game is over.
Once the winning Bidder agent is selected, the Auctioneer agent notifies the Accountant agent, which updates all the world views of the Bidder agents reflecting the move just made.
The Auctioneer agent also handles continued jumping, accepting new bids only from the CanJump agents of the piece that just jumped. Otherwise, the Auctioneer starts again with opponent's Bidder agents.
The extended-border game board is a virtual 22 by 22 array with the 8 by 8 checkerboard in the center. Every other cell is empty and does not figure in play or computation. However the extra-checkerboard cells on diagonals with the playable positions of the checkerboard (here marked with "--") have a distinguished status different from "vacant", let's say "outside", for computation purposes. This "outside" status never changes, unlike the playable spaces. This virtual array might be an actual array or generated by rules in code.
The actual playing positions are numbered in the standard way (Frey 1970) for reference.
| 00 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | |
| 00 |
-- |
-- |
-- |
-- |
-- |
-- |
-- |
-- |
-- |
-- |
-- |
|||||||||||
| 01 |
-- |
-- |
-- |
-- |
-- |
-- |
-- |
-- |
-- |
-- |
-- |
|||||||||||
|
02 |
-- |
-- |
-- |
-- |
-- |
-- |
-- |
-- |
-- |
-- |
-- |
|||||||||||
| 03 |
-- |
-- |
-- |
-- |
-- |
-- |
-- |
-- |
-- |
-- |
-- |
|||||||||||
| 04 |
-- |
-- |
-- |
-- |
-- |
-- |
-- |
-- |
-- |
-- |
-- |
|||||||||||
| 05 |
-- |
-- |
-- |
-- |
-- |
-- |
-- |
-- |
-- |
-- |
-- |
|||||||||||
| 06 |
-- |
-- |
-- |
-- |
-- |
-- |
-- |
-- |
-- |
-- |
-- |
|||||||||||
| 07 |
-- |
-- |
-- |
-- |
01 |
02 |
03 |
04 |
-- |
-- |
-- |
|||||||||||
| 08 |
-- |
-- |
-- |
05 |
06 |
07 |
08 |
-- |
-- |
-- |
-- |
|||||||||||
| 09 |
-- |
-- |
-- |
-- |
09 |
10 |
11 |
12 |
-- |
-- |
-- |
|||||||||||
| 10 |
-- |
-- |
-- |
13 |
14 |
15 |
16 |
-- |
-- |
-- |
-- |
|||||||||||
| 11 |
-- |
-- |
-- |
-- |
17 |
18 |
19 |
20 |
-- |
-- |
-- |
|||||||||||
| 12 |
-- |
-- |
-- |
21 |
22 |
23 |
24 |
-- |
-- |
-- |
-- |
|||||||||||
| 13 |
-- |
-- |
-- |
-- |
25 |
26 |
27 |
28 |
-- |
-- |
-- |
|||||||||||
| 14 |
-- |
-- |
-- |
29 |
30 |
31 |
32 |
-- |
-- |
-- |
-- |
|||||||||||
| 15 |
-- |
-- |
-- |
-- |
-- |
-- |
-- |
-- |
-- |
-- |
-- |
|||||||||||
| 16 |
-- |
-- |
-- |
-- |
-- |
-- |
-- |
-- |
-- |
-- |
-- |
|||||||||||
| 17 |
-- |
-- |
-- |
-- |
-- |
-- |
-- |
-- |
-- |
-- |
-- |
|||||||||||
| 18 |
-- |
-- |
-- |
-- |
-- |
-- |
-- |
-- |
-- |
-- |
-- |
|||||||||||
| 19 |
-- |
-- |
-- |
-- |
-- |
-- |
-- |
-- |
-- |
-- |
-- |
|||||||||||
| 20 |
-- |
-- |
-- |
-- |
-- |
-- |
-- |
-- |
-- |
-- |
-- |
|||||||||||
| 21 |
-- |
-- |
-- |
-- |
-- |
-- |
-- |
-- |
-- |
-- |
-- |
The Accountant agent keeps track of the board position changes resulting from moves selected by the Auctioneer agent. After each move, all the Bidder agents are sent information to update their own world-views, or perhaps a complete 15 by 15 array. Left agents are sent left-right reversed information. Black agents are sent top-bottom and left-right reversed information.
The Accountant agent also deletes the Bidder agents of "captured" pieces.
Each Bidder agent has a tailored view of the world provided to it by the Accountant agent, that consists of a 15 by 15 array, with the position of the Bidder agent's piece in the center (column 7, row 7) regardless of where the piece is on the checkerboard. This is so the bid evaluation mechanism is standardized for each Bidder agent. Notice the "outside" cells. The "empty" cells, again, are not used.
Below is the world view of the RF (Blocked) and RR (Blocked) agents of a white piece in location 04:
| 00 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 | 13 | 14 | |
| 00 |
-- |
-- |
-- |
-- |
-- |
-- |
-- |
-- |
|||||||
| 01 |
-- |
-- |
-- |
-- |
-- |
-- |
-- |
||||||||
|
02 |
-- |
-- |
-- |
-- |
-- |
-- |
-- |
-- |
|||||||
| 03 |
-- |
-- |
-- |
-- |
-- |
-- |
-- |
||||||||
| 04 |
-- |
-- |
-- |
-- |
-- |
-- |
-- |
-- |
|||||||
| 05 |
-- |
-- |
-- |
-- |
-- |
-- |
-- |
||||||||
| 06 |
-- |
-- |
-- |
-- |
-- |
-- |
-- |
-- |
|||||||
| 07 |
01 |
02 |
03 |
04 |
-- |
-- |
-- |
||||||||
| 08 |
05 |
06 |
07 |
08 |
-- |
-- |
-- |
-- |
|||||||
| 09 |
09 |
10 |
11 |
12 |
-- |
-- |
-- |
||||||||
| 10 |
13 |
14 |
15 |
16 |
-- |
-- |
-- |
-- |
|||||||
| 11 |
17 |
18 |
19 |
20 |
-- |
-- |
-- |
||||||||
| 12 |
21 |
22 |
23 |
24 |
-- |
-- |
-- |
-- |
|||||||
| 13 |
25 |
26 |
27 |
28 |
-- |
-- |
-- |
||||||||
| 14 |
29 |
30 |
31 |
32 |
-- |
-- |
-- |
-- |
Below is the world view of the RF and RR agents of a white piece in location 18. RF examines space 15 (and possibly 11) to determine if it can move or jump; if the piece is a king, RR examines space 23 (and possibly 27):
| 00 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 | 13 | 14 | |
| 00 |
-- |
-- |
-- |
-- |
-- |
-- |
-- |
-- |
|||||||
| 01 |
-- |
-- |
-- |
-- |
-- |
-- |
-- |
||||||||
|
02 |
-- |
-- |
-- |
-- |
-- |
-- |
-- |
-- |
|||||||
| 03 |
-- |
-- |
01 |
02 |
03 |
04 |
-- |
||||||||
| 04 |
-- |
-- |
05 |
06 |
07 |
08 |
-- |
-- |
|||||||
| 05 |
-- |
-- |
09 |
10 |
11 |
12 |
-- |
||||||||
| 06 |
-- |
-- |
13 |
14 |
15 |
16 |
-- |
-- |
|||||||
| 07 |
-- |
-- |
17 |
18 |
19 |
20 |
-- |
||||||||
| 08 |
-- |
-- |
21 |
22 |
23 |
24 |
-- |
-- |
|||||||
| 09 |
-- |
-- |
25 |
26 |
27 |
28 |
-- |
||||||||
| 10 |
-- |
-- |
29 |
30 |
31 |
32 |
-- |
-- |
|||||||
| 11 |
-- |
-- |
-- |
-- |
-- |
-- |
-- |
||||||||
| 12 |
-- |
-- |
-- |
-- |
-- |
-- |
-- |
-- |
|||||||
| 13 |
-- |
-- |
-- |
-- |
-- |
-- |
-- |
||||||||
| 14 |
-- |
-- |
-- |
-- |
-- |
-- |
-- |
-- |
I have arbitrarily denoted left as the "reversed" view of right.
Below is the world view of the LF and LR agents of a white piece in location 18 for comparison with the previous world view.LF examines space 14 (and possibly 09) to determine if it can move or jump; if the piece is a king, LR examines space 22 (and possibly 25). Because of the reversal, LF and LR are looking at the same kind of patterns as RF and RR, respectively, namely diagonally to the right.
| 00 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 | 13 | 14 | |
| 00 |
-- |
-- |
-- |
-- |
-- |
-- |
-- |
-- |
|||||||
| 01 |
-- |
-- |
-- |
-- |
-- |
-- |
-- |
||||||||
|
02 |
-- |
-- |
-- |
-- |
-- |
-- |
-- |
-- |
|||||||
| 03 |
-- |
04 |
03 |
02 |
01 |
-- |
-- |
||||||||
| 04 |
-- |
-- |
08 |
07 |
06 |
05 |
-- |
-- |
|||||||
| 05 |
-- |
12 |
11 |
10 |
09 |
-- |
-- |
||||||||
| 06 |
-- |
-- |
16 |
15 |
14 |
13 |
-- |
-- |
|||||||
| 07 |
-- |
20 |
19 |
18 |
17 |
-- |
-- |
||||||||
| 08 |
-- |
-- |
24 |
23 |
22 |
21 |
-- |
-- |
|||||||
| 09 |
-- |
28 |
27 |
26 |
25 |
-- |
-- |
||||||||
| 10 |
-- |
-- |
32 |
31 |
30 |
29 |
-- |
-- |
|||||||
| 11 |
-- |
-- |
-- |
-- |
-- |
-- |
-- |
||||||||
| 12 |
-- |
-- |
-- |
-- |
-- |
-- |
-- |
-- |
|||||||
| 13 |
-- |
-- |
-- |
-- |
-- |
-- |
-- |
||||||||
| 14 |
-- |
-- |
-- |
-- |
-- |
-- |
-- |
-- |
The standardized 15 by 15 world view provided to each Bidder agent is based on the premise that "local" board positions are more important than those farther away from the piece. So search algorithms such as alpha-beta pruning would be of little benefit, since they examine all possible jumps and moves individually, not recurring patterns. However there are at least four evaluation mechanisms that could take advantage of this premise, and use the standardized world view to generate bids:
1. An Expert System
An automated "knowledge engineer" might be contructed, say in Prolog, that simply "watches" the world views while humans or other checkers-playing automata play actual games. The "knowledge engineer" program would look specifically for moves/jumps that led to losses, and abstract, from the board positions of the standardized world view, rules that would give lower bids to the "bad" moves in those situations.
Manually created expert systems that capture expert players' knowledge in the traditional way are of course also possible.
2. A Neural Network
A continuously learning neural network is easy to contruct and train, with a negative objective function of lost pieces. The input to the neural network would be the 15 by 15 array of positions (actually 112 "active" positions) before the move/jump, with appropriate values for vacant cells, cells occupied by single men and kings of each color, and "outside" cells, and whether the Bidder agent is front or rear. This is different from the traditional neural network approach which only evaluates the 8 by 8 board positions (actually, 32 "active" positions) of the checkerboard. One evolving neural net would be shared by both players. Such a neural net trained by the standardized world view would quite naturally begin to give higher weights to cells closer to the center, i.e. "local."
3. The Genetic Algorithm
Genetic Algorithm (Holland 1975) "genes" can be assigned to each of the six possible occupants of a cell (vacant, "outside", friend or opponent single man or king) for each "active" cell, plus one gene to encode front vs. rear agent and one gene for single man vs. king. The values of the genes would be summed to create a bid. White and black would each have different sets of genes in a game. The game losing player dies. The winner "mates" with other winners to generate new gene sets to replace the losers. The normal procedures for mutation, tourneys, etc. apply.
4. Genetic Programming
Genetic Programming (Koza 1992) is similar to the Genetic Algorithm (in terms of game winners and losers, mating and mutation) except that program instructions are the genotype, so for example sets of evolving LISP programs would compete to reproduce or die.
A combination of Genetic Programming and the Genetic Algorithm is also possible, with numerical "genes" being translated to Prolog rules, for example.
As is usual in these types of system, provisions will be made for a human (or other automated system) to "play" either white or black. A Graphical User Interface will also provide animation and debugging facilities.
Frey, Richard L. 1970. According to Hoyle, Greenwich, Conn.: Fawcett Publications.
Holland, John H. 1975. Adaptation in Natural and Atifical Systems, Ann Arbor, Mich.: University of Michigan Press.
Holland, John H. 1998. Emergence: from chaos to order, Reading, Mass.: Addison-Wesley.
Koza, John R. 1992. Genetic Programming, Cambridge, Mass.: MIT Press.
Samuel, A. L. 1959. "Some Studies in Machine Learning Using the Game of Checkers." In E. A. Feigenbaum and J. Feldman, eds., 1963, Computers and Thought. New York: McGraw-Hill.
Samuel's Checkers Player: www-anw.cs.umass.edu/~rich/book/11/node3.html
Artificial Intelligence and Games: www.brl.ntt.co.jp/people/kojima/links/ai-game.html
Chinook: www.cs.ualberta.ca/~chinook/
Search Results for +samuel +checkers player: search.excite.com/search.gw?FI_1=samuel&FL_1=1&FI_2=checkers+player&FE_2=1&FL_2=1&c=web&showSummary=true&mode=advanced
RCR