Home *Engines * CHUMP

CHUMP, (CHUnking of Moves and Patterns)
was an experimental chess program byFernand Gobet andPeter Jansen thatlearned torecognize piece patterns and associated move sequences, introduced at theAdvances in Computer Chess 7 conference in 1993. The aim was to model human 'computational' mechanisms, not only to understand better those machanisms in human beings, but to yield techniques and algorithms that could lead to valuable additions to competitive game playing programs, for instance in improvingmove ordering and in learning search control akaselectivity of classicalalpha-beta searchers^[1].

CHUMP is based onCHREST (Chunk Hierarchy and REtrieval STructures), a computer model of human chess memory and perception^[2]. CHREST was inspired by earlier programsMAPP^[3] andPerceiver^[4] byHerbert Simon and colleages. CHREST was not conceived as a component of a game playing program - its knowledge was limited to pattern of chess positions and had no concept of moves, goals and values. In learning about moves and when to make them, CHUMP was the first step towards a game playing,pattern learning chess program. In 1997,Fernand Gobet developed a second simulation of move-selection calledSEARCH, which begins to incorporatesearch processes^[5].

Structure of CHUMP

CHUMP consists of the following components:

1. Eye movement simulator module
2. EPAM like discrimination nets, one for piece patterns, one for move sequences
3. Short-term memory (STM)
4. Retrieval structure

Eye Movements

Theeye movement simulator is the only part of the system where the rules of the game influence the learning process. It scans the board, and directs its attention topieces andsquares it expects, given the current node in its discrimination net, attack, defense andproximity relations between pieces. It is hoped, that this leads to the formation of meaningful chunks.

Discrimination and Familiarization

The discrimination nets are based o theEPAM model of memory and perception, with some differences in the way uses recursion in encoding chunks and in the nature of the discrimination data structure - EPAM uses a tree, CHUMP a graph. Each node in the net contains the image of the object that lead to its creation, and a list of descendants. There are two different types of learning, depending on whether is new or not. If an objcet is new, that is does not match the image of the chunk found in the discrimination net, a new branch is created - dubbeddiscrimination. Otherwise, CHUMP extends the image - calledfamiliarization.

Short-term Memory

Short-term memory (STM) is a n-pointer structure (n ≡ 7 for human simulations), in which each pointer refers to a single piece pattern recognized in the position. In CHUMP, to obtain faster learning, an STM size of n = 20 was applied.

Retrieval Structure

The retrieval structure is an intermediate memory structure that, in humans, allows a rapid access tolong-term memory. In CHUMP. the retrieval structure consists of an internalboard representation - a representation augmented with information about lines, diagonals and directions of movement of the pieces - and the hypothesis - the most information-rich pattern recognized so far, linking for instance to relevant plans.

Learning

CHUMP builds its discrimination nets for pieces and moves based on the patterns it recognizes when scanning the set of training positions. For each position three learning steps take place.

1. The eye movement recognizes piece pattern, which are discriminated or familiarized inside the piece patterns net.
2. The move actually played is learned inside its move sequence discrimination net.
3. The current move (sequence) is associated with those piece patterns that contain the moving piece on its correctfrom square; a link is created between the piece pattern and the move entry in the move sequence discrimination net. If this move has already been associated with the same pattern earlier, its activation (a counter that keeps track of how often a particular move has been associated with a given pattern) is increased.

Move Proposal

After (or during) learning, CHUMP can use its discrimination nets to suggests moves in certain positions. Again, three steps were applied.

1. The eye movement simulator iterates over all relevant piece patterns.
2. The moves associated with every piece pattern are retrieved from the net, along with the number of chunks associating it and its activation.
3. The move with the greatest number of chunks is prefered, if equal, the move with higher activation is considered best

Experiments

CHUMP's proposed moves were compared with actual moves in several different learning and testing situations, e.g. games byMikhail Tal and positions from the KQKR domain. The experiments show that CHUMP improves performance with learning in all cases.

See also

• CHREST
• Chunker
• Chunking
• EPAM
• Eye Movements
• Learning Chess Programs
• MAPP
• Pattern Learning

Publications

• Fernand Gobet,Peter Jansen (1994).Towards a Chess Program Based on a Model of Human Memory.Advances in Computer Chess 7
• Roy W. Roring III (2008).Reviewing Expert Chess Performance: A Production-Based Theory of Chess Skill. Ph.D. thesis, advisorNeil Charness,Florida State University
• Andrew Cook (2008).Chunk Learning and Move Prompting: Making Moves in Chess. Technical Report CSR-08-12,University of Birmingham

External Links

Chess Program

• CHREST projects - CHUMP

Misc

• chump Wiktionary
• Chump from Wikipedia
• A Chump at Oxford from Wikipedia

References

Up one Level

• Acronym
• Experimental