[madvorak]

Hello!

I am a student of Computer Science at the Charles University in Prague. I am also an enthusiastic bridge player. You can probably guess where this combination of interests leads to ...

My master thesis deals with an artificial intelligence for bridge. Specifically, my goal is to let my computer design its own bidding system without any prior knowledge. I perform experiments with evolutionary algorithms (involving genetic programming and learning classifier systems) for this purpose.

Would you be interested in watching my progress? I think that posting information about my research could increase my motivation to progress faster.

[hrothgar]

madvorak, on 2019-March-02, 02:59, said:

Hello!

I am a student of Computer Science at the Charles University in Prague. I am also an enthusiastic bridge player. You can probably guess where this combination of interests leads to ...

My master thesis deals with an artificial intelligence for bridge. Specifically, my goal is to let my computer design its own bidding system without any prior knowledge. I perform experiments with evolutionary algorithms (involving genetic programming and learning classifier systems) for this purpose.

Would you be interested in watching my progress? I think that posting information about my research could increase my motivation to progress faster.

VERY much so...

You might also considering sharing your progress over at BridgeWinners

FWIW, I'd have a strong personal interest in a very specialized subset of this problem space.

Suppose that you have a a relay auction in which the relay captain know's relay responder's precise shape and minimum strength.
For example, relay responder has just bid 3!D showing a 5=4=3=1 shape

What is the most efficient method to achieve the following goals

1. Signing off in the best game
2. Exploring for slam

[madvorak]

hrothgar, on 2019-March-02, 03:17, said:

VERY much so...

You might also considering sharing your progress over at BridgeWinners

FWIW, I'd have a strong personal interest in a very specialized subset of this problem space.

Suppose that you have a a relay auction in which the relay captain know's relay responder's precise shape and minimum strength.
For example, relay responder has just bid 3!D showing a 5=4=3=1 shape

What is the most efficient method to achieve the following goals

1. Signing off in the best game
2. Exploring for slam

Before I share information about methods that I use, I will add a brief comment on your question.

My algorithm will never explore relay bids. I don't inject any human-created knowledge into the system. I let my algorithms create everything from scratch, using a form of reinforcement learning. And because I decided to use a model-free approach to reinforcement learning, "pure ask bids" cannot emerge.

PS: With a very, very, very low probability, a "pure ask bid" can occur. However, the evolution will not be able to select them by their fitness anytime soon after they appear, so they will most likely die.

[madvorak]

First, I would like to share one funny moment with you.

About 5 months ago, when I finally implemented the learning classifier based genetic programming, I decided to train it on about 200 deals (which is not enough of course) and then test it on 1 deal, only to see the opening bid. I didn't expect any high-quality bidding, I just wanted to see whether it can do something.

pass

I started it again.

pass

I wanted to see, whether it can bid anything else (because always-pass system would be a symptom of either underfitting or implementation bug). So I started it again.

pass

It seemed that it can bid only pass. I started to feel disappointed. However, I started it again.

7NT

Well, it doesn't look like a reasonable opening!

[hrothgar]

madvorak, on 2019-March-02, 04:01, said:

Before I share information about methods that I use, I will add a brief comment on your question.

My algorithm will never explore relay bids. I don't inject any human-created knowledge into the system. I let my algorithms create everything from scratch, using a form of reinforcement learning. And because I decided to use a model-free approach to reinforcement learning, "pure ask bids" cannot emerge.

With a very, very, very low probability, a "pure ask bid" can occur. However, the evolution will not be able to select them by their fitness anytime soon after they appear, so they will most likely die.

Couple quick thoughts:

1. Bids like Stayman, Blackwood, RKCB, and the like are very common in bridge. It will be interesting to see what a bidding system that is purely descriptive looks like.
2. I wonder how well your system will handle stuff like the completion of a transfer which doesn't necessarily show much of anything.

I wouldn't be surprised to see you arrive at something that is better than many existing bidding systems, but significantly worse than what is actually possible.

I admit to having some personal biases, however, I wonder whether you might do better by using a deep learning type approach and allowing your algorithms to start by watching computers and people bid and then start riffing off of various existing systems rather than starting from scratch.

[madvorak]

hrothgar, on 2019-March-02, 04:33, said:

Couple quick thoughts:

1. Bids like Stayman, Blackwood, RKCB, and the like are very common in bridge. It will be interesting to see what a bidding system that is purely descriptive looks like.
2. I wonder how well your system will handle stuff like the completion of a transfer which doesn't necessarily show much of anything.

I wouldn't be surprised to see you arrive at something that is better than many existing bidding systems, but significantly worse than what is actually possible.

I admit to having some personal biases, however, I wonder whether you might do better by using a deep learning type approach and allowing your algorithms to start by watching computers and people bid and then start riffing off of various existing systems rather than starting from scratch.

Thanks for your thoughts!

1. I am also interested!
2. I think it will not develop transfers at all. Maybe I am wrong.

Application of a deep learning to bridge bidding is certainly a good idea! Recently (2016) there was made a great breakthrough in this area. See this paper:
https://arxiv.org/pdf/1607.03290.pdf

However, the method (DRL from the paper) has its limits. I will probably not be applicable to competitive bidding. Since the algorithm learns each sequence separately by Q-learning, it can't learn more general and abstract rules. This is a major obstacle. In competitive bidding, there are way too many possible sequences (they are there inherently; and what's worse, the algorithm cannot choose to limit the length of the bidding as it did with 4 bid limit in pure NS bidding). There will never be enough training data to learn every sequence from them. For comparison, real bridge players (people) don't learn each sequence separately. They use analogies.

My work focuses on creating generalized rules. I hope that my program will be able to perform in a competitive bidding, at least to some degree. I decided to use evolutionary algorithms. However, it is highly possible that deep learning is also useful for this purpose. For example, I could use evolution for exploration and generalization of bidding rules and then I could use deep learning for fine tuning of parameters (without creating nor destroying existing rules).

[nige1]

madvorak, on 2019-March-02, 02:59, said:

Hello!I am a student of Computer Science at the Charles University in Prague. I am also an enthusiastic bridge player. You can probably guess where this combination of interests leads to ...My master thesis deals with an artificial intelligence for bridge. Specifically, my goal is to let my computer design its own bidding system without any prior knowledge. I perform experiments with evolutionary algorithms (involving genetic programming and learning classifier systems) for this purpose.Would you be interested in watching my progress? I think that posting information about my research could increase my motivation to progress faster.

Good luck with your enterprise, madvorak. Genetic algorithms feature throughout the history artificial intelligence, Many forum-members would would be interested in progress-reports, here. Perhaps you could record tentative call-meanings in Kungsgeten's BML: Bridge Markup Language to facilitate human understanding.

[pescetom]

This is fascinating and we're all waiting to see what emerges and whether or not relay sequences will prove advantageous (like others here I take it for granted that blind "transfers" will not).
I think that a good part of the future of bridge is in the balance here: not so much in whether an AI-AI partnership can beat the best humans (I take it for granted) but in whether there can be any common ground in terms of communication of agreements (which is already at it's limits between humans) and as a consequence whether agreements can be left completely free and disclosed or not.

[helene_t]

We had a long discussion about this: https://www.bridgeba...ed-by-computer/

While ot didn't lead to any playble systems, you might get some inspiration from that thread.

You might also start with a less ambitious goal. Rather than letting the computer design an entire system, letting it design for example the follow ups to a 3nt overcall after opps' preempted.

[thepossum]

madvorak, on 2019-March-02, 02:59, said:

Hello!

I am a student of Computer Science at the Charles University in Prague. I am also an enthusiastic bridge player. You can probably guess where this combination of interests leads to ...

My master thesis deals with an artificial intelligence for bridge. Specifically, my goal is to let my computer design its own bidding system without any prior knowledge. I perform experiments with evolutionary algorithms (involving genetic programming and learning classifier systems) for this purpose.

Would you be interested in watching my progress? I think that posting information about my research could increase my motivation to progress faster.

Very much so. I am doing my own personal (unaffiliated, self/unfunded and non profit) "research" into data science, machine learning, AI, other predictive statistical methods, psychology etc. and bridge. I try to stay on top of all the researchers in the field and would be very interested in progress

I have many of my own ideas, some of which I share informally on forums, but would not like to bias your research in any direction at this stage with research questions, methods, limitations etc

Good luck with your research

regards P

[madvorak]

nige1, on 2019-March-02, 09:30, said:

Good luck with your enterprise, madvorak. Genetic algorithms feature throughout the history artificial intelligence, Many forum-members would would be interested in progress-reports, here. Perhaps you could record tentative call-meanings in Kungsgeten's BML: Bridge Markup Language to facilitate human understanding.

I am afraid that my program will not be able to export its bidding system in such a simple form.

[madvorak]

helene_t, on 2019-March-02, 16:01, said:

We had a long discussion about this: https://www.bridgeba...ed-by-computer/

While ot didn't lead to any playble systems, you might get some inspiration from that thread.

You might also start with a less ambitious goal. Rather than letting the computer design an entire system, letting it design for example the follow ups to a 3nt overcall after opps' preempted.

Thanks for your comment! I have just read the discussion you mentioned. There are interesting ideas!

I especially like the idea "maybe the algorithm should be tuned to avoid making low-level nonforcing calls that are unnecessary" because it seems that such a change could solve the problems of premature convergence that I have now (in my current program, too many biddings go like 1x - pass - pass - pass).

Thanks for your idea of setting an easier goal! In fact, this is something with a limited state-space (making it possibly easy for computers), but very complicated for me to do it as a human player well (in fact, I am terrible in bidding after opps' preempts). Do you have any idea how I should download/generate training data containing deals where opponents preempted? For example, I might generate random deals and somehow co-evolve a classifier to decide whether to preempt or pass (opponents' strategy). However, it could lead to some unrealistic bidding sequence. I would like to make this based on human data instead.

[madvorak]

thepossum, on 2019-March-02, 16:01, said:

Very much so. I am doing my own personal (unaffiliated, self/unfunded and non profit) "research" into data science, machine learning, AI, other predictive statistical methods, psychology etc. and bridge. I try to stay on top of all the researchers in the field and would be very interested in progress

I have many of my own ideas, some of which I share informally on forums, but would not like to bias your research in any direction at this stage with research questions, methods, limitations etc

Good luck with your research

regards P

Wow, that sounds interesting! BTW, how do you manage to stay on top of all the researchers in your fields of interest, when you are not payed by any university for studying this? Do you spend most of your free time on studying research papers etc?

[thepossum]

madvorak, on 2019-March-03, 03:36, said:

Wow, that sounds interesting! BTW, how do you manage to stay on top of all the researchers in your fields of interest, when you are not payed by any university for studying this? Do you spend most of your free time on studying research papers etc?

I'm lucky to have a lot of free (from deadlines, projects, responsibility etc) time at the moment, over the last year, so have been looking for an interesting personal (non client) research application area that covers all my knowledge bases and multliple interests (bridge, AI, psychology, statistics). I only try to stay on top of a well defined application area and rely on past knowledge and branch out into specific methods, subdiscplines etc. Obviously you cant stay on top of everything but focus on a specific application domain, specific methods to give a very focussed question. Then you can branch out. I'm still only 6-8 months into getting to grips with the latest research in computational bridge then I will define a project. I hope I may be able to contribute to some of the existing projects around the world, even in a small way

It would be good to be paid to do research by a university but its also good being free from confines of universities, funders, deadlines, onerous publication requirements, teaching requirements etc. I have a very small but adequate budget, there are many free sources of information (eg Google Scholar), some of the people in the field share their methods and code with Open source licenses, and I have a couple of professional online databases to access for some things, and of course the local library, and my personal library and memory.

The main thing it needs is time and interest/motivation and I have plenty of that at the moment and it helps to have many years in different fields behind me. I would never claim to be on top of everything except at a broad level and then dive deep into specific application areas. AT the moment I have an initial list of about 200 papers to get through

Hope that makes sense.

Your bidding project sounds interesting but extremely challenging given the nature of the game and how humans developed bidding systems over the years. I would be very interested to hear how you go trying to get learning to produce a bidding system (even a basic one). The biggest challenge in bridge I think is the number of hands needed on top of the complexity of the game itself and the multiple information sources bridge players use to compensate for incomplete information. Without giving too much away my main interest at the moment (without specific RQs) is application of alternative AI approaches to play to augment, improve or replace the DD approach to play. So I'm drawing on different fields and methods. Getting to grips with some of the recent literature is enough for me at the moment but I started off with Ginsberg, Gitelman, GiB and worked on from there to start to understand the field.

Sorry for waffling a bit. Its late here.

regards P

[madvorak]

thepossum, on 2019-March-03, 04:54, said:

I'm lucky to have a lot of free (from deadlines, projects, responsibility etc) time at the moment, over the last year, so have been looking for an interesting personal (non client) research application area that covers all my knowledge bases and multliple interests (bridge, AI, psychology, statistics). I only try to stay on top of a well defined application area and rely on past knowledge and branch out into specific methods, subdiscplines etc. Obviously you cant stay on top of everything but focus on a specific application domain, specific methods to give a very focussed question. Then you can branch out. I'm still only 6-8 months into getting to grips with the latest research in computational bridge then I will define a project. I hope I may be able to contribute to some of the existing projects around the world, even in a small way

It would be good to be paid to do research by a university but its also good being free from confines of universities, funders, deadlines, onerous publication requirements, teaching requirements etc. I have a very small but adequate budget, there are many free sources of information (eg Google Scholar), some of the people in the field share their methods and code with Open source licenses, and I have a couple of professional online databases to access for some things, and of course the local library, and my personal library and memory.

The main thing it needs is time and interest/motivation and I have plenty of that at the moment and it helps to have many years in different fields behind me. I would never claim to be on top of everything except at a broad level and then dive deep into specific application areas. AT the moment I have an initial list of about 200 papers to get through

Hope that makes sense.

Your bidding project sounds interesting but extremely challenging given the nature of the game and how humans developed bidding systems over the years. I would be very interested to hear how you go trying to get learning to produce a bidding system (even a basic one). The biggest challenge in bridge I think is the number of hands needed on top of the complexity of the game itself and the multiple information sources bridge players use to compensate for incomplete information. Without giving too much away my main interest at the moment (without specific RQs) is application of alternative AI approaches to play to augment, improve or replace the DD approach to play. So I'm drawing on different fields and methods. Getting to grips with some of the recent literature is enough for me at the moment but I started off with Ginsberg, Gitelman, GiB and worked on from there to start to understand the field.

Sorry for waffling a bit. Its late here.

regards P

Wow, you are awesome!

As for the double-dummy approach and number of hands needed, the good thing is that double-dummy analyses can be pregenerated (since calculating the result of the deal for all contracts takes about 700 ms, but loading the deal with results from hard drive takes less than 1 ms). Therefore, I can use a fixed (big) pack of pre-generated deals and experiment with various algorithms on them. However, when I want to see the result of my evolution, despite many optimizations it takes almost and hour for my computer to evolve the system. However since this Friday, I have obtained an access to computers at the university, so I will be able to run my program on several computers in order to test several versions/settings of my algorithm at the same time.

At the moment, I am studying papers about Michigan style strength-based learning systems vs Michigan style accuracy-based learning systems.

[helene_t]

madvorak, on 2019-March-03, 03:34, said:

Do you have any idea how I should download/generate training data containing deals where opponents preempted? For example, I might generate random deals and somehow co-evolve a classifier to decide whether to preempt or pass (opponents' strategy). However, it could lead to some unrealistic bidding sequence. I would like to make this based on human data instead.

There is open source available for double dummy analysis. So I would just generate a million random hands and run them through a double dummy solver.

As for the (3 bananas)-3NT-pass-? problem, you would have to decide what a 3NT bid looks like. Maybe 16-22 HCPs, stopper in opps' suit, no 6-card major. Or something like that.

For the experiments I did for the purpose of the thread, I didn't even bother to DD solve the hands but just made a crude formula for the number of tricks you can take a a function of HCPs and trumps. This is probably not good enough for an M.Sc. thesis, but I was OK with it because there were obviously bigger problems with my algorithm than the minor issue that I had used a crude formula for the number of tricks

[madvorak]

helene_t, on 2019-March-03, 05:39, said:

There is open source available for double dummy analysis. So I would just generate a million random hands and run them through a double dummy solver.

As for the (3 bananas)-3NT-pass-? problem, you would have to decide what a 3NT bid looks like. Maybe 16-22 HCPs, stopper in opps' suit, no 6-card major. Or something like that.

For the experiments I did for the purpose of the thread, I didn't even bother to DD solve the hands but just made a crude formula for the number of tricks you can take a a function of HCPs and trumps. This is probably not good enough for an M.Sc. thesis, but I was OK with it because there were obviously bigger problems with my algorithm than the minor issue that I had used a crude formula for the number of tricks

OK. How do you decide which deals are opened by 3 bananas from the opponent? I don't have trouble generating DD results. I have trouble selecting the deals if I want to do this specialized analysis.

[thepossum]

madvorak, on 2019-March-03, 05:38, said:

Wow, you are awesome!

Thanks but it's not so much awesome as frustrating that I end up using my skills and experience modelling a card game rather than my previously chosen preferred fields. Something of a reflection on society and attitudes to funding socially valuable research.

But it's fun and more relaxing than stressing over deadlines

I'm also interested in different predictive models for players taking account of different strengths and weaknesses of players, different hand types, competition type, other attributes but I don't really have a database for that yet. Have been testing the concept on my own hands.

I think a good robot player eventually needs to learn from its opps and change its behaviour according to contexts

And it clearly can't rely on DD type simulation alone. It needs to understand the game, tactics, strategies, behaviour, patterns of hands and play. DD is very basic

Some of the better players are doing more advanced plays but I don't know if they genuinely learn and plan them or if they are just artefacts of better or deeper simulation

Also to be a truly AI player it needs to explain its bids and plays. When a bot can explain its bid and play to a human it is closer to AI

But many apologies. Those are my areas, not yours. Good luck with your bidding and ML. I'm not so deep into the ML at the moment as other aspects so can't really comment directly on your approach.

Regards P

[Lorneg]

Good luck with your endeavour. I worked in that world for 42 years and the changes
that have been made in programming are unreal.

I would like to see the Robots on BBO get smart some day. Today they just
follow a bunch of rules. I keep looking for a Robot that can work from my CC.
Is that possible??? Yes but you need the will to make it happen.

[kellonius]

madvorak, on 2019-March-02, 02:59, said:

Hello!

I am a student of Computer Science at the Charles University in Prague. I am also an enthusiastic bridge player. You can probably guess where this combination of interests leads to ...

My master thesis deals with an artificial intelligence for bridge. Specifically, my goal is to let my computer design its own bidding system without any prior knowledge. I perform experiments with evolutionary algorithms (involving genetic programming and learning classifier systems) for this purpose.

Would you be interested in watching my progress? I think that posting information about my research could increase my motivation to progress faster.

Thanks for sharing, sounds interesting.

Out of curiosity what happens when this is treated as a supervised learning problem, e.g. learn to predict what the experts bid?