Last week I explained why a DSL and genetic programming are such an awesome combination. So, we can almost start to mutate our ACOL code. But, there is one thing we need: a fitness function, a function that tells us we are going the right way.

When mutating a string, we used the Levenshtein distance between the output and our goal. When mutating our rewriting system, we wanted only to select valid rewrite rules. I anticipated people would ask after my F# Exchange talk what a good fitness function was for a bidding system, but I ran out of time, so here goes. There are actually a few options we could try.

Looking at old games

There are a few sites that have old games*, with the deals, the contacts bid and whether or not they were achieved. We could, for example, use the number of games in which we get the same answer as famous players (most of the datasets are world championships and such) and only take into account the games that were actually won. This is a fairly cheap strategy (we only need to read the old games, store them and then run our newly synthesized system)

But…! There are a few buts here:

• Suppose there was a secret way in which we could bid better, we would never find it, because we won’t get better than historical (existing) players
• Suppose a few people in the dataset are good bidders, but bad players (or very very good ones) than there might be bids in the db that are good, but were not executed well (or too good)
• Even though the dataset is big, there might be situations that are not covered and what to do then?

Initially (before I gave it lots of thought) I thought this would be a plan, but I have a better plan now 🙂

Double dummy solver

A simplified version of the game of computer bridge is the called double dummy solving (dds) This is playing a game while you know where all the cards is, i.e. complete versus partial information. This is of course a lot simpler, but, it is very easy to program, there are a dozen implementations on github. So, what we are going to do is the following:

1. We generate one random hand
2. We generate a number of possibilities for the other 3 hands
3. We run the dds on all the above four hands
4. We select the minimum makeable contract**

Now, we have a hand, and a contract that a player should be able to make based on lots of combinations with different hands. Using lots of those and trying to get as close as possible is the goal of the genetic programming for the first step of the bidding system. How I will do the rest

There is a dds for C# already!

As I said, there are a few implementations on github, according to the best one seems to be by Bo Haglund in C++. Luckily, someone already ported it, thanks! It is a bit tricky to rely on someone else’s code of course, so I might make a dds later, but for now it is nice to take it for granted and work on the synthesis.

—————-

* Sadly enough though, there is no one stop shop to get a lot at once, I was not able to find the biggest one I have read about, the mythical GIB dataset which is rumored to have 700,000 files, despite me email the researchers who wrote a research paper using that data. Of course, their university website no longer works. If only they put their data on figshare or github :'(

** We could also take one or two contracts above minimum to be a bit more competitive