GIB Suggestion

[glen]

I see there could be, at some future time, improvements to GIB – see:

 

BBO Help Wanted Thread

 

a# Decipher & document the GIB "bidding database"

b# Construct tools to measure & improve GIB performance

c# Maintain and enhance the GIB engine/database

For these software updates, I was wondering if GIB’s artificial intelligence might be enhanced by using a level of abstraction. For an example reference on this, see:

 

A grounded theory of abstraction in artificial intelligence - Jean-Daniel Zucker

 

I’ll just focus on the bidding, and I should mention that I haven’t kept pace with all of GIB’s improvements over the last few years, so I’m using Ginsberg’s "GIB: Steps Toward an Expert-Level Bridge-Playing Program" 1999 paper as a base line.

 

One possible abstraction would be for a second double-dummy engine to treat all spots under the 9 as x, and if only x’s are played on a trick, then the last player to the trick wins. This would mean that the double-dummy analysis will not be perfect on each hand, but for helping out the bidding it should be quite sufficient. By treating all spots under the 9 as x, the transposition table etc. of this 2nd engine would be able to speed up the processing.

 

The bidding component would then use this second double-dummy engine with Monty Hall* sampling to determine the approximate number of tricks that could be expected for each of the bids partner is likely to make. The bidding component would bias, or weighted, each sampling result based on how close the sample seems to the average expected holdings for the other three players, based on the bidding so far, and partner’s potential bids. For example, in the uncontested auction of 1♣-2NT(11-12);-?, GIB, the opener, would do various samples, weighting the results towards average hands that the opponents would have for passing. Then it would decide whether to pass, or what bid it should select for the next step forward. With lots of computing power, one could even use this method for opening bid decisions, or at least into research on this subject.

 

Now if one does a google search on {"artificial intelligence" uncertainty probabilistic heuristic} one gets 223,000 hits, so there is certainly a lot of continuing research into these areas. For example selective sampling is discussed in:

 

Using Probabilistic Knowledge and Simulation to Play Poker

 

which references Ginsberg’s paper.

 

* gaming variation of the more common name

[NickRW]

One possible abstraction would be for a second double-dummy engine to treat all spots under the 9 as x, and if only x’s are played on a trick, then the last player to the trick wins.  This would mean that the double-dummy analysis will not be perfect on each hand, but for helping out the bidding it should be quite sufficient.

 

This is interesting.

 

Using Probabilistic Knowledge and Simulation to Play Poker

 

which references Ginsberg’s paper.

 

I am familiar with the work of Darse Billings and others. I think their use of selective sampling, certainly in their earlier bots, was to the extent that they would weight likely possible opponent hole card combinations based on prior observation and then simulate likely play from that point on again using observed characteristics of that opponent. So in other words, there was no treating cards as 'x' as such. There was selection or weighting of likely opponent hole cards. Never the less any (valid) simplifications, assumptions or inferences that can be drawn seem to improve these things.

 

Nick

[NickRW]

From Ginsberg's paper:

 

8.3 Other games

I have left essentially untouched the question of to what extent the basic techniques we have discussed could be applied to games of imperfect information other than bridge.

 

The ideas that we have presented are likely to be the most applicable in games where the perfect information variant is tractable but computationally challenging, and the assumption that one’s opponents are playing with perfect information is a reasonable one. This suggests that games like hearts and other trick-taking games will be amenable to our techniques, while games like poker (where it is essential to realize and exploit the fact that the opponents also have imperfect information) are likely to need other approaches.

 

This assumption is/was a good one in improving the standard of bridge playing programs (compared to what existed pre-GIB). It is not necessarily a good one if one wishes to make a truly expert bot.

 

Nick