DCS

16 May 2017

Dynamic Move Tables and Long Branches with Backtracking
in Computer Chess
Kieran Greer, Distributed Computing Systems, Belfast, UK.
http://distributedcomputingsystems.co.uk
Version 1.2

Abstract—The idea of dynamic move chains has been described in a preceding paper [10]. Re -usi ng
an earlier piece of search allows the tree to be forward-pruned, which is known to be dangerous,
because it can potentially remove new information that would only be realised through a more
exhaustive search process. The justification is the integrity in the position and small changes
between positions make it more likely that an earlier result still applies. Larger problems where
exhaustive search is not possible would also like a method that can guess accurately. This pape r has
added to the forward-pruning technique by using ‘move tables’ that can act in the same way as
Transposition Tables, but for moves not positions. They use an efficient memory structure and have
put the design into the context of short or long-term memories. The long-term memory includes
simply rote-learning of other players’ games. The forward-pruning technique can also be fortified to
help to remove some potential errors. Another idea is ‘long branches’. This plays a short move
sequence, before returning to a full search at the resulting leaf nodes. Therefore, with some
configuration the dynamic tables can be reliably used and relatively independently of the posi ti on.
This has advanced some of the future work theory of the earlier paper, and made more explicit
where logical plans and more knowledge-based approaches might be applied. The author would
argue that the process is a very human approach to searching for chess moves.
Index Terms— Move table, dynamic move sequence, long branch, tree search, memory, knowledge.

1

Introduction

The idea of dynamic move chains has been described in a preceding paper [10]. It
incorporates the idea of forward-pruning the search tree, which is known to be dangerous,
because it can potentially remove new information that would only be realised through a
more exhaustive search process. If the decision is based on a lot of knowledge, then it might
be OK, but because computer chess programs are mainly statistical, they do not typically
contain enough knowledge about any single position or move, to make that assumption.
The amount of ‘knowledge’ that the chess program contains is still limited and so it must
evaluate many more positions to produce reliable results. Even if evolutionary methods or

1

DCS

16 May 2017

machine learning is used to improve the evaluations [9], the understanding level compared
to a human is still very shallow, although a recent program may be improving on this [14].
Therefore, if the knowledge is going to be limited, a similarly limited technique that can
forward prune would be useful. This paper suggests such a technique, where the
justification is the integrity in the position and small changes between positions make it
more likely that an earlier result still applies.

The intention of dynamic move chains is to store sequences of moves, rather than positions
with evaluations. The move sequences can then be tried in any relevant position, where the
fact that positions vary only slightly from one ply to the next is helpful. This means that a
move sequence that gets stored has a higher probability of being relevant to the next
position as well, and so on. If you like, the dynamic move sequence is more like a rule than a
statically learned position. The sequences are stored in lists called chains, that might spawn
tree-like structures, but in practice so far, are not very deep structures. Even if the first
move does not forward prune, any subsequent moves in the path would. The paths can also
be tried and replaced during a single search process, meaning that there is still a large
statistical element to it. The term ‘chain’ is used to try to distinguish from the more
common term ‘sequence’ that is also used in the paper.

The move chains cannot cycle, but the search process itself does cycle, again suggesting
repetition of the positions and subsequent best moves . As a move chain is created from a
cut-off sequence, it does represent the better moves in a position. It is however very
dynamic, constantly changing to the new circumstance that should also be the most
relevant. If thinking about the human process, then this type of immediate situation is
recognised, but we also store all of these situations into a longer-term memory that is builtup more slowly. When we are faced with an immediate situation again, we can still retrieve
from the long-term memory, helpful advice about what to do. It happens to be the case that
the move chains can be used to build up a type of longer-term memory for the computer
program as well. They can be stored in table structures, saved to a database, retrieved and
updated. The move paths can be of any length and the tables are indexed by moves and not
positions. This is possibly just completing the move chains idea that was reported previously
and can give the search process more reliability or stability when using forward-pruning. The
2

DCS

16 May 2017

long-term memory includes simply rote-learning of other players’ games. The forwardpruning technique can also be fortified to help with some potential errors. For example, a
minimum beam width can guarantee x dynamic moves are searched, broadening the
minimum search window. An idea of ‘long branches’ is also introduced. They forward prune
only part of the search, for a few ply, before returning to a full search at the resulting leaf
nodes. So, the search is full (broad) – pruned (narrow) – full again, and so on. Therefore,
with some configuration the dynamic tables can be reliably used and relatively
independently of the position.

The rest of the paper is structured as follows: section 2 notes some other chess heuristics
that would be related to the work. Section 3 gives a recap of the dynamic move chains,
while section 4 describes the new Move Tables idea. Section 5 describes how the forward
pruning technique can be incorporated into a full search process and section 6 gives some
test results from using the new algorithms. Section 7 gives a discussion, including where
more knowledge-based approaches might benefit from the new structure, while section 8
gives some conclusions on the work.

2

Related Work

This paper is a follow on from the earlier paper [10] that describes the new forward-pruning
method in detail. It therefore mostly extends the ideas of that paper to give more validity to
it. Related research would still be the original Chessmaps Heuristic paper [11], the Killer
Heuristic [13][3], Null-Move Heuristics [2][19], the History Heuristic or Transposition Tables
[16][17], or Monte Carlo search [6][20], for example. The Chessmaps Heuristic is the moveordering algorithm and its square control can also be used by the quiescence search. The
Killer Heuristic is another type of immediate result. It can store a killer or best move for each
level of the search tree, based on the idea that in many positions, the same move of the
opponent will be the best after ‘any’ move by oneself. This can be compared with the Move
Chains (section 3) that maybe store the best result for each legal move in the position, or
even a short path, but are immediately used and updated in a similar manner. Another
example of storing moves instead of positions is the Countermove Heuristic [18]. It is based

3

DCS

16 May 2017

on the observation that in many different positions a particular move is best responded to
by some particular opposing move. An economic storage structure can be used to store the
moves and also the counter moves. It was shown to reduce the search by as much as 20 –
50%. This could be compared with Move Tables (section 4), but they are used to continue
one’s own search and not to counter the opponent’s. They also introduce a new idea of
‘long branches’ and forward pruning that the older heuristics do not use. These new ideas
may also be more knowledge-based, generalising a strategy, while the other heuristics were
maybe more tactical. The History Heuristic uses a similar type of compact storage structure
to the Move Tables and Transposition Tables are a position-indexed version of the moveindexed Move Tables.

The Monte Carlo search [6] was recently used for the AlphaGo program [20] that defeated
the leading world Go player. It is also a selective search and judging from its recent results, it
looks to be one of the top methods at the moment. It selects which branches or lines of
play, to expand further through statistics, but still performs a full search over what it selects.
The advantage of the selective search is that it can deal with almost any problem, including
imperfect information and very large branching factors. It may require larg e search trees to
be effective, however and not being able to evaluate intermediate moves is at least a
restriction, but that can surely be changed. Null or Zero-Move heuristics [2][19] are
mentioned because they could be useful when trying to formulate plans. With these, a
player can make more than 1 move in a row, or the opponent makes a null move. If the free
move does not improve the position, then the position is not likely to change much. They
are not used in the current chess program, but if the program were to try to move pieces to
particular areas without considering too much every tactic in the position, then allowing
some free moves could become important.

As described in section 7.1, Botvinnik’s knowledge-based approach [4][5] might now be
relevant. Even though it was found to be insufficient at the time, some new ideas could
improve the research potential. With relation to writing a game-playing program, the
following blog [15] is interesting. It actually quantifies the reason why forward-pruning
should not work, which is helpful for making comparisons with. There are lots of other more
recent search algorithms and some have been written about in earlier papers, [10] for
4

DCS

16 May 2017

example. The strongly AI-based heuristics are often use to learn evaluation functions and
the Move Tables or Move Chains seem to have more in common with these earlier attempts
that relied on compact storage structures and reactionary or very basic updates, resulting
from reliable evaluations in the search process. The more knowledge-intensive processing
would be part of the next phase that builds on the information that the Move Tables
provide, see section 4. The ‘Method of Analogies’ [1] has been suggested and was
implemented as part of the Deep Blue program1 [12]. In the summary they state that:

‘… a game-playing algorithm often inspects the same thing many times over. A human, havi ng
studied a situation once, will in the future draw conclusions by the use of analogy. But, it often
happens that seemingly insignificant changes in the position alter the course of the game and
lead to substantially different outcomes.’

Therefore, specific features and knowledge are required to determine these differences.
Section 7 suggests some new techniques that might be tried, to generate some low-level
knowledge automatically, as with Botvinnik’s problem, although new research in [14] should
also be considered.

3

Dynamic Move Chains

A dynamic move chain [10] is a small move sequence generated from an earlier part of the
search. It can be significant because it resulted from a cut-off in the search process. A cut-off
is generated when the current evaluation refutes a particular position and means that
further search of the position is not required. A dynamic move chain might also occur when
the current best value is changed, as part of looping through the move list. When a
significant result is recognised, the current search path can be stored, with the intention of
re-using it later, to replace a full search. Even very small changes in a position however can
produce very different evaluations and so it is not possible to be 100% accurate based on
this type of move sequence alone. The move sequence must be played again and reevaluated in any position that it is applied to, but the fact that positions vary only slightly
from one ply to the next suggests that the move sequence can still be relevant. If it is found
1

Reviewer comment.

5

DCS

16 May 2017

to be unreliable, it can simply be replaced by a full search and so the statistic is a small
amount of forward pruning (with additional checks) with the risk of a full re-search, versus
an optimal full α-β search at every node.

An algorithm for the dynamic move chains is provided in [10] and so using dynamic move
tables also now needs to be integrated. The move chains are completely temporary and
more immediate. They are created and stored during the course of the game, but not saved
afterwards. The dynamic tables can store more aggregated information over the course of a
game and the results can be saved to files. For any future game, the tables can be read in
again, updated and re-saved, or whatever and so they can represent a very light form of
learning. This is all described in the next section.

4

Move Tables

As well as a full search, the computer program now uses three types of dynamic table. A
knowledge-based version is to store move sequences from game scores, probably
Grandmaster games. A short-term memory is the dynamic move chain that is constantly
changed and another type of long-term memory is the dynamic move table that is weighted.
The order for using these tables is as follows:

1. If there is a short-term dynamic move sequence then try it first.
2. If there is a long-term dynamic move sequence, then also try it.
3. Compare the two dynamic memory results for consistency and keep the better one.
4. If the dynamic memory is not satisfactory, then if the games database tables have any
entries, try them next.
5. If these all fail, then try a full search.

4.1

Game Scores

This was a surprising result. It could be thought that copying directly from existing games is
a waste of time because the search space of chess is so large. In fact, it is possible to read
game scores and store move sequences from them and re-use those sequences directly as
6

DCS

16 May 2017

part of a search. There is not much point storing sequences 1 ply deep as that can result
from a full search and so the decision was to store move sequences of 3 moves in length.
This is long enough to reduce the search size, but it can still be reinforced by a full and
subsequent quiescence search afterwards. When reading the player game scores, a move
sequence was added only if it occurred at least 3 times. Then it may have occurred in
different positions and may be related to a general rule or strategy about those positions.
These knowledge-based move sequences are therefore more like a strategy engine.

For the test program, a list of all World Championship games and some other Grandmasters
were read, resulting in just over 2.5 million positions. From that only 30,000 – 40,000
sequences of 3 moves were generated for each side and stored in files only 1-2 MB in size.
These sequences were then read into a dynamic move table at the start of the game. The
search would then check if any first move was in the table and try the move sequences if
any were legal. To reduce the number of sequences to consider, they would be ordered on
an average position evaluation. A weighted reinforcement value was also tried, but there
were more negative than positive updates and so the weight would not be useful for move
retrieval, and so the averaged evaluation was used instead. All of this is configurable
however. The full 3 move path would have to be played and it provided a surprisingly high
percentage of completions from when the first move was tried. The stored paths could
therefore be played in full more often than not, when the first move was legal. This suggests
that there is quite a lot of integrity in chess positions and it is not random. As we learn the
basic strategies and rules, the positions are determined by this and pieces are related to
each other through those strategies and rules. The positions all share similar features. The
piece positions and square control for the move sequences could also be stored and
summarised as game scores were read, but as yet, there is no way of turning that into useful
knowledge.

4.2

Dynamic Tables

One set of tables therefore comes from existing game scores. The other tables come from
the results of the game search. These include the dynamic move chains [10] and a more
permanent version of them, when 3-ply move sequences are transferred to another
7

DCS

16 May 2017

dynamic table structure. The move chains cover an immediate search and are not weighted.
If a cut-off occurs, it gets added as a move chain, or if a move chain gives a poor result, it
gets removed immediately. They are also allowed to be any length, including a single move.
This will still forward prune however, because the program still tries the move sequence
instead of a full search. They can also be updated more frequently, as part of the loop
through all legal moves in a position and can be compared to a short-term memory. Then a
second set of dynamic move tables can be considered to be a long-term memory that spans
the whole game and even across games. It may require longer move sequences – 3-ply for
example and would record an averaged result to compare against the immediate one of the
move chains. The averaged evaluation can also be used to order the sequences when there
are too many. The updating did not work well when it was part of the move list loop and so
it occurred only at the end of each node or position evaluation, using only the best path and
value from that node. Re-saving the tables in a database can store new knowledge each
time a game is played, but it did not result in very large table sizes. Each game might only
add a few KBs of moves to the database, for example, but it can also reduce in size.

4.3

Dynamic Table Structure

Move Tables perform a similar operation to Transposition Tables. There are lots of different
heuristics that can be used together in a program, and Move Tables and Transposition
Tables might both be used, but this program is only interested in testing the dynamic move
sequences ideas. They have been given the ‘Move’ title to distinguish indexing on moves
with indexing on positions. They have some advantages and some disadvantages over
Transposition Tables. For one thing, they can be encapsulated in an array that is the size of a
board. They can also be stored for each piece type, for both colours requiring a total of 12
tables, but this is still a relatively small amount of memory compared to Transposition
Tables. The enhancement of the table then, is paths of moves that grow from them and
would also link from one table to another one. Figure 1 is an example of what the move
tables might look like. The large squares represent the move tables for each piece type and
can literally be only 64 elements in size. They then also store any number of links between
themselves. The smaller squares represent the move sequence that has just been added,
resulting in incrementing those related weight values only.
8

DCS

16 May 2017

Figure 1. Example of Move Tables and Links between them.

Consider, for example, a cut-off that has resulted in a move sequence such as: WPe2-e4,
BPe7-e5, WNg1-f3: This would be stored as a move chain sequence and also used to update
the dynamic move tables. Both the ‘from’ and ‘to’ move squares can be updated, where the
related weight/evaluation value can be updated. If an evaluation is found to be unreliable
however, the table move sequence does not have to be removed immediately, but can have
a negative adjustment, until it is eventually removed. There can also be links between the
tables, where the move WPe2-e4 is stored in the e2 square that then links to Black’s Pawn’s
table, to the e7 square. That then links to White’s Knight’s table, to the g1 square, and so
on. Any move sequence that is returned can also be checked for legality in the position as
well as weight value. As typical optimised search can have a branching factor of only 6 and
the Move Tables might return more potential sequences than this and so they need to be
filtered again, to keep only the top ‘x’ number, as in a beam width. But this can be set to
anything and therefore tailored to the particular program that is using it. While the tables
are constantly updated, they still retain the information of the earlier searches.

9

DCS
4.4

16 May 2017
Best Squares and Important Squares

These move tables then produce a pattern of what the best moves for each piece type is,
see Figure 2 and Figure 3. This could be useful information as this type of view could help
with knowledge-based reasoning. It is also useful that it can be considered individually for
each piece. The Chessmaps program was built from the idea of square control [11], which is
central to generating the move ordering for the computer program. The new Move Tables
also generate this type of information for individual pieces and piece and control values can
be stored with any move sequence, but it is not currently used. As square control is part of
the Chessmaps heuristic however, it will always be available.

If trying to derive some form of knowledge from the move tables , possibly through a plan,
then looking at the best squares only might not be the most beneficial. Figure 2 shows the
Queen and Bishop move tables for the indicated position, with only the best and positive
weights displayed. It clearly agrees with that position, where the best moves for White
indicate to attack Black’s weakened King’s side. The weighted squares however, only relate
to two specific moves, where negative weight values are not displayed and this might make
the table a bit sparse. If there are several moves from a square, for example, then if one of
them is the best, the others will have their weight values decremented and might become
very small, or they might mutually decrement each other.

Figure 2. Queen and Bishop Move Tables for the shown position.

10

DCS

16 May 2017

In Figure 3 however, the accumulated weight values for all of the stored moves for the
White Queen are displayed. Note that the accumulated values have made every square
negative, apart from the squares with the value of 0. These are squares that no moves were
stored for, whereas, even if the values are negative, those squares have been very actively
considered and are therefore important. It is also interesting that the squares with the
largest negative values relate to the best move for the Queen as well, shown in Figure 2. So
there were many considerations around those squares and one idea might be to take the
absolute value of the accumulated weight values to represent a square’s ‘importance’ for a
piece and the best weight value(s) to represent the ‘best’ square(s). An important square
can then possibly be given priority as part of a plan, for example. To illustrate this, the
second diagram of Figure 3 has coloured in the table, using the absolute weight values only.
The most important squares are coloured red; then orange, yellow, green, light blue and
dark blue is the least important. The white squares should maybe not be considered at all.

Figure 3. Accumulated weight strengths and relative importance map.

5

Game-Playing Program and Search Algorithm

The Move Tables can be incorporated into the general search procedure and used to reduce
the search through a small amount of forward-pruning. They would typically be tried first,
but some other considerations are required. If they are not found to be reliable, then the
11

DCS

16 May 2017

full search can be tried. Each move in the position can be used as an index to a list of move
sequences in the tables. If the list is too long, then it would need to be filtered further. This
could be based on a weight, or an average evaluation, for example. A beam width can be
used to ensure that x move table paths are always played, even if an early one produces a
significant result. The tables also need a current result to compare with, to check that their
evaluations are accurate. The Chessmaps heuristic is able to recognise different types of
move that are as follows:
1.
2.
3.
4.

Safe capture moves, Safe forced moves, Safe forcing moves.
Safe other moves.
Unsafe capture moves, Unsafe forced moves, Unsafe forcing moves.
Unsafe other moves.

One division is to split the moves into safe and unsafe. Unsafe moves would lead to loss of
material on the square the piece is moved to, while safe moves would not. It is also possible
to recognise capture, forced and forcing moves. Forced moves would be ones where the
piece would have to move because it could be captured with a loss of material. Forcing
moves are moves that force the opponent to move a piece because it could then be
captured with a gain of material. Capture moves capture a piece and other moves move a
piece to an empty square, without an immediate threat. The forward-pruning techniques
have therefore been incorporated into the Chessmaps game-playing program [7] as follows:

1. Safe Forcing Moves: The first three categories, all safe capture, forced or forcing moves,
can always be played (list 1). So this is a type of quiescence search at the start, removing
these moves from the move list and gives a best value to compare with.
2. Dynamic Move Tables: Using this best value, take the list of ‘safe other’ moves (list 2) as
key values and retrieve moves from the tables in the order specified at the start of
section 4 – short-term, long-term, knowledge-base. This is where the search reduction
needs to be, as partial table searches have replaced full ones. So this is more strategic in
nature and does not make an immediate capture or threat.
3. All Other Moves: Any satisfactory replies from the tables are removed from the notsafe-forcing list (lists 2 to 4). For the remaining moves in the list, perform the standard
α-β full search. This includes the ‘safe other’ moves not used in 2 and any ‘not safe’
moves.
12

DCS

16 May 2017

The short-term memory (move chains) can play a path of any length, followed by at least 1ply full search and a quiescence search. The move tables of long-term memory or
knowledge-base, play paths of 3-ply, followed by at least 1-ply full search and quiescence
search. These paths are being called ‘long branches’ because they may not forward-prune
completely, but move the search on in specific areas. Other localised checks can be carried
out in a way that a human player might do things. If the full path is 3-ply, then after 2-ply,
perform a 1-ply full search plus quiescence from there as well. Compare the 2-ply path with
the intended 3-ply path for consistency and only accept the result if they are similar. So this
is a bit of backtracking that a human would easily use. ‘I know this variation, but I will check
for a different move first’, for example. There is still a substantial search saving. For
example, instead of a full search of (36x36x36) nodes, it could be ((1x36x36) + (1x1x36)) and
then those leaf nodes are also expanded.

As described at the start of section 4, each table result is compared with the other table
types, where similar paths in different tables should return similar results. So basically, an
unexpected result can force a re-search, but the process includes comparisons with a stable
material position and also comparisons between small variations in the searches. A research will still update the tables and make their evaluations more in line with the current
game. The dynamic tables for the long-term memory are therefore constantly updated
during the game and these changes are also saved to the database afterwards. Because only
positive evaluations are saved, the database is actually quite small. The knowledge-base
tables can also be updated during the game, but the changes should not be re-saved to the
database. So the knowledge-base is always read as it was originally, but new player games
can always be added to it. The current algorithm that is used is shown in Appendix A.

5.1

Summary of some Points

To summarise some of the main points: For the immediate or short-term move chains: they
get removed if they are unreliable, but they are immediately added and used if they return a
good score later on. For the long-term move tables: for each increment or decrement
update, the evaluation score is added to the stored move path. This is then averaged with
13

DCS

16 May 2017

all of the earlier scores and that is used as the general assessment for the move path. The
first evaluation can be as incorrect to the current position as a later one, for example. The
move paths are updated or stored if they produce a better alpha value or current value.
There can be a threshold where weight values below that are not considered, but the
selection of the paths should be done using the general evaluation result instead.

6

Testing

The tests are from two variations of the new move tables algorithm. The first version did not
include the knowledge-base tables and was also constructed differently to the new version
of this paper. For general search sizes and playing strength however, it is useful to include
the test results of the first version. The chess-playing program itself and the test program
are both written in the C# .Net language. With the older version, two types of test have
been carried out. The first is simply some 5-minute games against the standard Chessmaps
Heuristic, so show that using Move Tables with Dynamic Move Chains does not have a
detrimental effect in real play. For this, the number of table moves to search first was set to
a maximum of 4. A random opening for each game would be selected and there was also
iterative deepening with a minimal window. The new Dynamic Move Chains with Move
Tables performed well enough against the standard Chessmaps Heuristic with Transposition
Tables. In ten 5-minute games, it won 7-3.

6.1

Tests with the Older Algorithm

To see how adding the move tables changes the search size, tests adding 1, 2 and 4 moves
to the start of the Move Chains search process was measured. The paper [11] shows how
the forward pruning approach of using dynamic move chains by itself, can reduce the search
by as much as 99% more than a standard one and so there is a lot of scope for trying to
broaden the search process by adding extra knowledge or moves. Table 1 gives the results
of the relative search sizes for dynamic move chains with or without the additional move
tables. This was measured over a full game containing 98 separate positions to a depth of 5
ply. The results are for the negamax α-β search stage only and show the number of times

14

DCS

16 May 2017

the search size is less rather than the reduction percentage. Note that this result does not
measure move quality, only the search reduction.

Search Type

Move Chains

Move Chains + Move

Move Chains + Move

Move Chains + Move

tables (1 move)

tables (2 moves)

tables (4 moves)

Av Nodes

545

13367

12117

12550

Times less

23

1

1

1

Table 1. Search reduction for Move Chains, or MC plus Move Tables – 1, 2 or 4 moves.

It is interesting that adding 1 single additional move dramatically increases the search size
(98%), but adding more than 1 move does not have the same increase effect. So if using the
short-term Move Chains by itself, it searches in effect, an average branching factor of 3-4.
Then forcing at least 1 additional full-search move, increases this to 6-7, which is the
standard search size. Forcing more than 1 additional move does not have the same effect.
So further down the search, where all of the cut-off techniques are still used, the new
additions must be compensated in some way, possibly by adding accuracy to the move
ordering.

Another stat here suggests that move tables are used maybe only 30% of the time, as part
of the α-β search, or not used 70% of the time, when the dynamic cut-offs can still occur.
But this is for a new table from a single position. If it has built up a picture from earlier
searches during a game, then it would probably be used more than that.

6.2

Tests with the New Algorithm

The new algorithm has changed the way that the forward pruning is used and added some
new checks. It should be more reliable and does not appear to have increased the search
size by any great amount. The dynamic tables were only applied during the full α-β search,
not during the quiescence search and with the move keys being safe non-forcing, the tables
would build up a more strategic than tactical picture. Based on a small number of five 15
15

DCS

16 May 2017

minute games, a knowledge-based path would be attempted maybe 5-10% of all positions,
but this is for relatively small tables, as described in section 4.1. Of the number started
however, the 3-ply path could be legal 60-70% of the time. Of that, a better move might not
be recorded more than 5% of the time. The dynamic table paths would also complete a high
percentage of times, but not be used as often as the knowledge-base. The percentage of
better results would also be lower, but that does not mean a poorer evaluation was not
included in the general search. So contrary to the integrity argument, if moves then change
the position, remove pieces and so on, would that make the dynamic memory tables slightly
out of sync? In a 15 minute game, the program would rarely exceed a depth of 5 ply for the
α-β search, which is nothing compared to the better chess programs . Obvious blunders are
not apparent in any recent games and the new algorithm has a slightly stronger playing
strength to the older one.

7

Discussion

Move Tables are similar to Transposition Tables, except that they store move sequences and
not position evaluations. They might be thought of as completing the solution to using Move
Chains, suggested in [10]. They can be used in any position where it is legal and reduce the
search through forward pruning. As written about in the earlier paper, the advantage of
storing a move is that it is position independent and can therefore be tried in any legal
situation. For chess, the branching factor is still quite small, but for larger games or
problems, the database size for a transposition table might simply become too large. The
knowledge that is added is still statistical in nature. There is no understanding of why a
move sequence is good, only that the statistical evaluation of it was good. The earlier paper
[10] also suggested future work that can be tried, along the lines of adding more knowledge
and some form of narrow evolutionary search. This even went back to the very beginning
and the knowledge-based feature extraction processes. Move Tables does not solve that
problem specifically, but it does provide some automatic processes that can realistically be
used to help with the knowledge-based approach. Reading player game scores and storing
common move sequences in them is a direct realisation of a more knowledge-based
approach. It was surprising how many of those move sequences were legal in arbitrary

16

DCS

16 May 2017

games, which highlights how much chess is controlled by specific rules and strategies. The
search process is also configurable and flexible. It would be possible, for example, to
retrieve any number of moves from the tables, depending on the allowed search size.

Storing those move sequences also stored common features in the positions that could be
aggregated. However, it is still not clear how the computer could use the aggregated
information. It can be told, for example, that a particular move sequence happens when
there are two pawns somewhere and a piece somewhere else, but it will not have any
understanding of why that may be, or how to use those piece positions in a different
situation. The closest match to human understanding might be if the pieces are objec ts in
the environment and the move is some type of action. Then a basic summary of the
environment can suggest a type of action, for example, there are two enemy soldiers and a
gun, along with a number of other features, so try to get the gun. The earlier paper also
wrote about tactical chunks, instead of the more common knowledge-based ones [8]. If
there are weight concentrations in a move table, then the related position could be looked
at to see what pieces or piece formations were present. Or if two or more move tables
intersect somewhere, it might represent an important board feature. This could simply be
used to re-order all moves to that particular area, or it might help with creating these
knowledge or tactical chunks. The chunks however would then need to be made part of a
plan and not one that the search process would naturally choose. It would need to change
the natural search process in some way, maybe by re-ordering moves. However, if it is
automatically created, then it is more in sync with the evaluation function that created it,
rather than an expert saying one thing and the computer program saying another thing. An
idea here might be an intersection of the evaluation function features and the aggregated
position features. The ideas of Botvinnik may become relevant as well, see the next section.
For example, the computer can devise plans for both sides based on advantageous features,
determined automatically. Pieces are then moved to each side’s better area, so use a very
directed search and not any plan. It can then evaluate the resulting position to determine
which plan is better, if attack or defence is required, and so on. This would set some quite
human-oriented goals.

17

DCS
7.1

16 May 2017
Botvinnik’s Computer Chess Theory

The former World Champion Botvinnik wrote a computer chess book [5] and program
(Pioneer) when the chess programs were built on the theories of logic and knowledge. As
computer speeds improved, the statistical brute-force approaches took over and are now
standard. The expert logician suggested in his book, to measure how many moves it might
take for a piece to move from where it is to where it should be. This requires specific
knowledge about the position, but is a bit like narrow sequences that need to be
incorporated into a main search process. This more specific knowledge represents a
particular plan in the position, but as current programs lack that level of knowledge, a
simpler plan devised from more low-level knowledge would be a start. Looking at the
patterns in each move table shows the squares that the search process has evaluated as
important for each piece. Therefore, some counting measure of how to move between
them could be considered, in what would be a more logical and knowledge-based approach.
The chess program is also described in [4], where the following quote from ‘The Tale of a
Small Tree’ chapter sums up some of the relevant philosophy:

‘Thus, during a game a player analyses the movements of a limited number of pieces on a
limited part of the board, and analyses the movements of only those pieces which come
directly into collision, and only on those squares where collisions are possible. In other wor ds,
he examines only those pieces which interact with the enemy pieces, and only those square s
where this interaction is possible. But how can one check that these pieces and these square s
have been correctly chosen? …’

So the move tables can maybe produce a map that can be combined or compared and show
more easily what the squares or pieces might be. While a human player can simply see that,
it might not be as obvious to the chess computer program. So some more elements could be
in place for the knowledge-based approach now, but it is also clear that a lot more work is
still required.

18

DCS

8

16 May 2017

Conclusions

This paper has added to the forward-pruning technique of Dynamic Move Chains, through
the use of Move Tables that can act in the same way as Transposition Tables, but for moves
not positions. They use an efficient memory structure and have put the design into the
context of short or long-term memories. The dynamic move chains cause an immediate
reaction, whereas the move tables build up more slowly. So there are different views of the
same knowledge – one is immediate and one is more aggregated. A third version of the
same technique can read existing games and store move paths that are common in them. It
can also store additional information such as aggregated position features, for example. The
search process then has some flexibility in when to use each type of knowledge and how
much to use. The tables can even be saved to a database and read in again for the next
game. These tables have advanced some of the future work theory of the earlier paper [10]
and made more explicit where logical plans or more knowledge-based approaches might be
tried. It is also likely that successful results would be transferrable to other types of game or
problem, when some level of estimation is required. The main improvement in this paper is
the sorting of the different techniques and using them with the more ordering of the
Chessmaps heuristic, to produce something that should be reliable. This is demonstrated in
the game-playing program [7], although the version of this paper is not currently published.
However, forward-pruning will always remove moves and so a question still remains if the
new research has moved the problem from playing a blunder instead of a reliable move, to
playing a reliable move instead of a brilliant one. Appendix B lists a game with the new
version of this paper against the currently published program (older algorithm). The control
of the winning side (this paper) is impressive.

9

References

[1] Adelson-Velsky, G., Arlazarov, V. and Donskoy, M. (1988). Algorithms for Games, Springer.
[2] Adelson-Velskiy, G.M., Arlazarov, V.L., & Donskoy, M.V. (1975). Some methods of controlling the
tree search in chess programs. Artificial Intelligence, Vol. 6, No. 4, pp. 361 - 371.
[3] Birmingham, J. and Kent, P. (1977). Tree searching and tree pruning techniques, Advances in
Computer Chess, Edinburgh University Press, Ed. Clarke, M.R.B., pp. 89-107.

19

DCS

16 May 2017

[4] Botvinnik, M.M. (1981). Selected Games 1967 – 1970, Pergamon Russian Chess Series, Pergamon
Press, translated by K.P.Neat.
[5] Botvinnik, M.M. (1970). Computers, Chess, and long range planning, New York: Springer-Verlag.
[6] Browne, C., Powley, E., Whitehouse, D., Lucas, S., Cowling, P., Rohlfshagen, P., Tavener, S., Perez,
D., Samothrakis, S. and Colton, S. (2012). A Survey of Monte Carlo Tree Search Methods, IEEE
Transactions on Computational Intelligence and AI in Games, Vol. 4, No. 1, pp. 1 - 49.
[7] Chessmaps program, http://distributedcomputingsystems.co.uk/gameplaying.html. (last
accessed 30/6/17).
[8] Fürnkranz, J., (1995). Machine Learning in Computer Chess: The Next Generation, ICCA Journal,
Vol. 19, No. 3, pp. 147-161.
[9] Fürnkranz, J. (2007). Recent advances in machine learning and game playing. OGAI Journal , Vol.
26, No. 2. Special Issue on Computer Game Playing.
[10]Greer, K. (2013). Tree Pruning for New Search Techniques in Computer Games, Advances in
Artificial Intelligence, Vol. 2013, Article ID 357068, 9 pages. doi:10.1155/2013/357068, Hindawi.
[11]Greer, K., (2000). Computer Chess Move Ordering Schemes Using Move Influence, Artificial
Intelligence Journal, Vol. 120, No. 2, July, pp. 235-250.
[12]Hsu, F. (2002). Behind Deep Blue: Building the Computer that Defeated the World Chess
Champion. Princeton University Press. ISBN 0-691-09065-3.
[13]Huberman, B.J. (1968). A Program to Play Chess End Games, Technical Report, No. CS-106, Ph.D.
Thesis, Stanford University, Computer Science Department.
[14]Lai, M. (2015). Giraffe: Using Deep Reinforcement Learning to Play Chess. M.Sc. thesis, Impe rial
College London, arXiv:1509.01549v1.
[15]Laramee,

F.D.

(2000).

Chess

Programming

Part

III:

Move

Generation,

http://www.gamedev.net/page/resources/_/technical/artificial -intelligence/chessprogramming-part-iii-move-generation-r1126. (last accessed 30/6/15).
[16]Schaeffer J., (1989). The History Heuristic and other Alpha-Beta Search enhancements in
Practice, IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 11, No. 11.
[17]Schaeffer J., and Plaat A., (1996). New Advances in Alpha-Beta Searching, Proceedings of the
25th Computer Science Conference.
[18]Uiterwijk, J.W.H.M. (1992). The Countermove Heuristic, ICCA Journal, Vol. 15, pp. 8 – 15, ISSN
0920-234X.
[19]Winands, M.H., Van den Herik, H.J., Uiterwijk, J.W. and Van der Werf, E.C. (2005). Enhanced
forward pruning. Information Sciences, Vol. 175, No. 4, pp. 315-329.

20

DCS
[20]Yustalim,

16 May 2017
W.

(2017).

Application

of

Monte

Carlo

Search

Tree

in

AlphaGo,

http://informatika.stei.itb.ac.id/~rinaldi.munir/Matdis/2016-2017/Makalah2016/MakalahMatdis-2016-010.pdf.

21

DCS

16 May 2017

Appendix A – Search Algorithm
If (depth == max_depth)
{
return quiescence_search(…)
}
else
{
moveList = generateMoves();
safeForcing = getSafeForcingMoves();
safeOther = getSafeOtherMoves();
notSafeForcing = getNotSafeForcingMoves();
for each move in safeForcing
{
Play the move and then a full search plus quiescence to required depth
set best path and value from this
}
for each move in safeOther
{
retrieve from short-term memory move chain, any path stored under the key
if path exists play and evaluate with at least 1-ply full search and quiescence at end
retrieve from long-term memory tables, any paths stored under the key
for each path
{
play and evaluate with at least 1-ply full search and quiescence at end
store the path and value that is best
}
If (st and lt similar) keep long or short-term, whichever is better
If (memory value not better than best)
{
retrieve from knowledge-base tables, any paths stored under the key
for each path
{
play and evaluate with at least 1-ply full search and quiescence at end
store the path and value that is best
}
}
If (dynamic tables move OK)
{
remove the move from notSafeForcing
check if best reply is better than current best
set best value and path if better
update move chains with the result
}
}
for each remaining move in notSafeForcing
{
play and evaluate with a full search and quiescence
store the path and value that is best
if (better than current best)
{
store best value and path
update move chains to use the current best path for the selected key
}
}
at end of node search there is a best path and value for the node
update the long-term tables and knowledge-base using this value
}

22

DCS

16 May 2017

Appendix B – Example Game
His is an example game of the new search algorithm of this paper, against the earlier version
that uses move chains only and not the move tables. It demonstrates an impressive level of
control, even if forward-pruning techniques are being used. 15 minutes each with the first 6
moves being opening theory.

Old Algorithm New Algorithm
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.

e4
Nf3
d4
Nxd4
Nc3
g4
Nxc6
Be2
exd5
O-O
Na4
g5

c5
d6
cxd4
Nf6
e6
Nc6
bxc6
d5
exd5
Bc5
Bd6
Ne4

13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.

f4
c4
cxd5
Kxf1
dxc6
Bxd1
Be3
h4
Kf2
Kf3
Kg2
Kxh1

O-O
Bh3
Bxf1
Bc7
Qxd1
Rad8
Rfe8
Ng3
Nh1
Rd3
Rexe3
Re1
0-1

23

