~ubuntu-branches/ubuntu/oneiric/dds/oneiric

Bo Haglund

Rev. E1,  2008-03-21

 

 

Search Algorithms for a Bridge Double Dummy Solver 

 

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.  

 

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.

 

 

 

 

1.The basic search algorithm

 

 The search is based on the zero window search [Pearl 1980]. 

 Pseudo code for its application on DD solver search is given.

 Cards searched are described as ”moves” in contrast to cards that are really played.

 

 int  Search(posPoint, target, depth) {

    if (depth==0) {

        tricks=Evaluate;

        if  (tricks >= target) 

            value=TRUE;

        else

            value=FALSE;

        return value;

    }

    else {

        GenerateMoves;

        if  (player_side_to_move) {

            value=FALSE;   moveExists=TRUE;

            while (moveExists) {

                Make;

                value=Search(posPoint, target, depth-1);

                Undo;

                if  (value==TRUE) 

        goto searchExit;        /* Cutoff, current move recorded as ”best move” */

                moveExists=NextMove;

            }

        }       /* Opponents to move */

        else {      

             value=TRUE;   moveExists=TRUE;

             while (moveExists) {

                 Make;

                 value=Search(posPoint, target, depth-1);

                 Undo;

                 if  (value==FALSE) 

        goto searchExit;        /* Cutoff, current move recorded as ”best move” */

                 moveExists=NextMove;

             }

        }

    }

 

    searchExit:

    return  value;

}

 

 

The Search  parameters are:

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.

target -  the number of tricks the player must take. 

depth -  the current search depth.

 

Search returns TRUE if the target is reached, otherwise FALSE.

 

When Search is called, depth is set to the number of cards left to play minus 4. 

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. 

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.

 

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”.

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”.

 

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.

Finally, Search returns for the top level.

 

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.  

 

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:

 

g = guessed number of tricks for side of the player

iniDepth = number of cards to play minus 4

upperbound = 13;

lowerbound = 0;

do  {

    if  (g==lowerbound)

        tricks=g+1;

    else

        tricks=g;

    if  ((Search(posPoint, tricks, iniDepth)==FALSE)  {

        upperbound=tricks-1;

        g=upperbound;

    }

    else  {

        lowerbound=tricks;

        g=lowerbound;

    }

}

while (lowerbound < upperbound);

g=maximum tricks to be won by side of player.

 

 

 

2.Overview of the search algorithms used in the DD solver 

 

The additional functions in the pseudo code for supporting the search speed enhancements are given in italics.  

 

int  Search(posPoint, target, depth) {

      if (no_move_yet_in_trick)  {

          TargetTooLowOrHigh;

          if (target_already_obtained)

              return TRUE;

          else if (target_can_no_longer_be_obtained)

              return FALSE; 

          QuickTricks;

          LaterTricks;

          if  (cutoff_for_player_side) 

             return TRUE;

          else if  (cutoff_for_opponent_side)

             return FALSE;

          RetrieveTTresult;

          if (transposition_table_entry_match) {

             if  (target_reached)

                return TRUE;

            else

                return FALSE;

         }

     }

 

      if (depth==0) {

          evalRes=Evaluate;

          if  (evalRes.tricks >= target) 

             value=TRUE;

         else

             value=FALSE;

         return value;

      }

      else {

          GenerateMoves; 

          MoveOrdering;

          CheckMovesForCutoff;   /* For pseudo-code, see chapter 6 */  

          if  (player_side_to_move) {

              value=FALSE;    moveExists=TRUE;

              while (moveExists) {

                 Make;

                 value=Search(posPoint, target, depth-1);       

                 Undo;

                 if  (value==TRUE)  {

        MergeMoveData; 

        goto searchExit;        /* Cutoff, current move recorded as ”best move” */

                 }

                 MergeAllMovesData;

                 moveExists=NextMove;

             }

         }      /* Opponents to move */

         else {     

             value=TRUE;   moveExists=TRUE;

             while (moveExists) {

                 Make;

                 value=Search(posPoint, target, depth-1);       

                 Undo;

                 if  (value==FALSE)  { 

        MergeMoveData;

        goto searchExit;        /* Cutoff, current move recorded as ”best move” */

                 }

                 MergeAllMovesData;

                 moveExists=NextMove;

             }

         }

     }

     searchExit:

     AddNewTTentry;

     return  value;

 }

 

 

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.

It is executed at the beginning of each trick, before any card has been played.

If number of currently won tricks by player’s side equals or exceeds target, Search returns TRUE.

If number of currently won tricks by player’s side plus tricks left to play is less than target Search returns FALSE.

Since possible winning cards for the remaining tricks are irrelevant, no winning cards are backed up at cutoff termination.

 

TargetTooLowOrHigh  search enhancement is described e.g. in [Chang].

 

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.

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.

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.

The detailed conditions for determination of sure tricks are described in Chapter 3.

When quicktricks win by rank, they are backed up at cutoff termination. 

 

The idea of QuickTricks is described e.g. in [Chang].

 

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. 

When quicktricks win by rank, they are backed up at cutoff termination.

For a detailed description, see Chapter 4.

 

RetrieveTTresult scans the set of positions in the transposition table to see if there is a match against the current position. 

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. 

For details, see Chapter 7.

 

Evaluate  returns evalResult which updates the position state information. evalResult contains:

evalResult.tricks, the number of tricks won by the side of the player, and

evalResult.winRank which includes the card in the last trick that won by rank.  

E.g. if the last trick includes the spades A, Q, 9 and 3, evalResult.winRank returns spade A. But

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. 

 

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]. 

 

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.

 

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.

 

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.

 

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.

 

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.

 

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.

 

AddNewTTentry adds the evaluated position as a new entry in the transposition table. See Chapter 7.

 

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.

This search enhancement was suggested by Hans Kuijf [Kuijf]. 

 

 

 

3.The Quick Tricks cutoff algorithm

 

The number of tricks that can immediately be taken by the side to play the leading card of the trick consists of:

a)The number of tricks that can be taken by the hand-to-play, and

b)The number of tricks that can be taken by the partner of the hand-to-play

At return by QuickTricks, the position state information is updated with the winning ranks found. 

 

Of course, in order to add b), there must be an entry from the hand-to-play to the partner’s hand.

 

For each ”s” (suit) the following is calculated:

 

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.

 

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.

 

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:

The number of quick tricks for s is the suit length of partner.

 

Else:

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.

 

Else:

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.

 

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.

 

When the other suits are investigated for quick tricks, only the remaining opponent trump cards need to be considered.

 

The quick tricks are then summarized from each suit, and the total calculated.

 

A simple Quick Tricks algorithm is also executed after the leading card of the trick has been played:

 

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.

 

The idea to also execute Quick Tricks after the leading card has been played was given by Hans Kuijf [Kuijf].

 

 

 

4.The Later Tricks cutoff algorithm 

 

Check for search cutoff if the opponents to the trick leading hand have at least a sure trick later. 

 

If not trump contract:

 

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.

More than one sure trick can be taken by the opponents if they possess the winning rank for more than one suit, or

 

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

maximum lengths of these suits.

If this still cannot cause a cutoff for the trick leading side, allocate one sure trick for the opponents side.   

 

If trump contract:

 

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].

 

1)   If the opponent side have all the trumps, the number of sure tricks is the maximum suit length

      length, or

 

2)   If the opponent side has the highest trump, they have 1 sure trick. If they also have the second

      highest trump, they have 2 sure tricks, or

 

3)  If the opponent side has the second highest trump plus at least one trump more behind the 

     hand with the highest trump, the opponent side has 1 sure trick.

 

5.The Move Ordering algorithm

 

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.

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. 

There are 2 exceptions though:

If the hand-to-play is trick leading hand, cards having the suit decided as best by the move ordering algorithm will occupy the first two positions in the move list, provided that there are at least 2 cards with that suit.

If the hand-to-play is void in the suit played by leading hand, a card having the suit decided as best by the move ordering algorithm will occupy the first position in the move list.

 

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:

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. 

At a Transposition Table entry match, its stored best move will be best move for the current search depth.

 

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. 

 

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. 

 

 

Hand-to-play is trick leading hand

 

The contribution of the suit to the weight:

 

suitWeightDelta = suitBonus - (countLH+countRH) * 2

 

If trump contract, and the suit is not trump, then there is a (negative) suitBonus of –12  if 

LHO is void and LHO has trump card(s), or

RHO is void and RHO has trump card(s)

 

Otherwise, suitBonus = 0.

 

countLH = (suit length of LHO) * 4, if LHO is not void in the suit,

countLH = (depth + 4), if LHO is void in the suit

 

countRH = (suit length of RHO) * 4, if RHO is not void in the suit,

countRH = (depth + 4), if RHO is void in the suit

 

Suits are thus favoured where the opponents have as few move alternatives as possible. 

 

 

if (trick winning card move) {

    if (one of the opponents has a singleton highest rank in the suit)

        weight = suitWeightDelta + 40 – (rank of card move)

    else if (hand-to-play has highest rank in suit)  {

        if (partner has second highest rank in suit)

            weight = suitWeightDelta + 50 – (rank of card move)

        else if  (the card move is the card with highest rank in the suit)

            weight = suitWeightDelta + 31

        else

            weight = suitWeightDelta + 19 – (rank of card move)

    }

    else if  (partner  has highest rank in suit)  {

        if (hand-to-play has second highest rank in suit)

            weight = suitWeightDelta + 50 – (rank of card move)

        else

            weight = suitWeightDelta + 35 – (rank of card move)  

    }

    else if (card move include equivalent card(s) in the suit)

        weight = suitWeightDelta + 40 – (rank of card move)

    else

        weight = suitWeightDelta + 30 – (rank of card move)

    if  (the card move  is ”best move” as obtained at search cutoff)

        weight = weight + 50;

}

else {  /* Not a trick winning move */

    if  (either LHO or RHO has singleton in suit which has highest rank)

        weight = suitWeightDelta + 20 – (rank of card move)

    else if (hand-to-play has highest rank in suit)  {

        if (partner has second highest rank in suit)

            weight = suitWeightDelta + 35 – (rank of card move)

        else if  (the card move is the card with highest rank in the suit)

            weight = suitWeightDelta + 16

        else

            weight = suitWeightDelta + 4 – (rank of card move)

    }

    else if  (partner  has highest rank in suit)  {

        if (hand-to-play has second highest rank in suit)

            weight = suitWeightDelta + 35 – (rank of card move)

        else

            weight = suitWeightDelta + 20 – (rank of card move)  

    }

    else if  (hand-to-play has second highest rank together with equivalent card(s) in suit)

        weight = suitWeightDelta + 20 – (rank of card move)

    else

        weight = suitWeightDelta + 4 – (rank of card move)

    if  (the card move  is ”best move” as obtained at search cutoff)

        weight = weight + 30;

}

 

 

 Hand-to-play is left hand opponent (LHO) to leading hand

 

if (trick winning card move) {

    if  (hand-to-play void in the suit played by the leading hand)  {

        if  (trump contract and trump is equal to card move suit)

            weight = 30 - (rank of card move) + 2 * (suit length for card move suit)

        else

            weight = 60 - (rank of card move) + 2 * (suit length for card move suit)

    }

    else if (lowest card for partner to leading hand is higher than LHO played card)

        weight = 45 - (rank of card move)

    else if (RHO has a card in the leading suit that is higher than the trick leading card

               but lower than the highest rank of the leading hand)

        weight = 60 - (rank of card move)

    else if (LHO played card is higher than card played by the leading hand) {

        if (played card by LHO is lower than any card for RHO in the same suit)

            weight = 75 - (rank of card move)

        else if (played card by LHO is higher than any card in the same suit for the leading hand)

            weight = 70 - (rank of card move)

        else  {

            if  (LHO move card has at least one equivalent card) {

                weight = 60 - (rank of card move) 

            else

                weight = 45 - (rank of card move)

        }

    }

    else if (RHO is not void in the suit played by the leading hand) {

        if  (LHO move card has at least one equivalent card)    

            weight = 50 - (rank of card move)

        else

            weight = 45 - (rank of card move)

    }

    else

        weight = 45 - (rank of card move)

}

else {  /* card move is not trick winning */

    if  (hand-to-play void in the suit played by the leading hand)  {

        if  (trump contract and trump is equal to card move suit)

            weight = 15 - (rank of card move) + 2 * (suit length for card move suit)

        else

            weight = - (rank of card move) + 2 * (suit length for card move suit)

    }

    else if (lowest card for partner to leading hand or for RHO in the suit played is higher 

               than played card for LHO) 

        weight = - (rank of card move) 

    else if (LHO played card is higher than card played by the leading hand) { 

        if  (LHO move card has at least one equivalent card)

            weight = 20 - (rank of card move) 

         else 

             weight = 10 - (rank of card move)

     }  

     else 

         weight = - (rank of card move)

}      

 

 

 

Hand-to-play is partner to trick leading hand

 

if (trick winning card move) {

    if  (hand-to-play void in the suit played by the leading hand)  {

        if (card played by the leading hand is highest so far) {

            if (card by hand-to-play is trump and the suit played by the leading hand is not trump) 

                weight = 30 - (rank of card move) + 2 * (suit length for card move suit)

            else

                weight = 60 - (rank of card move) + 2 * (suit length for card move suit)

        }

        else if (hand-to-play is on top by ruffing)

            weight = 70 - (rank of card move) + 2 * (suit length for card move suit)

        else if (hand-to-play discards a trump but still loses)

            weight = 15 - (rank of card move) + 2 * (suit length for card move suit) 

        else       

            weight = 30 - (rank of card move) + 2 * (suit length for card move suit)

    }

    else 

        weight = 60 - (rank of card move) 

}

else {               /* card move is not trick winning */

    if  (hand-to-play void in the suit played by the leading hand)  {

        if (hand-to-play is on top by ruffing)

            weight = 40 - (rank of card move) + 2 * (suit length for card move suit)

        else if (hand-to-play underruffs */

            weight = -15 - (rank of card move) + 2 * (suit length for card move suit)

        else

            weight = - (rank of card move) + 2 * (suit length for card move suit)

    }

    else {

         if (the card by hand-to-play is highest so far) {

             if (rank of played card is second highest in the suit)

                weight = 25  

             else if (hand-to-play card has at least one equivalent card)

                 weight = 20 - (rank of card move)

             else

                 weight = 10 - (rank of card move)

         }

         else

             weight = -10 - (rank of card move)

    }

}

 

Hand-to-play is right hand opponent (RHO) to leading hand

 

if  (hand-to-play is void in leading suit)  {

    if  (LHO has current highest rank of the trick)  {

       if  (card move ruffs)

          weight = 14- (rank of card move) + 2 * (suit length for card move)

       else

          weight = 30- (rank of card move) + 2 * (suit length for card move) 

     }

    else if  (hand-to-play ruffs and wins) 

         weight = 30- (rank of card move) + 2 * (suit length for card move)

    else if  (card move suit is trump, but not winning)

        weight = - (rank of card move)

    else

        weight = 14- (rank of card move) + 2 * (suit length for card move)

}

else if  (LHO has current winning move)  {

    if  (RHO ruffs LHO’s winner)

        weight = 24 - (rank of card move) 

    else

        weight = 30- (rank of card move) 

}

else if  (card move superior to present winning move not by LHO)  {        

     weight = 30- (rank of card move)

else  {

    if  (card move ruffs but still losing)

        weight = - (rank of card move)

    else

        weight = 14- (rank of card move)

}

 

 

 

6.Algorithm to try early cutoff for generated moves

 

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.

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). 

Pseudo code:

 

moveExists = TRUE;

while  (moveExists)  {

     Make;

     depth = depth –1;

     RetrieveTTresult;

     if (hit in the transposition table)  {

          Search returnsTRUE if value of the position is TRUE and player side to move, or 

          FALSE if value of the position is FALSE and opponents side to move.  

          Else: Increment weight of move with 100.  

      }

       depth = depth +1;

       Undo;

       moveExists = NextMove;

}

    

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.

 

 

 

7.Storage and retrieval of position state data in the Transposition Table

 

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.

 

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.

 

7.1   Transposition Table storing winning card ranks

 

For the outcome of played tricks, only card ranks that are winning due to their ranks matter:

Assume that the last two tricks of a deal without trumps looks like the following:

Trick 12: Leading hand North plays heart A, East, South and West follow by hearts Q, 9 and 7 respectively. 

Trick 13: North then leads spade A, the other hands plays diamonds  J, 8,3 in that order.

 

In trick 12, heart A wins by rank. In trick 13, spade A wins but not by rank.

The sequence of cards could have been the following without  changing the outcome:

Trick 12:  heart A, heart x, heart x, heart x

Trick 13:  spade x, diamond x, diamond x, diamond x

where x is any rank below lowest winning rank.

 

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.

 

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:

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.

 

In the state position information absolute ranks are used, it is only in the Transposition Table where the ranks are stored as relatives. 

 

 

7.2  Backing up the winning ranks

 

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.

As this information propagates upwards, it is aggregated  with backed up information from other tree branches.

At a search cutoff, MergeMoveData merges the information (V is a union):

   

(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)

 

For each new move not causing cutoff, MergeAllMovesData merges:

 

(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) 

 

 

7.3     Checking the current position for a Transposition Table entry match 

 

The "Transposition Table" has a tree structure rather than a table, consisting of 2 interconnected trees. 

For deciding if there is a match, input is the position state data, including the cards left to play and the current leading hand. 

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]. 

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.)

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. 

 

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: 

 

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.

 

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.

 

If instead it is East/West that is the player’s side, the following conditions apply:

 

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.

 

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.

 

For all other cases, the search continues for the current depth.

 

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.

The ”root pointer” is now defined by the number of tricks remaining (=2) and North as leading hand.

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.

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. 

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. 

 

The usage of upper and lower value bounds in transposition tables is described in [Chang] and [Kupferschmid, Helmert].

 

 

 

The ”suit lengths combination” node includes:

      The suit lengths combination as a 64-bit integer.

      A pointer to the top ”winning cards node”.

      A pointer to next left ”suit lengths combination node” in the binary tree.

      A pointer to next right ”suit lengths combination node” in the binary tree.

 

 

The ”winning cards node” includes:

The hands of the relative ranks for each winning card of the actual suit.

A pointer to the next winning cards node required to achieve a Transposition Table match for this branch of the tree.

A pointer to the previous winning cards node.

A pointer to the next alternative winning cards node that leads to a Transposition Table match in an alternative tree branch.

      A pointer to the "set of positions node". 

 

 

The "set of positions node” includes:

An upper and a lower bound for the winning tricks of the North/South side. These values

are used to determine whether or not a search cutoff can be done.

The lowest winning rank per suit, expressed as relative rank.

The suit and rank for the currently best move.

 

 

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.

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:

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.

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.

 

 

7.4  Building a new entry in the Transposition Table

 

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. 

The ranks of the backed up winning cards are converted from absolute to relative.

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.

The trees of the Transposition Table are searched starting from the ”root pointer” and additional nodes are inserted corresponding to the current position. 

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.

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.

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. 

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.

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:

 

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.   

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.

 

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.

 

 

 

 

 

References

 

James Dow Allen:

Source code for a simple DDS.

http://freepages.genealogy.rootsweb.com/~jamesdow/Tech/dbldum.htm

 

Matthias Brill:

DDS algorithms description (in German) and DDS source code.

 http://linux.softpedia.com/get/Science-and-Engineering/Artificial-Intelligence/cddsolve-20055.shtml 

 

Ming-Sheng Chang:

DDS algorithms description.

cs.nyu.edu/web/Research/TechReports/TR1996-725/TR1996-725.ps.gz

 

 

Ed Colley:

DDS source code and DDS executable.

http://freefinesse.sourceforge.net/

 

Matthew L. Ginsberg:

DDS algorithms description.

http://www.cs.cmu.edu/afs/cs/project/jair/pub/volume14/ginsberg01a.pdf

 

Dan Hirschberg:

DDS algorithms description and DDS executable (MS DOS, cannot run in XP?)

http://www.ics.uci.edu/~dan/bridge/index.html

 

Alexey Slovesnov:

DDS source code and DDS executable.

http://slovesnov.narod.ru/bridge/en/index.html

 

Judea Pearl: Asymptotic properties of minimax trees and game search precedures.

   Artificial Intelligence 14(2):113-138. [Pearl 1980]

 

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.]

 

Hans Kuijf, personal communication.

 

Pedja Stanojevic, personal communication.

 

Knuth: The art of computer programming, Vol. 3, Searching and Sorting, chapter 6.2.2, Algorithm T.

 

Sebastian Kupferschmid, Malte Helmert: A Skat Player Based on Monte Carlo Simulation.

 

Joël Bradmetz, personal communication.

http://jibe-bridge.perso.cegetel.net/