229:
in the game tree. The vast majority of nodes are not transposition nodes, i.e. positions that will recur, so effective replacement strategies that retain potential transposition nodes and replace other nodes can result in significantly reduced tree size. Replacement is usually based on tree depth and aging: nodes higher in the tree (closer to the root) are favored, because the subtrees below them are larger and result in greater savings; and more recent nodes are favored because older nodes are no longer similar to the current position, so transpositions to them are less likely.
36:
179:
of each of the positions analyzed so far up to a certain depth. On encountering a new position, the program checks the table to see whether the position has already been analyzed; this can be done quickly, in amortized constant time. If so, the table contains the value that was previously assigned to
277:
Static bitmaps of the possible moves of each type of piece on each space of the board can be cached at program initialization, so that the legal moves of a piece (or together, all legal moves for move generation) can be retrieved with a single memory load instead of having to be serially enumerated.
240:
Though the fraction of nodes that will be transpositions is small, the game tree is an exponential structure, so caching a very small number of such nodes can make a significant difference. In chess, search time reductions of 0-50% in complex middle game positions and up to a factor of 5 in the end
228:
A transposition table is a cache whose maximum size is limited by available system memory, and it may overflow at any time. In fact, it is expected to overflow, and the number of positions cacheable at any time may be only a small fraction (even orders of magnitude smaller) than the number of nodes
191:
The computation saved by a transposition table lookup is not just the evaluation of a single position. Instead, the evaluation of an entire subtree is avoided. Thus, transposition table entries for nodes at a shallower depth in the game tree are more valuable (since the size of the subtree rooted at
124:
encoding the current board position as the hash index. The number of possible positions that may occur in a game tree is an exponential function of depth of search, and can be thousands to millions or even much greater. Transposition tables may therefore consume most of available system memory and
104:
is a cache of previously seen positions, and associated evaluations, in a game tree generated by a computer game playing program. If a position recurs via a different sequence of moves, the value of the position is retrieved from the table, avoiding re-searching the game tree below that position.
273:
and responses to other lines showing that they are inferior. Refutation tables were sometimes used instead of transposition tables in the earlier years of computer chess, when memory was more limited. Some modern chess programs use refutation tables in addition to transposition tables for move
183:
The number of positions searched by a computer often greatly exceeds the memory constraints of the system it runs on; thus not all positions can be stored. When the table fills up, less-used positions are removed to make room for new ones; this makes the transposition table a kind of
220:: given a position, it may not be possible to determine whether it has already occurred. A solution to the general problem is to store history information in each node of the transposition table, but this is inefficient and rarely done in practice.
203:
is used, the move that was found to be the best in a shallower search is a good approximation. Therefore this move is tried first. For storing the best child of a node, the entry corresponding to that node in the transposition table is used.
207:
Use of a transposition table can lead to incorrect results if the graph-history interaction problem is not studiously avoided. This problem arises in certain games because the history of a position may be important. For example, in
199:, the search is fastest (in fact, optimal) when the child of a node corresponding to the best move is always considered first. Of course, there is no way of knowing the best move beforehand, but when
212:
a player may not castle if the king or the rook to be castled with has moved during the course of the game. A common solution to this problem is to add the castling rights as part of the
258:
structures in a position. Since the number of pawn positions examined is generally much smaller than the total number of positions searched, the pawn hash table has a very high
141:, which means that they do not keep track of all the positions analyzed so far. In many games, it is possible to reach a given position in more than one way. These are called
328:
Atkin, L. and Slate, D., 1977, "Chess 4.5, the
Northwestern University Chess Program", in Chess Skill in Man and Machine, Peter W. Frey, Ed. Springer-Verlag, New York, NY
137:
Game-playing programs work by analyzing millions of positions that could arise in the next few moves of the game. Typically, these programs employ strategies resembling
65:
316:
232:
Other strategies are to retain nodes in the principal variation, nodes with larger subtrees regardless of depth in the tree, and nodes that caused cutoffs.
172:!). Although many of these are illegal move sequences, it is still likely that the program will end up analyzing the same position several times.
340:
200:
374:
87:
180:
this position; this value is used directly. If not, the value is computed, and the new position is entered into the hash table.
346:
109:(where the entire state of the game is known to all players at all times). The usage of transposition tables is essentially
192:
such a node is larger) and are therefore given more importance when the table fills up and some entries must be discarded.
48:
58:
52:
44:
69:
161:
106:
262:, allowing a program to spend more time on sophisticated pawn evaluations because they are reused many times.
379:
196:
195:
The hash table implementing the transposition table can have other uses than finding transpositions. In
142:
250:
Similar techniques can be used to cache evaluations of certain features of a position. For example, a
217:
270:
114:
164:) has 4 possible transpositions, since either player may swap their move order. In general, after
293:
138:
288:
259:
185:
269:
can be used to store sequences of moves from the root node to leaf nodes. This includes the
126:
298:
213:
358:
368:
352:
255:
110:
17:
176:
121:
27:
Cache of previously seen positions, and associated evaluations in a game tree
175:
To avoid this problem, transposition tables are used. Such a table is a
209:
146:
29:
168:
moves, an upper limit on the possible transpositions is (
349:(information on the data structure and implementation)
278:
These are commonly used in bitboard implementations.
120:Transposition tables are typically implemented as
57:but its sources remain unclear because it lacks
105:Transposition tables are primarily useful in
8:
113:applied to the tree search and is a form of
254:can be used to store an evaluation of the
88:Learn how and when to remove this message
319:, Gamedev.net, Francois-Dominic Laramee.
309:
347:Technical The Main Transposition Table
149:, for example, the sequence of moves
7:
355:T.A. Marsland, University of Alberta
25:
34:
1:
353:The anatomy of chess programs
375:Game artificial intelligence
396:
361:The Chess Programming Wiki
129:of game playing programs.
241:game have been reported.
107:perfect-information games
216:key. Another example is
162:algebraic chess notation
125:are usually most of the
43:This article includes a
72:more precise citations.
224:Replacement strategies
341:Transposition Tables
317:Transposition Tables
305:Notes and references
236:Size and performance
359:Transposition Table
271:principal variation
201:iterative deepening
115:dynamic programming
102:transposition table
294:Alpha-beta pruning
245:Related techniques
218:draw by repetition
197:alpha–beta pruning
139:depth-first search
45:list of references
289:Minimax algorithm
98:
97:
90:
16:(Redirected from
387:
329:
326:
320:
314:
267:refutation table
127:memory footprint
93:
86:
82:
79:
73:
68:this article by
59:inline citations
38:
37:
30:
21:
18:Refutation table
395:
394:
390:
389:
388:
386:
385:
384:
365:
364:
337:
332:
327:
323:
315:
311:
307:
299:Zobrist hashing
285:
252:pawn hash table
247:
238:
226:
214:Zobrist hashing
135:
94:
83:
77:
74:
63:
49:related reading
39:
35:
28:
23:
22:
15:
12:
11:
5:
393:
391:
383:
382:
380:Computer chess
377:
367:
366:
363:
362:
356:
350:
344:
343:Sigmachess.com
336:
335:External links
333:
331:
330:
321:
308:
306:
303:
302:
301:
296:
291:
284:
281:
280:
279:
275:
263:
246:
243:
237:
234:
225:
222:
143:transpositions
134:
131:
96:
95:
53:external links
42:
40:
33:
26:
24:
14:
13:
10:
9:
6:
4:
3:
2:
392:
381:
378:
376:
373:
372:
370:
360:
357:
354:
351:
348:
345:
342:
339:
338:
334:
325:
322:
318:
313:
310:
304:
300:
297:
295:
292:
290:
287:
286:
282:
276:
272:
268:
264:
261:
257:
253:
249:
248:
244:
242:
235:
233:
230:
223:
221:
219:
215:
211:
205:
202:
198:
193:
189:
187:
181:
178:
173:
171:
167:
163:
159:
157:
153:
148:
144:
140:
133:Functionality
132:
130:
128:
123:
118:
116:
112:
108:
103:
92:
89:
81:
78:November 2017
71:
67:
61:
60:
54:
50:
46:
41:
32:
31:
19:
324:
312:
266:
251:
239:
231:
227:
206:
194:
190:
182:
174:
169:
165:
155:
151:
150:
136:
119:
101:
99:
84:
75:
64:Please help
56:
122:hash tables
111:memoization
70:introducing
369:Categories
177:hash table
274:ordering.
283:See also
260:hit rate
154:d4 Nf6
66:improve
210:chess
186:cache
160:(see
158:c4 g6
147:chess
145:. In
51:, or
256:pawn
117:.
371::
265:A
188:.
156:2.
152:1.
100:A
55:,
47:,
170:n
166:n
91:)
85:(
80:)
76:(
62:.
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.