Bridge and Genetic Algorithms

[EricK]

What aspects of computer bridge (or just bridge in general) could be helped with the use of genetic algorithms?

 

Could one use them to evolve a hand evaluation system (not just for initial valuation but also one which changes as the bidding progresses)?

 

What about evolving a whole bidding system? (But would the resultant system even be understandable by a human?

 

What about evolving a bidding system which has to eg accord to the ACBL General Chart?

 

What about card play?

 

Has anybody tried to do any of these?

[awm]

Jason Woolever's Masters thesis from MIT involved using genetic algorithm to search for an effective bidding system. I can't seem to find a copy online, but anecdotally the result was a fairly simple system where the final contract was generally reached by opener's rebid. Complicated sequences and methods simply didn't evolve.

 

As best I can tell (and I am a professor of computer science), genetic algorithms are really just a buzzword for a particular search technique which isn't dramatically different or more effective than the various other search techniques found in the AI literature. The problem with applying any such search to bidding in bridge is the difficulty of evaluating the "fitness" of a particular set of methods, as well as the vast space of methods to explore. In order to really evaluate a "system" you need to bid (and somehow solve) an immense number of hands (since any particular sequence will be unlikely to show up, and a method which is good in general might reach a high-percentage contract which happens to go down, etc). Even with a huge library of double-dummy solved hands, it's impossible to gauge the amount by which information conveyed will help the opposing side, or the effect of various forms of interference on the methods.

 

It might be possible to do better with card play, but to be honest GIB is a pretty good single-dummy card player. The main weaknesses of GIB (at a reasonable time setting anyway) involve inferences from the bidding, tempo, choice of lead, and subsequent defense. This is obviously going to be a hard part for a computer to "get" and various search techniques are unlikely to help much.

[Flame]

I dont understand any of this but this might be related http://www.cs.technion.ac.il/~shaulm/paper...t-2005-LBB.html

[helene_t]

I once made a very simple experiment on this, when only the bids pass, 1NT, 2NT and 3NT were allowed, only on the basis on crude HCP, and only uncontested auctions. The awards for different contratcs as a function of combined HCP were taken from 750,000 DD hands.

 

The system very quickly (some 30 generations) evolved into what you would expect, including lighter openings in 3rd4/th seat and more aggresive game bidding when vulnerable.

 

I've given a lot of thoughts on how to proceed further. The main problem is, I think, to find a formalism for a bidding system, which satisifies

- General enough to include some interesting bidding principles

- Not too complex

- Does not rely on my own knowledge about what the solution should look like: I'd like to see completely bizare, unexpected systems to evolve, if they are effective.

- Evolvability, the effectiveness should be a (near) continous function with a (near) single-component image in mutation space

 

One inspirating remark was made by Todd: the bidding system should not be described in terms of rules for how to handle specific auctions but in terms of some principles for how to construct the decision tree given an auction.

 

This is what I suggest: first, the auction is reduced to the following set of descriptive parameters (the below is incomplete but would do for a start):

- The height and denomination of the last bid made (pass through 7NT)

- By our side or their side?

- Plain, doubled or redoubled.

- Will partner get a new turn if I pass?

- What has partner promissed (e.g., HCP range and length ranges)

- What have I promised.

 

Now the bidding system is an algortihm which, given specific values of the above parameters, generates a decision tree which decides on a call given a hand.

 

The beauty of this principle is that if the decision tree uses the same parameters as are used for the "promiss" parameters, the generation of the instantiation of the "promiss" parameters is automatic so that no bidding misunderstanddings can ever occur. Also, whenever a mutation changes the meaning of a call, the way partner handles the new meaning is automatically adapted because his response is not based on the call itself, but on its meaning.

 

What remains is a set of parameters (the "genome" of bidding system) that control how the decision tree is build.

 

Btw, thanks for the link, Flame, it looks very interesting.

[barmar]

It's always seemed to me that game playing is very amenable to genetic algorithms. awm mentions the difficulty in evaluating the fitness, but that's relatively straightforward: play a tournament between pairs using the different systems. You could have a round-robin tournament where the number of descendants is based on the position in the final results, with crossing-over (i.e. sexual reproduction) between the top systems. Or perhaps run it as teams of 4, and perform crossing-over between the pairs in the top teams.

 

Sure, sometimes random factors will cause better systems to lose. But that's just like real-world natural selection -- sometimes members of a population with better genes get hid by a bus. But the better genes should survive in the long run.

 

The main problem with this is that it will be slow. To get decent results you'll want matches of at least 32 boards, preferably 64 or 128. And at 2 minutes/board, say, you're talking an hour per match. A full round-robin among 8 teams would require 56 matches, so that's about 3 days of computer time per generation. But it's also amenable to parallelization -- unlike real world bridge, the same "pairs" can be playing in multiple concurrent matches, and on multiple teams.

[hotShot]

It's always seemed to me that game playing is very amenable to genetic algorithms. awm mentions the difficulty in evaluating the fitness, but that's relatively straightforward: play a tournament between pairs using the different systems.

What you describe is a competition between implemented bidding systems.

My impression was that the question was about developing a new bidding system using genetic algorithms.

This would require a fitness function that allows to evaluate each bid. Your target is to hit the best playable contract, the fitness function has parameter like HCP, distribution and the submitted information about partners hand.

How will you evaluate a sequence like:

1♣ - 1♥

What is the best contract and on what level should it be played?

Without knowing strength and full distribution of partners hand, it seems hard to evaluate.

So this evaluation function, will induce a set of rules, that are optimised by the process.

Conventions like Jacoby 2NT, Bergen Raises, Blackwood or Stayman could only evolve in this process by mutation, and they must be kept alive long enought to reach the right contract. But how do you change the fitness function so that these sequences are better than plain natural bidding?

 

To the original question:

If you define a bidding system, you should be able to optimise HCP-ranges for bids and evaluation of distributional strength.

You might end up with a system that gives (just guessing):

A = 5.8

K = 3.9

Q = 1.6

J = 0.3

T = 0.1

void = 2.8

...

Would you find that usefull?

 

A new bidding system will not come up this way.

 

Double-dummy solvers are perfect (but slow), there is nothing to optimise.

Single-dummy agents, are guessing hands and use double-dummy solvers to find the right move for these. The card that is best in most of the guessed distribution is played. I don't think using genetic algorithms can do better here.

[hrothgar]

You've opened a big can of worms... I'm not saying that this is a bad thing, rather that there's a lot of ground that needs to be covered here. There have already been a number of good posts, however, I'd like to make a couple minor points:

 

I've seen a number of quite ambitious projects fail because they bit off more than they could chew. For example, part of Ginsberg's work on GIB was an attempt to automatically generate a bidding system using a combination of monte carlo simulation and his double dummy engine. From my perspective, the output of this experiment looked rather dubious. (Ginsberg eventually shelved the efforts)

 

Personally, I think that people would be better served if they dipped their foot into the pool and tested the water before trying a double gainer off the high board...

 

For example, Barry posited a much simplier problem that (probably) needs to be solved first: How should one go about creating an "arena" in which different bidding systems can compete with one another? In a sense, one would like to recreate the work that Axelrod did with iterated prisioner's dilmena low these many years ago. (As I noted in the past, I'd be very interested in understanding whether the equilibirum was a single bidding system or a optimal ratio between bidding systems)

 

In a similar fashion, rather than looking at the entire bidding "space", it might be worthwhile to focus on a single small/well defined problem. Once you've come up with techniques that can solve the simple case, you can start considering more complex issues. One option jas already been addressed: Take the bidding as a "given" (for example, restrict all programs to 2/1 GF) and simply focus on different types of hand evaluation metrics. Alternatively, one could move to the opposite extreme and look at a limited module within an existant bidding system. (Assume that everyone is playing a relay method that resolves shape according to some known formula... Study the most accurate system for auction termination and placing controls)

[barmar]

It's always seemed to me that game playing is very amenable to genetic algorithms.  awm mentions the difficulty in evaluating the fitness, but that's relatively straightforward: play a tournament between pairs using the different systems.

What you describe is a competition between implemented bidding systems.

My impression was that the question was about developing a new bidding system using genetic algorithms.

No, I was suggesting that the competition be used by the genetic algorithm to select which system should be allowed to reproduce. The development of a new bidding system will come about from mutation and cross-over that occurs during reproduction.

 

Whether this just develops a system by combining known conventions, or develops entire new conventions, depends on what you use as the "genes". Which is, of course, the hard part of any genetic algorithm -- you need to give it enough building blocks so that it can combine them to produce a useful result. This is where restricting the scope comes in, as Richard points out. If you confine your work to a single aspect, it's much easier to define what the genome for that computation should look like.

 

If you have different groups working on defining genomes for different parts of the game, you could then combine them to allow further evolution of complete bridge players (much like the way cells evolved by engulfing mitochondria and chloroplasts).

[DrTodd13]

I think others have pointed this out but I don't think you need genetic algorithms to handle the play of the hand. We have super-fast double-dummy solvers and you can combine that with generating a sufficient sample of likely hands to determine how to play the hand. So, the GIB approach in this regard is probably optimal. The more hands you can simulate the better. With regards to a bidding system being developed genetically, you need a way to represent hand types and systems. Like in FD, the answer to this is that a bidding system is basically a tree. For each bidding system you have, you compare them with thousands of hands (the more the better) and measure how close they get to the par contract. The closer to the par contract the better the system is. You could either have a fixed way to define hands with fixed values for high cards, shortness, etc. or you could genetically evolve that as well.

 

Now for the problems! Cross-breeding of similar bidding systems might yield a reasonable system but cross-breeding of unlike systems would generate an unusable system. Imagine pasting a portion of a forcing pass tree into a SAYC tree. I guess you'd need some complicated rules about what kind of pastes were allowed but how you do this is not clear. Then arises the problem of irreducable complexity. It may require several simultaneous mutations to get a benefit. The odds of these simultaneous mutations may be so low as to be effectively impossible. Another big problem is that if you want your system to handle interference then the system tree explodes. The size increase would be roughly (# of possible competitive auctions * # of possible different meanings for each competitive bid)/(# of uncontested auctions). You would want the ability to respond differently to a capp overcall versus a dont overcall and you need a way to differentiate them.

 

In theory, none of these obstacles are insurmountable given sufficient time and compute power. The problem may be a practical one. It might take thousands of years before you got a system out that was even remotely competitive and then it might be impossible to remember because human instinctly design systems to be rememberable whereas a genetic algorithm would not.

[hrothgar]

If you have different groups working on defining genomes for different parts of the game, you could then combine them to allow further evolution of complete bridge players (much like the way cells evolved by engulfing mitochondria and chloroplasts).

Barry just brought up another good point that I was debating whether or not to introduce. Oh well, pandora's box has been opened.

 

Harken back to the whole "Intelligent Design" discussion and some of the running commentary about bacterial flagellum and whether anything this complex could evolve. Most of the evolutionary pathways posited for complex systems like flagellum and the like posit that these systems get cobbled together out of precursors that served some other purpose. (Barry's example about mitochondria and cloroplasts transitioning from independent living organisms through some system of mutualism/symbiosis until (eventually) they are considered part and parcel of the same organism.

 

Returning to the world of bridge, its unclear to me the level at which we want this "evolution" take place...

 

At one extreme, we could create a system in which you have random bridgebots sitting in the primordial ooze that do nothing but pass. We start introducing mutations, and suddenly one of the bots thinks that its a good idea to open 6♣ any time that it has a 4=5=1=3 hand with 12-16 HCP. This bot quickly dies out. A while later, another bot springs up which thinks that it should bid 2♣ any time that it has 6+ clubs and 14-20 HCP. This bot actually does fairly well, since 2♣ scores better than pass. Run this type of system long enough and you'll probably end up with an interesting looking "natural" bidding system with lots of non-forcing bids. You might even see some strong club systems evolve. In theory, opening 1♣ with a "strong" hand might score better than passing

[barmar]

The thing about genetic algorithms is that unlike the real world, there *is* an intelligent designer who can guide things. It doesn't start de novo, we can choose what raw materials to provide it. We can also start from an already-developed baseline, like Precision or 2/1, and then evolve improvements to it, much like geneticists working with fruit flies. If the raw materials don't include random bids having arbitrary meanings, you should get a system that humans can understand; if the genome is allowed to assign any meaning to any bid, then you might end up with a totally artificial, heavily coded system that would be impossible for flesh and blood to use. Similarly, if you don't constrain the hand evaluation algorithm, it might evolve something that requires a calculator.

 

My suggestion of running tournaments to determine fitness does indeed slow things down considerably. If we just wanted to develop bidding systems, we could probably do it with a database of thousands of hands and their par contracts, and just count how often it reaches par.

 

As DrTodd pointed out, we already have pretty good algorithms for declarer play and defense. So from a practical point of view there's not much point to evolving this. But I think it would still make an interesting AI exercise. The monte carlo method is obviously different from how we declare, and I would be interested in seeing what a genetic algorithm could come up with. The hard part of this is defining the genetic code -- how do you encode the pattern recognition techniques and the consequent actions (e.g. when there's a tenace, try a finesse if you need an extra trick)? Nature didn't evolve declarer play, either; it evolved a general purpose pattern recognizer (the vertebrate brain) and a particular version of it with advanced planning capabilities (the human brain), and then the human brain invented bridge as something it could process. Not everything can be produced by evolution, it can only create things that occur by gradual modification from existing raw materials.

[helene_t]

I agree with Richard that one should start with some simpler problems. Maybe machine learning pricinples could invent the optimal defense against a gambling 3NT opening, or the optimal continuation after a natural weak two opening.

[barmar]

Good point, Helene. In real life, bidding systems don't pop up fully formed, they're created by accretion. Various players develop conventions that address particular situations, and then others adopt them into their repertoire, and so on. So what we should be looking for is the computer equivalent of Eric Kokish; preprogram it with a reasonably standard bidding system, and then see what gadgets it can come up with to improve it.

[hotShot]

No doubt that is you put a lot of conventions in the system that can be swtiched on and off, you can try to optimize it to a "best set of conventions".

No doubt if you set a bidding system you can optimize, hand evaluation or point ranges.

 

But the creation of a new convention seems very hard, though not impossible.

You'd need to allow modification of existing rules and definition of new rules that are used by the bidding engine. The genes in the rules would have to be suitlength, strength etc.. You have to solve the problem of overlapping or even contradicting rules. To have a chance to get rules that contain answers to newly created bids, you would need a lot of randomness, a long survival rate and a big population.

This way simple conventions like transfers (perhaps even simple relays) could evolve.

Limiting it to e.g. 1NT opennings, seems a good way to start.

This could really be interesting, but you would need a LOT of computing power.

[barmar]

A problem with trying to evolve conventions is that they generally involve some logical structure. It's not just a single artificial bid, it's a collection of similar or related bids. For instance, consider something as similar as transfers. It doesn't make sense to just come up with 2♦->2♥ -- logically, this implies that 2♥ should be a transfer to 2♠ as well, and 2♠ should have some other meaning. Similarly, when splinters were invented, what she came up with was the general idea that double jumps show shortness, not a set of specific bidding sequences. You can see the difference if you ever try to create a Full Disclosure convention card -- it forces you to enumerate all the possible bidding sequences that are lumped into a single abstract concept in your brain.

 

But maybe this is similar to the argument that's often made against biological evolution, that the eye couldn't evolve because "half an eye" doesn't work. Maybe there is some benefit to a system that has transfers to ♥ even though it doesn't have transfers to ♠. But once it does have transfers to ♥, there may be more selective pressure to evolve transfers to ♠ as well (however, a system that only has transfers to ♠, without transfers to ♥, is likely to have problems, since it has no way to get to a 2♥ contract, although it can get to 2♦ contracts that standard bidders can never find).

 

It's not impossible for evolution to do this, it just takes time. Think of all the changes that had to occur when we evolved to walk upright: changes in the pelvis, leg bones, neck, arms, etc. all had to be coordinated to get a body plan that worked in the new orientation. But it did happen, and the same thing can conceivably happen with genetic algorithms.

[helene_t]

I agree with your concerns, Barmar. But it's my hope (maybe not well enough thought through, but anyway) that this issue can be solved by describing a bidding system not in terms of the meanings of specifc calls (such as a 2♦ response to 1NT) but in terms of general principles that guide the generation of the decision tree. For example:

 

1) you get an award for making a bid that is likely to be a playable spot, provided that partner is likely to know when it's a playable spot.

2) you get an award for making a bid that is certain to have a higher-ranking playable spot, provided that partner is certain to know that.

 

Suppose (for simplicity) that the tree-generating algorithm works by scanning through all available calls and chosing the meaning with the highest award (this is way too primitive but will do for the sake of this argument).

 

Now, the award given to 2♦ showing hearts is probably higher than the award of 2♦ showing diamonds because it can have more meanings (weak as well as strong hands). Suppose the algorithm choses to let 2♦ show hearts.

 

Next decision to be made is to assign a meaning to 2♥. Since "hearts" was shown by a lower-ranking bid, hearty hands have been eliminated from the set of possible holdings. So 2♥ must mean something else. It's likely that 2♥ will be chosen as meaning spades for the same reason as why 2♦ was chosen as meaning hearts.

[civill]

I think AI engineering of bridge is not direct benefit to the sports of bridge now,but one day,it should be.

With the experiences of mine,AI researching on bridge is good for one's knowledges about bridge.