This text is provided in the hope that it is usefull and informative. No garantees can be given that any of it is actually correct. Code is available but not intended to be user-friendly in any way and is not documented.

Automated learning of tactical patterns in draughts

Introduction

Human players of draughts are experts in reconizing patterns and learning new patterns. In many games each score associated with a pattern can be learned trough experience, with backgammon and othello as the most obvious examples. However, computer programms usually have a hard time learning from experience and new patterns usually are hard-coded into a program. On this page I shall describe an algorithm to learn new patterns. I think the algorithm is very similar to Stef Keetman's, but I have never seen his essay on the subject.

Defining patterns

The algorithm is based on the feature of draughts that capture moves are forced; if a capture is offered to the opponent, he has usually very few available moves. The objective of the algorithm is to find patterns, in which it is possible to get a better position by forcing the moves of the opponent. An Example position:
In this position white can win two man by:
1. 28-23  19x28
2. 29-24  20x29
3. 34x21  16x27
4. 31x33
White can still make this combination if he does not have a man at field 50, because this stone does not in any way contribute to the combination. In fact there are more man that are irrelevant to the combination.I determen the relevance of a field by carefully examining the pieces that are involved in the combination, but other methods are possible. Here all irrelevant fields are marked with a green dot:
Ofcourse there are exceptions, such as putting a crown somewhere on the board will have some effects, so it is not garanteed to work every time. This is not important if failure happens only infrequently. So we now have a template that can be used in many positions.

Finding new patterns

I have searched for patterns in two ways: in the first place from draughts-problems. However, there are many more templates than I have problems, so the second way is to use professional games. Positions from professional games very rarely have tactical wins, so a 1 or 2 ply tree is generated from each 'professional position'. For each resulting position it is checked if there is a forced win.

Using templates

For each position that is evaluated, it is checked if the position matches that of a previously found template. If it does, the corresponding moves are tried out. If the moves are not legal, the template is rejected. If the moves do not lead to a win, the template is rejected. If it does lead to a win, the position's evaluation is feeded back into the normal alpha-beta search. Often this results in a immidiate beta-cut. Rejections and acceptions are logged for each template. After a while, templates that are rejected too often are removed from memory.

Fast indentification of templates

The above method generates thousands of patterns and checking them all in every leaf-node is extremely slow. The solution to this is generating a decision tree; We begin with the complete set of templates. Now we ask the set a question like 'is there a white man on field 23?'. The tree now branches into YES and NO. Some templates will move into the NO branch, some into the YES branch. Others allow the answer to be both NO or YES, if the field 23 is irrelevant. The question that achieves the two best seperation between the sets is selected as THE question. The procedure is repeated recursevely until no more meaningfull questions can be asked. Usually there is only 1 template left, but there may be more.

The trees generated this way are pretty big, at about 0.06 T^2 (T=number of templates), and generating them is very time consuming. In the real search, the tree can be traversed very quicky. Sometimes this leads to a number of templates, which are than checked if a win can be achieved.

Discussion

About 1 to 4 percent of the leaf nodes (after quiesence search) in DragonDraughts are positions that allow a tactical combination. Using the patterns allow these patterns to be correctly indentified as wins, by extending the search by a few ply in a very selective matter.
Main Draughts page
Copyright ,