5
Search Algorithms for a Bridge Double Dummy Solver
7
This description is intended for anyone interested in the inner workings of a bridge double dummy solver (DDS). It describes my solver implemented in the Win32 environment as a DLL.
9
DDS algorithm descriptions already exist, see reference list at the end. However, to my knowledge, no document exists that gives an in depth description of all algorithms covered in this document.
14
1.The basic search algorithm
16
The search is based on the zero window search [Pearl 1980].
17
Pseudo code for its application on DD solver search is given.
18
Cards searched are described as ”moves” in contrast to cards that are really played.
20
int Search(posPoint, target, depth) {
31
if (player_side_to_move) {
32
value=FALSE; moveExists=TRUE;
35
value=Search(posPoint, target, depth-1);
38
goto searchExit; /* Cutoff, current move recorded as ”best move” */
41
} /* Opponents to move */
43
value=TRUE; moveExists=TRUE;
46
value=Search(posPoint, target, depth-1);
49
goto searchExit; /* Cutoff, current move recorded as ”best move” */
60
The Search parameters are:
61
posPoint - a pointer to a structure containing state information for the position (deal) to be searched, e.g. leading hand, hand-to-play, cards yet to play etc.
62
target - the number of tricks the player must take.
63
depth - the current search depth.
65
Search returns TRUE if the target is reached, otherwise FALSE.
67
When Search is called, depth is set to the number of cards left to play minus 4.
68
GenerateMoves generates a list of alternative moves (=cards) that can be played in the initial position whose state data is pointed to by posPoint. For cards that are equivalent (e.g. AK) only the card with highest rank is generated. Card equivalence is reanalyzed after each trick.
69
E.g. if the hand-to-play has AQ in a suit where K was played in a previous trick, then A and Q become equivalents.
71
If the side of the player has the move, Search tries to find a move that meets the target, i.e that evaluates to TRUE. If such a move is found, search returns TRUE, and saves the move as ”best”.
72
If the other side has the move, Search tries to find a move that defies meeting the target, i.e. that evaluates to FALSE. If such a move is found, search returns FALSE, and saves the move as ”best”.
74
Each move in the generated move list is handled by first calling Make, which removes the card from the position state information. Search is then recursively called with a position state that now has excluded the played card, depth has been decremented by one. For each new recursive call to Search, a card is removed from the position state information and depth is decremented. This goes on until depth equals 0 in which case only one trick remains. The outcome of this trick is calculated by Evaluate. If the total number of tricks won by the side of the player then reaches target, Search returns TRUE, otherwise FALSE. This result propagates upwards as Search returns for each level, Undo is called which reinstalls the searched card on this level.
75
Finally, Search returns for the top level.
77
This basic search algorithm is not powerful enough to terminate the search of a typical 52 cards deal in a reasonable time. To accomplish this, a number of search algorithm enhancements are required, which will be described in the following chapters.
79
The described search algorithm only tells if a predefined target can be reached. It does not tell how many tricks that the side of the player can get. This is accomplished by repeated calls to Search:
81
g = guessed number of tricks for side of the player
82
iniDepth = number of cards to play minus 4
90
if ((Search(posPoint, tricks, iniDepth)==FALSE) {
99
while (lowerbound < upperbound);
100
g=maximum tricks to be won by side of player.
104
2.Overview of the search algorithms used in the DD solver
106
The additional functions in the pseudo code for supporting the search speed enhancements are given in italics.
108
int Search(posPoint, target, depth) {
109
if (no_move_yet_in_trick) {
111
if (target_already_obtained)
113
else if (target_can_no_longer_be_obtained)
117
if (cutoff_for_player_side)
119
else if (cutoff_for_opponent_side)
122
if (transposition_table_entry_match) {
132
if (evalRes.tricks >= target)
141
CheckMovesForCutoff; /* For pseudo-code, see chapter 6 */
142
if (player_side_to_move) {
143
value=FALSE; moveExists=TRUE;
146
value=Search(posPoint, target, depth-1);
150
goto searchExit; /* Cutoff, current move recorded as ”best move” */
155
} /* Opponents to move */
157
value=TRUE; moveExists=TRUE;
160
value=Search(posPoint, target, depth-1);
164
goto searchExit; /* Cutoff, current move recorded as ”best move” */
177
TargetTooLowOrHigh checks the target value against the number of tricks currently won by side of the player and against number of tricks left to play.
178
It is executed at the beginning of each trick, before any card has been played.
179
If number of currently won tricks by player’s side equals or exceeds target, Search returns TRUE.
180
If number of currently won tricks by player’s side plus tricks left to play is less than target Search returns FALSE.
181
Since possible winning cards for the remaining tricks are irrelevant, no winning cards are backed up at cutoff termination.
183
TargetTooLowOrHigh search enhancement is described e.g. in [Chang].
185
QuickTricks determines if the side to move can take one or more sure tricks. E.g. if the hand to move has an Ace in an NT contract, at least one sure trick can be taken.
186
It is executed at the beginning of each trick, before any card has been played. A simple quick trick is also executed after the leading card of the trick is played.
187
Assuming that the sure tricks are won by the side to move, then the conditions for search cutoff in TargetTooLowOrHigh are again tested to produce further search cutoffs.
188
The detailed conditions for determination of sure tricks are described in Chapter 3.
189
When quicktricks win by rank, they are backed up at cutoff termination.
191
The idea of QuickTricks is described e.g. in [Chang].
193
LaterTricks determines if the opponents of the side to move can take one or more tricks at their turn or later in the play. It is also executed at the beginning of each trick and uses similar criteria for search cutoff as Quicktricks.
194
When quicktricks win by rank, they are backed up at cutoff termination.
195
For a detailed description, see Chapter 4.
197
RetrieveTTresult scans the set of positions in the transposition table to see if there is a match against the current position.
198
It is executed at the beginning of each trick, before any card has been played. After detection of a transposition table entry match, the winning ranks necessary in the remaining cards are backed up.
199
For details, see Chapter 7.
201
Evaluate returns evalResult which updates the position state information. evalResult contains:
202
evalResult.tricks, the number of tricks won by the side of the player, and
203
evalResult.winRank which includes the card in the last trick that won by rank.
204
E.g. if the last trick includes the spades A, Q, 9 and 3, evalResult.winRank returns spade A. But
205
if the last trick was won without a win by rank as for spade 5 (leading and winning card), heart A, heart Q, heart 5, no winning rank is returned.
207
Keeping record of cards that win by ranks and subsequently using this information to ignore ranks for other cards is discussed in the Partition Search concept invented by Matthew Ginsberg and described in his paper [Ginsberg].
209
MoveOrdering. The alternative cards created by MoveGenerate are sorted, with the cards most likely to terminate the search fastest being sorted first in the move list.The allocation of card weights are described in detail in Chapter 5.
211
CheckMovesForCutoff checks if any of the moves just generated will lead to a position that can be found in the transposition table. If so, an immediate Search return can be done, saving unnecessary search effort. This is further described in Chapter 6.
213
To my knowledge this is not described anywhere for usage in a DDS. It is described in [Plaat et al.] and named Enhanced Transposition Cutoffs.
215
At move search cutoff, MergeMoveData collects the union of the backed up accumulated winning ranks and the rank of the made move, assuming it did win by rank. The state data of the position is updated with the collected information.
217
MergeAllMovesData collects the union of the backed up accumulated winning ranks, the previous accumulated winning ranks of the alternative moves generated on this depth, and the rank of the made move, assuming it did win by rank. When all alternative moves have been searched without a cutoff, the state data of the position is updated with the collected information.
219
The information from MergeMoveData and MergeAllMovesData is later stored in the transposition table and determines which ranks that are essential when RetrieveTTresult scans the set of positions in the transposition table. A match of ranks with the current position is only needed for winning ranks. See Chapter 7.
221
AddNewTTentry adds the evaluated position as a new entry in the transposition table. See Chapter 7.
223
NextMove filters out all ”small” cards except one per hand/suit combination. A ”small” card is a backed up card that is shown to never win by rank. The rest of the ”small” card moves for the hand/suit combination are never searched, leading to a smaller search tree.
224
This search enhancement was suggested by Hans Kuijf [Kuijf].
228
3.The Quick Tricks cutoff algorithm
230
The number of tricks that can immediately be taken by the side to play the leading card of the trick consists of:
231
a)The number of tricks that can be taken by the hand-to-play, and
232
b)The number of tricks that can be taken by the partner of the hand-to-play
233
At return by QuickTricks, the position state information is updated with the winning ranks found.
235
Of course, in order to add b), there must be an entry from the hand-to-play to the partner’s hand.
237
For each ”s” (suit) the following is calculated:
239
If the hand-to-play is the only hand having cards in s, and the opponents have no trumps (when s is not trumps), the number of quick tricks for s is the suit length of the hand-to-play.
241
If the opponents have no trumps, a check is made to see if quick tricks equal to the maximum of the trumps length for leading hand and the partner causes a search cutoff.
243
If the hand-to-play has a card in a suit where the partner has a winning rank, and partner is the only hand having cards in s:
244
The number of quick tricks for s is the suit length of partner.
247
If the winning rank is in hand-to-play, and the opponents cannot ruff, the number of quick tricks is incremented by one. Further, if the second best rank is also in hand-to-play, and the opponents cannot still ruff, the quick tricks is again incremented by one.
250
If the winning rank is in partner and partner has winning rank as entry, the same applies for the partner as for the hand-to-play described above.
252
If it is a trump contract, the first suit to be investigated is the trump suit. Then if there are trump suit quick tricks for the side to play, those are cashed and quick tricks incremented accordingly.
254
When the other suits are investigated for quick tricks, only the remaining opponent trump cards need to be considered.
256
The quick tricks are then summarized from each suit, and the total calculated.
258
A simple Quick Tricks algorithm is also executed after the leading card of the trick has been played:
260
A quick trick is gained either if the hand-to-play or the partner can win the current trick with the card having the highest rank of the suit played, or if hand-to-play or the partner can win the trick by ruffing.
262
The idea to also execute Quick Tricks after the leading card has been played was given by Hans Kuijf [Kuijf].
266
4.The Later Tricks cutoff algorithm
268
Check for search cutoff if the opponents to the trick leading hand have at least a sure trick later.
270
If not trump contract:
272
1)The opponents have at least a sure trick if for all suits where the trick leading hand has a card, the side of the leading hand does not have the highest rank.
273
More than one sure trick can be taken by the opponents if they possess the winning rank for more than one suit, or
275
2)Assume that all suits where the side of the trick leading hand has the winning rank give maximum possible number of tricks, i.e. that the sure trick number is the sum of the
276
maximum lengths of these suits.
277
If this still cannot cause a cutoff for the trick leading side, allocate one sure trick for the opponents side.
281
Quick tricks for the opponents of the leading hand are added when the opponents have one or more winning trumps. This idea was given by Pedja Stanojevic [Stanojevic].
283
1) If the opponent side have all the trumps, the number of sure tricks is the maximum suit length
286
2) If the opponent side has the highest trump, they have 1 sure trick. If they also have the second
287
highest trump, they have 2 sure tricks, or
289
3) If the opponent side has the second highest trump plus at least one trump more behind the
290
hand with the highest trump, the opponent side has 1 sure trick.
292
5.The Move Ordering algorithm
294
The weight of a card in the move list is affected by the suit and the rank of the card and by the other cards in the same trick.
295
The weights of the cards in the move list are used to sort them, with the cards having the highest weight being sorted first in the list.
297
If the hand-to-play is trick leading hand or void in the suit played by leading hand, the card with the highest weight for each present suit will get a high additional bonus weight. After list resorting, those cards will occupy the first positions in the move list.
299
A "best move" is maintained for each searched depth. At a search (alpha-beta) cutoff, the move causing the cutoff overwrites the present "best move" for the current depth. When a Transposition Table entry is created, the current best move is stored in that entry if:
300
The target is met and the leading hand belongs to the player’s side, or target is not met and the leading hand belongs to the other side. Otherwise the best move is not stored in the Transposition Table entry.
301
At a Transposition Table entry match, its stored best move will be best move for the current search depth.
303
By ”card move” in the following pseudo code is meant the card by the hand-to-play that is getting a weight in the move list. The ”card rank” is a value in the range 2-14, corresponding to the card ranks 2 to the Ace.
305
For the determination of the weight, it is calculated whether or not the current card move is a card that wins the current trick for the side of the hand-to-play, assuming that both sides play their optimum cards.
308
Hand-to-play is trick leading hand
310
The contribution of the suit to the weight:
312
suitWeightDelta = suitBonus - (countLH+countRH) * 2
314
If trump contract, and the suit is not trump, then there is a (negative) suitBonus of –12 if
315
LHO is void and LHO has trump card(s), or
316
RHO is void and RHO has trump card(s)
318
Otherwise, suitBonus = 0.
320
countLH = (suit length of LHO) * 4, if LHO is not void in the suit,
321
countLH = (depth + 4), if LHO is void in the suit
323
countRH = (suit length of RHO) * 4, if RHO is not void in the suit,
324
countRH = (depth + 4), if RHO is void in the suit
326
Suits are thus favoured where the opponents have as few move alternatives as possible.
329
if (trick winning card move) {
330
if (one of the opponents has a singleton highest rank in the suit)
331
weight = suitWeightDelta + 40 – (rank of card move)
332
else if (hand-to-play has highest rank in suit) {
333
if (partner has second highest rank in suit)
334
weight = suitWeightDelta + 50 – (rank of card move)
335
else if (the card move is the card with highest rank in the suit)
336
weight = suitWeightDelta + 31
338
weight = suitWeightDelta + 19 – (rank of card move)
340
else if (partner has highest rank in suit) {
341
if (hand-to-play has second highest rank in suit)
342
weight = suitWeightDelta + 50 – (rank of card move)
344
weight = suitWeightDelta + 35 – (rank of card move)
346
else if (card move include equivalent card(s) in the suit)
347
weight = suitWeightDelta + 40 – (rank of card move)
349
weight = suitWeightDelta + 30 – (rank of card move)
350
if (the card move is ”best move” as obtained at search cutoff)
351
weight = weight + 50;
353
else { /* Not a trick winning move */
354
if (either LHO or RHO has singleton in suit which has highest rank)
355
weight = suitWeightDelta + 20 – (rank of card move)
356
else if (hand-to-play has highest rank in suit) {
357
if (partner has second highest rank in suit)
358
weight = suitWeightDelta + 35 – (rank of card move)
359
else if (the card move is the card with highest rank in the suit)
360
weight = suitWeightDelta + 16
362
weight = suitWeightDelta + 4 – (rank of card move)
364
else if (partner has highest rank in suit) {
365
if (hand-to-play has second highest rank in suit)
366
weight = suitWeightDelta + 35 – (rank of card move)
368
weight = suitWeightDelta + 20 – (rank of card move)
370
else if (hand-to-play has second highest rank together with equivalent card(s) in suit)
371
weight = suitWeightDelta + 20 – (rank of card move)
373
weight = suitWeightDelta + 4 – (rank of card move)
374
if (the card move is ”best move” as obtained at search cutoff)
375
weight = weight + 30;
379
Hand-to-play is left hand opponent (LHO) to leading hand
381
if (trick winning card move) {
382
if (hand-to-play void in the suit played by the leading hand) {
383
if (trump contract and trump is equal to card move suit)
384
weight = 30 - (rank of card move) + 2 * (suit length for card move suit)
386
weight = 60 - (rank of card move) + 2 * (suit length for card move suit)
388
else if (lowest card for partner to leading hand is higher than LHO played card)
389
weight = 45 - (rank of card move)
390
else if (RHO has a card in the leading suit that is higher than the trick leading card
391
but lower than the highest rank of the leading hand)
392
weight = 60 - (rank of card move)
393
else if (LHO played card is higher than card played by the leading hand) {
394
if (played card by LHO is lower than any card for RHO in the same suit)
395
weight = 75 - (rank of card move)
396
else if (played card by LHO is higher than any card in the same suit for the leading hand)
397
weight = 70 - (rank of card move)
399
if (LHO move card has at least one equivalent card) {
400
weight = 60 - (rank of card move)
402
weight = 45 - (rank of card move)
405
else if (RHO is not void in the suit played by the leading hand) {
406
if (LHO move card has at least one equivalent card)
407
weight = 50 - (rank of card move)
409
weight = 45 - (rank of card move)
412
weight = 45 - (rank of card move)
414
else { /* card move is not trick winning */
415
if (hand-to-play void in the suit played by the leading hand) {
416
if (trump contract and trump is equal to card move suit)
417
weight = 15 - (rank of card move) + 2 * (suit length for card move suit)
419
weight = - (rank of card move) + 2 * (suit length for card move suit)
421
else if (lowest card for partner to leading hand or for RHO in the suit played is higher
422
than played card for LHO)
423
weight = - (rank of card move)
424
else if (LHO played card is higher than card played by the leading hand) {
425
if (LHO move card has at least one equivalent card)
426
weight = 20 - (rank of card move)
428
weight = 10 - (rank of card move)
431
weight = - (rank of card move)
436
Hand-to-play is partner to trick leading hand
438
if (trick winning card move) {
439
if (hand-to-play void in the suit played by the leading hand) {
440
if (card played by the leading hand is highest so far) {
441
if (card by hand-to-play is trump and the suit played by the leading hand is not trump)
442
weight = 30 - (rank of card move) + 2 * (suit length for card move suit)
444
weight = 60 - (rank of card move) + 2 * (suit length for card move suit)
446
else if (hand-to-play is on top by ruffing)
447
weight = 70 - (rank of card move) + 2 * (suit length for card move suit)
448
else if (hand-to-play discards a trump but still loses)
449
weight = 15 - (rank of card move) + 2 * (suit length for card move suit)
451
weight = 30 - (rank of card move) + 2 * (suit length for card move suit)
454
weight = 60 - (rank of card move)
456
else { /* card move is not trick winning */
457
if (hand-to-play void in the suit played by the leading hand) {
458
if (hand-to-play is on top by ruffing)
459
weight = 40 - (rank of card move) + 2 * (suit length for card move suit)
460
else if (hand-to-play underruffs */
461
weight = -15 - (rank of card move) + 2 * (suit length for card move suit)
463
weight = - (rank of card move) + 2 * (suit length for card move suit)
466
if (the card by hand-to-play is highest so far) {
467
if (rank of played card is second highest in the suit)
469
else if (hand-to-play card has at least one equivalent card)
470
weight = 20 - (rank of card move)
472
weight = 10 - (rank of card move)
475
weight = -10 - (rank of card move)
479
Hand-to-play is right hand opponent (RHO) to leading hand
481
if (hand-to-play is void in leading suit) {
482
if (LHO has current highest rank of the trick) {
484
weight = 14- (rank of card move) + 2 * (suit length for card move)
486
weight = 30- (rank of card move) + 2 * (suit length for card move)
488
else if (hand-to-play ruffs and wins)
489
weight = 30- (rank of card move) + 2 * (suit length for card move)
490
else if (card move suit is trump, but not winning)
491
weight = - (rank of card move)
493
weight = 14- (rank of card move) + 2 * (suit length for card move)
495
else if (LHO has current winning move) {
496
if (RHO ruffs LHO’s winner)
497
weight = 24 - (rank of card move)
499
weight = 30- (rank of card move)
501
else if (card move superior to present winning move not by LHO) {
502
weight = 30- (rank of card move)
504
if (card move ruffs but still losing)
505
weight = - (rank of card move)
507
weight = 14- (rank of card move)
512
6.Algorithm to try early cutoff for generated moves
514
After generating moves at the end of a trick, they are each checked to see if one of them will lead to a position that already is stored in the Transposition Table.
515
Due to the processing overhead, this check is only made if the depth is 29 or more (i.e there are at least 33 cards in the position).
523
if (hit in the transposition table) {
524
Search returnsTRUE if value of the position is TRUE and player side to move, or
525
FALSE if value of the position is FALSE and opponents side to move.
526
Else: Increment weight of move with 100.
530
moveExists = NextMove;
533
The performance improvement for this enhancement is less than for the other enhancements. The number of generated nodes is roughly decreased by 10% and the search time is slighly decreased.
537
7.Storage and retrieval of position state data in the Transposition Table
539
Positions stored in the Transposition Table always consist of completed tricks. Positions stored start at depth=4, then 8,12, and so on. The information stored is information on won cards, the suit lengths of the hands, the hand to play the leading card in the position and upper and lower bounds for the number of future tricks to be taken by the side of the player.
541
Starting from issue 1.1.8, each ”winning cards node” contain all winning cards for one suit after an idea by Joël Bradmetz. This new solution is faster.
543
7.1 Transposition Table storing winning card ranks
545
For the outcome of played tricks, only card ranks that are winning due to their ranks matter:
546
Assume that the last two tricks of a deal without trumps looks like the following:
547
Trick 12: Leading hand North plays heart A, East, South and West follow by hearts Q, 9 and 7 respectively.
548
Trick 13: North then leads spade A, the other hands plays diamonds J, 8,3 in that order.
550
In trick 12, heart A wins by rank. In trick 13, spade A wins but not by rank.
551
The sequence of cards could have been the following without changing the outcome:
552
Trick 12: heart A, heart x, heart x, heart x
553
Trick 13: spade x, diamond x, diamond x, diamond x
554
where x is any rank below lowest winning rank.
556
The cards that win by rank are recorded during the search and backed up similarly to the search value. If a card wins by rank and there are equivalent cards, e.g. only spade A is searched from a sequence of AKQ, then also the other cards K and Q must be recorded as having won by rank.
558
The cards winning by rank are stored in the Transposition Table as relative ranks, however any rank larger than the lowest winning rank in the suit are also stored as ”winning ranks”. Using relative ranks rather than absolute ranks considerably increases the number of positions that match this Transposition Table entry:
559
As an example, assume that there are only 4 cards left in a suit, A, Q, 9, 7 where each hand has one card in the suit. Then any combination of ranks, e.g. 8, 6, 3, 2 that preserves the relative order of ranks between hands will cause a match.
561
In the state position information absolute ranks are used, it is only in the Transposition Table where the ranks are stored as relatives.
564
7.2 Backing up the winning ranks
566
At the search termination, either at the last trick or at a cutoff, the cards that have won by rank are backed up in the search tree together with the search value.
567
As this information propagates upwards, it is aggregated with backed up information from other tree branches.
568
At a search cutoff, MergeMoveData merges the information (V is a union):
570
(winning ranks of all suits for current depth) = (winning ranks of all suits for depth - 1) V (possible winning rank for the current move causing the cutoff)
572
For each new move not causing cutoff, MergeAllMovesData merges:
574
(winning ranks of all suits for current depth) = (winning ranks of all suits for current depth) V (winning ranks of all suits for depth - 1) V (possible winning rank for the current move)
577
7.3 Checking the current position for a Transposition Table entry match
579
The "Transposition Table" has a tree structure rather than a table, consisting of 2 interconnected trees.
580
For deciding if there is a match, input is the position state data, including the cards left to play and the current leading hand.
581
There are ”root pointers” per number of tricks left and per leading hand which each points to the root of a tree of ”suit lengths combination” nodes. Each such node includes a 64-bit code that uniquely defines one combination of suit lengths for the hands. The nodes are ordered such that the value of the 64-bit code in a parent node is higher than the 64-bit code of its left child but lower than the 64-bit code of its right child. So to find the node with the suit lengths combination for the actual position, a binary search is made. The basic binary search algorithm is described in [Knuth].
582
Each ”suit length combination node” points to the root of a tree consisting of ”winning cards nodes”, ie. cards that win by rank. (So the Transposition Table is really a number of trees, a forest.)
583
When a position is checked for a possible Transposition Table match, a tree branch is selected consisting of 4 subsequent ”winning cards nodes”, each ”winning cards node” includes an aggregate of all winning cards for one suit. This branch is followed as long as the ”winning cards” also can be found in the current position. (Note that the ranks of the ”winning card nodes” are relative, so the ranks of the current position must first be translated from absolute to relative ranks.) When the ”winning cards node” no longer matches with the current position and there is no other alternative ”winning cards node” that fits, then the search backs up and tries an alternative ”winning cards node” on a higher level.
585
When the last of the 4 subsequent ”winning cards nodes” containing clubs is reached, it points to a ”set of positions node”. Its stored upper and lower value bounds are checked against the number of tricks won so far by the player’s side and the target value. The following conditions are then checked, assuming that it is the North/South side that is the player’s side:
587
If the sum of the stored lower value bound and the number of tricks won so far for the player’s side is equal or larger than target, then target can be reached for the player’s side in the current position. Search on this depth is terminated and TRUE is returned.
589
If the sum of the stored upper value bound and the number of tricks won so far for the player’s side is less than target, then reaching target can be prevented by the opponents to the player’s side in the current position. Search on this depth is terminated and FALSE is returned.
591
If instead it is East/West that is the player’s side, the following conditions apply:
593
If the sum of number of tricks remaining and the number of tricks won so far for the player’s side minus the upper value bound is equal or larger than target, then target can be reached for the player’s side in the current position. Search on this depth is terminated and TRUE is returned.
595
If the sum of number of tricks remaining and the number of tricks won so far for the player’s side minus the lower value bound is less than target, then reaching target can be prevented by the opponents to the player’s side in the current position. Search on this depth is terminated and FALSE is returned.
597
For all other cases, the search continues for the current depth.
599
For example, take the previous example with 2 tricks remaining with spade rank order 1 at North. (Rank order 1 is highest rank.) The hearts have rank orders 1 at North, 2 at East, 3 at South and 4 at West. The diamond rank orders are orders 1 at East, 2 at South and 3 at West. North is leading hand.
600
The ”root pointer” is now defined by the number of tricks remaining (=2) and North as leading hand.
601
The ”root pointer” points to the root node of its ”suit lengths combination” tree. The 64-bit integer coded from the suit lengths for all suits and hands is now searched within the tree. When the node is found with matching 64-bit suit lengths code, this node will point to the root of its ”winning card” tree.
602
This pointer points to a "winning cards node" containing spade rank order 1 at North which fits with the current position. This ”winning cards node” points to another "winning cards node" containing hearts rank orders 1 at North and 2 at East which also fits the current position. Next ”winning cards node” pointed to contains diamonds order 1 at South, which does not match the current position. However, there is an alternative ”winning cards node” that has diamonds order 1 at East, which fits. (If there had been no alternative ”winning cards node” which fitted, the search had backed up to the previous ”winning cards node” to see if there was an alternative ”winning cards node” on this level which also fitted.) The next ”winning cards node” pointed to is for clubs. This node is empty, which fits the current position which have no clubs.
603
This ”winning cards node” points to a "set of positions node” which have upper and lower value bounds defined. The conditions for these bounds are assumed to be fulfilled causing search termination on this depth, as described earlier.
605
The usage of upper and lower value bounds in transposition tables is described in [Chang] and [Kupferschmid, Helmert].
609
The ”suit lengths combination” node includes:
610
The suit lengths combination as a 64-bit integer.
611
A pointer to the top ”winning cards node”.
612
A pointer to next left ”suit lengths combination node” in the binary tree.
613
A pointer to next right ”suit lengths combination node” in the binary tree.
616
The ”winning cards node” includes:
617
The hands of the relative ranks for each winning card of the actual suit.
618
A pointer to the next winning cards node required to achieve a Transposition Table match for this branch of the tree.
619
A pointer to the previous winning cards node.
620
A pointer to the next alternative winning cards node that leads to a Transposition Table match in an alternative tree branch.
621
A pointer to the "set of positions node".
624
The "set of positions node” includes:
625
An upper and a lower bound for the winning tricks of the North/South side. These values
626
are used to determine whether or not a search cutoff can be done.
627
The lowest winning rank per suit, expressed as relative rank.
628
The suit and rank for the currently best move.
631
After a Transposition Table match, the current position may later be part of a position that will be stored in the Transposition Table. Therefore, the stored winning ranks in the Transposition Table must be included in the state information of the current position. However, the winning ranks cannot be taken as is, because they are stored as relative ranks which now must be converted to absolute ranks in the current position.
632
This is done using the lowest winning relative rank for each suit that is stored in the ”set of positions” node that gave the Transposition Table match:
633
The aggregated set of (absolute) ranks for each suit in the current position is filtered using the stored information on the lowest winning relative rank. The winning ranks for each suit is then the aggregated set with only the number of highest ranks implied by the stored lowest winning relative rank in the ”set of positions” node.
634
E.g. if the aggregated rank set for spades is A J 9 4 2 and lowest winning relative rank is order=2, then winning ranks are A J.
637
7.4 Building a new entry in the Transposition Table
639
When the value of the current position is known and it is the end of a trick (except the last), position state information is collected for storage in the Transposition Table.
640
The ranks of the backed up winning cards are converted from absolute to relative.
641
For each suit, it is determined which winning rank that is lowest. The relative ranks then stored in the new Transposition Table entry are all ranks above and including the lowest rank, filling out any ”holes” in the ranks that might have been present.
642
The trees of the Transposition Table are searched starting from the ”root pointer” and additional nodes are inserted corresponding to the current position.
643
First, the suit lengths of the current position are used to find a ”suit lengths combination node” or to create a new such node if it does not exist already.
644
The next step is to search for a ”winning card node” that has the ”suit length combination node” as parent. This ”winning card node” has then winning cards for spades.
645
If no such node yet exists, ”winning card nodes”, one for each suit, are created using the winning cards of the current position. Each such node includes all winning cards for one of the suits. Then, a ”set of positions” node is created. This node is pointed to from the last created ”winning card node” created for the winning cards of clubs.
646
Otherwise, if there already exists a matching ”winning card node” with the ”suit length combination node” as parent, it is checked whether or not the ”winning card nodes” in a subsequent tree branch already created for hearts, diamonds and clubs also are matched with the current position.
647
If such a sequence of nodes can be found, the upper or lower bound in the connected ”set of positions node” may be updated to allow for an increased number of cutoffs:
649
If the current position upper value bound is less than the stored upper value bound, the stored value is updated with the current position value.
650
If the current position lower value bound is larger than the stored lower value bound, the stored value is updated with the current position value.
652
In case a matching ”winning card node” cannot be found, a new ”winning card node” is created and linked to the last matching node. E.g. if existing ”winning card nodes” for spades and hearts match the current position, but no node match for diamonds, then a ”winning cards node” for diamonds is created and linked to the previous ”winning cards node” for hearts. Then a clubs ”winning cards node” and a ”set of positions node” are created.
661
Source code for a simple DDS.
662
http://freepages.genealogy.rootsweb.com/~jamesdow/Tech/dbldum.htm
665
DDS algorithms description (in German) and DDS source code.
666
http://linux.softpedia.com/get/Science-and-Engineering/Artificial-Intelligence/cddsolve-20055.shtml
669
DDS algorithms description.
670
cs.nyu.edu/web/Research/TechReports/TR1996-725/TR1996-725.ps.gz
674
DDS source code and DDS executable.
675
http://freefinesse.sourceforge.net/
678
DDS algorithms description.
679
http://www.cs.cmu.edu/afs/cs/project/jair/pub/volume14/ginsberg01a.pdf
682
DDS algorithms description and DDS executable (MS DOS, cannot run in XP?)
683
http://www.ics.uci.edu/~dan/bridge/index.html
686
DDS source code and DDS executable.
688
Judea Pearl: Asymptotic properties of minimax trees and game search precedures.
689
Artificial Intelligence 14(2):113-138. [Pearl 1980]
691
Aske Plaat, Jonathan Schaeffer, Wim Pijls and Arie de Bruin: Exploiting graph properties of game trees. In Proceedings of the Thirteenth National Conference on Artificial Intelligence, pages 234-239, 1996 [Plaat et al.]
693
Hans Kuijf, personal communication.
695
Pedja Stanojevic, personal communication.
697
Knuth: The art of computer programming, Vol. 3, Searching and Sorting, chapter 6.2.2, Algorithm T.
699
Sebastian Kupferschmid, Malte Helmert: A Skat Player Based on Monte Carlo Simulation.
701
Joël Bradmetz, personal communication.
702
http://jibe-bridge.perso.cegetel.net/