Back to Deal Top Page.

Deal 3.0 - New Features

  • General performance improvements using Tcl 8.x features
  • Fast holding procedures
  • Interface to the GIB double dummy solver
  • More input formats, and extensible input formats
  • Smart hand stacking

Performance Improvements

There are a number of performance improvements in Deal 3.0.

Tcl 8.x Improvements

In early releases of Tcl (7.x and earlier) the interpreter treated everything as a string. That meant that Tcl data and procedures were regularly parsed and reparsed, which made it a fairly slow language. Tcl 8.x changed that - it uses internal objects which have optional string representations.

This means that the first time you pass the string "AK4" to a Deal procedure, it will parse it into an internal represention, and then never parses it again. The internals of Deal now take advantage of this in quite a lot of places.

Fast and general holding procedures

Many bridge evaluators can be seen as evaluating the holdings in each suit, and then adding up the values. For example, in the hand:
  Spades: AKx
  Hearts: KQJ
Diamonds: xxxx
   Clubs: Axx
We compute the high card points as 7, 6, 0, and 4, in spades, hearts, diamonds, and clubs, for a total of 17 points. We compute losers in the suits as 1, 1, 3, and 2, for a total of 7 losers.

In Deal 2.0, you could define a very limited set of procedures of this sort - the so-called vector procedures. You could, for example, define "high card points" or "controls," but not "losers."

In Deal 3.0, virtually any such procedure can be written.

See seperate document for more details.

Other Features

GIB interfaces

Deal 3.0 now has a a set of tools for people who own GIB. Specifically, it provides a procedure for determing the number of tricks available on a deal, double dummy.

See separate document for details.

Input formats

Deal 3.0 now lets you read deals from a file easily. It is also easy to write extensions which change the way Deal 3.0 reads from files or generates deals.

To access an input format, you can either add the line:

deal::input formatName [args...]
or, from the command line, use the -I switch:
deal -I "FormatName[ args...]" ...
Deal 3.0 includes the following input formats:
line
This reads in deals in the format written by deal with the -l flag. For example, you can generate a file of 1000 deals then run two seperate queries on the file with:
deal -l 1000 > sample.txt
deal -I "line sample.txt" -i query1.tcl > out1.txt
deal -I "line sample.txt" -i query2.tcl > out2.txt
If no file is given, the lines are read from standard input.

giblib
Matt Ginsberg has made available a large file of 700,000+ deals with double dummy data. This input format lets read this data file sequentially. Calls to the GIB procedure gib::tricks take the data from this file, rather than calling the double-dummy solver.
deal::input giblib [filename]
If no file is given, Deal looks in the current directory for a file named library.dat.

The data file is not included in this release - it's really huge. See the GIB research project page for more details.

smartstack
The deal of the smartstack is to find certain rare types of deals very quickly, not using the standard dealing techniques, but using a more complicated and data-heavy approach. Smart stacking is documented seperately below.
To add a new input format named Foo, you write a file named input/Foo.tcl which contains a Tcl package named Foo with procedures called set_input and next. See the input formats included with Deal for examples. The next procedure should return an error when it has reached the end of input.

An input format does not have to read from a file. For example, the smartstack code is a factory which builds deals on the fly with one hand fitting a certain condition.

Smart Stacking

Deal, by default, just keeps dealing hands until it finds one that fits a pattern. This can be too slow sometimes when looking for specific hands.

Suppose we want north to have a balanced hand with 22 or 23 high card points. We can force this by using the smartstack input format:

deal::input smartstack north balanced hcp 22 23
The arguments tell the stacker to randomly build north hands that are balanced with high card points in the range of 22 and 23.

Any shape class can be used in the place of balanced, and any holding procedure can be used in place of hcp in the above example. If an evaluator is not passed in, there is no range requirement. If you wish no shape restrictions, use the shapeclass AnyShape.

Specific cards can still be placed in specific hands:

        deal::input smartstack north balanced hcp {20 21}
	south is K52 KJ3 98542 AK
        north gets AS QS QH
Smart stacking can also put restrictions on specific suits:
deal::input smartstack north balanced hcp 20 21
smartstack::holding diamonds controls 2 3
This requires north to have 2-3 controls in diamonds.

The tighter the restrictions, the faster Deal will be able to build hands which satisfy them.

Any additional conditions you want to place on any of the hands can still be placed in main, as usual.

Performance issues

Smart stacking costs a lot of initial overhead. For example, on my Linux computer, ex/1-shapeclass.tcl in the release has no startup time, and takes about 0.014 seconds per match found. The equivalent script using smartstack, ex/1-stack.tcl, takes almost 13 seconds at startup time, but then takes onlu 0.002 seconds per match found. So if I'm generating 10,000 with these deals, it takes about 36 with smart stacking, and about 140 seconds without. But if I'm generating 1,000, they take about the same time, and if I'm generating only 10, using smart stacking is costly.

Is smart stacking ever useful when dealing with small sample requests? Definitely - if the hand is *very* specific and/or rare. For example, the two above scripts use a point range of 11-15, but if they are changed to seek 21-22 hcp hands of the same shape, they both take about 10 seconds to find 10 deals, but the smart stacker takes only 14 seconds to find 1,000, while the standard algorithm takes 1,000 second!

Originally, I was going to call the "smart stacker" by the name, "deal factory." Like a real world factory, there is a large startup cost, but after it is built, it builds deals to specification far faster. The more specific your needs and/or the larger supply you need, the more useful that initial investment is.

If I use smartstack to generate balanced hands with 20 points, it has a startup time of about 20 seconds. If I request balanced 25-counts, 17 seconds, balanced 29-counts 12 seconds. After startup, the amount of time to find examples is almost nil. Without smartstack, it takes about five minutes to generate ten examples of balanced 29-counts. With smartstack, only 13 seconds.

For the evaluator, don't use one that has too many possible values, or the size of the stacker's table balloons horribly. For example, in each suit, the values possible for hcp are 0-10. But if you were to use something really complex with floating point values, you might screw the pooch. No smart checking is applied when building the table, either, so Deal might just appear to churn.


Silhouette Thomas Andrews (thomaso@best.com) Copyright 1996-2002. Deal is covered by the GNU General Public License.

Plane Dealing graphic above created using POV-Ray.