program performance

The following table illustrates the program's performance on a Sparc 5.

The execution time dramatically increases with the problem size and difficulty. Many hands require only a few minutes, but some hands (two examples given below) require several hours, even using Version 4.
If the pool usage approaches 100%, increasing POOLSIZ may significantly improve performance. In one example hand shown below, increasing POOLSIZ by 50% reduced the number of nodes (and time) by a factor of 2.
The performance (execution time) will degrade horribly if too much space is used. One should adjust STKSIZ and POOLSIZ so as to avoid using any virtual memory. Since there are other resident programs (such as the underlying operating system), a reasonable rule of thumb is to use 75% of physical memory.
When tree production is optionally suppressed, fewer nodes need to be expanded.
Further significant performance enhancements are certainly possible, as comparison with Matt Ginsberg's engine (MG) illustrates.

    |"devilish"|   hard   |  harder  |
    |   3NT    |    7H    |    3NT   |
    |          |          |          | alpha-beta
Vers|Nodes Time|Nodes Time|Nodes Time|  amenities
----|----- ----|----- ----|----- ----| ----------
 0  | 21 M 11 m|          |          | dynamic rank equiv
 1  |7.8 M 110 |          |          | dynamic rank order
 2  | 562k  13 | 65 M 41 m|          | node isomorphism
    | 541k  12 | 19 M 12 m|281 M 107m|     "    , no tree
 3  | 198k 6.4 |2.7 M 130 |9.7 M 327 | node equivalence
    | 188k 5.4 |1.4 M  59 |6.4 M 195 |     "    , no tree
 4  | 136k 2.6 |1.2 M  27 |6.2 M 127 | dynamic backtrack
    | 126k 2.3 |1.0 M  22 |5.6 M 109 |     "    , no tree
----|----- ----|----- ----|----- ----| ----------
MG  |  46k 3.0 |  51k 3.5 | 219k  16 | partition search, no tree

In the above table,
Nodes = number of nodes expanded (M = million, k = thousand)
Time = time to complete (in seconds, except m = minutes) on a Sparc 5.
A Pentium Pro 200 would be about 2.5 to 3 times faster.

The hands are as follows:

#========================================
#  "devilish" 3NT
WHO = N
NEED = 9
SIZE = 13
TRUMP = N
LEADER = W
FORCED = QH
NORTH = S AK83 H AK     D A65432 C K
EAST  = S JT92 H 54     D Q      C 765432
SOUTH = S Q74  H 932    D J87    C QT98
WEST  = S 65   H QJT876 D KT9    C AJ
#========================================
#  hard 7H
WHO = N
NEED = 13
SIZE = 13
TRUMP = H
LEADER = W
FORCED = QC
NORTH = S 5     H 85     D AK7  C AK86542
EAST  = S 86432 H Q632   D J62  C 3
SOUTH = S AQJ9  H AKJT74 D 954
WEST  = S KT7   H 9      D QT83 C QJT97
#========================================
#  harder 3NT
WHO = S
NEED = 9
SIZE = 13
TRUMP = N
LEADER = W
FORCED = 7S
NORTH = S 43    H AK42 D A6    C QT853
EAST  = S K2    H 9876 D KT4   C K974
SOUTH = S AT86  H Q5   D Q7532 C A6
WEST  = S QJ975 H JT3  D J98   C J2
#========================================
# painful for the program
# (hand provided by John Moore)
# using POOLSIZ=1800, Version 4 expanded approx. 1.5 Billion nodes
# using POOLSIZ=2700, Version 4 expanded 839 million nodes
#       and took 309 minutes (about 5 hours) on my Sparc 5
WHO = S
NEED = 9
SIZE = 13
TRUMP = N
LEADER = W
PRINT = 0
WEST =  S J     H KT8732 D 84    C JT32
NORTH = S K982  H Q6     D QJT9  C A97
EAST =  S AT653          D A6532 C Q84
SOUTH = S Q74   H AJ954  D K7    C K65
#========================================
# very painful for the program
# (hand provided by Thomas Andrews)
# using POOLSIZ = 2700, Version 4 expanded 2.45 Billion nodes
#       and took 901 minutes (about 15 hours) on my Sparc 5
WHO = S
NEED = 11
SIZE = 13
TRUMP = C
LEADER = W
PRINT = 0
NORTH = S KT83          D KT64  C J6543
EAST  = S 94   H J9865  D AJ873 C T
SOUTH = S AQ72 H AK     D 952   C AK82
WEST  = S J65  H QT7432 D Q     C Q97
#========================================

Dan Hirschberg
Computer Science Department
University of California, Irvine, CA 92697-3425

dan at ics.uci.edu
Last modified: July 1, 1996