[Computer-go] MC in games of imperfect information

Jonas Kahn jonas.kahn at math.u-psud.fr
Fri May 14 11:41:27 PDT 2010


On Fri, 14 May 2010, Nick Wedd wrote:

> In message <960661D6-7942-4CD5-BB94-8B11518DFF60 at gmx.ch>, Isaac Deutsch 
> <ibd at gmx.ch> writes
>> Hi all,
>> 
>> I'm thinking about creating a computer player for Tichu 
>> (http://en.wikipedia.org/wiki/Tichu), a game that is rather widespread here 
>> in Switzerland. However, to my knowledge there exists no official bot that 
>> plays it. Someone I know has created a bot that plays using rules only (if 
>> X, play cards YZ), but his findings were that the bot plays pretty weak.
>> 
>> Of course, the game is solvable when there are only 2 players left because 
>> then, the distribution of cards is clear and the best strategy can be 
>> calculated.
>> 
>> With 3 or even all 4 players still in the game, it is clear that it is not 
>> clear which player has which cards. :) It is a game of imperfect 
>> information. I was wondering if Monte Carlo (MC) can and should be used at 
>> this stage of the game. It seems that there has been some success of MC in 
>> poker.
>> If yes, how would MC be used? When a move is to be made, should all legal 
>> moves be generated, and should a number of playouts be simulated for each 
>> (1-ply MC)? What do the playouts look like? Give all players (weighted) 
>> random cards, then play the game out with deterministic rules? Give all 
>> players (weighted) random cards, then play the game out (weighted) 
>> randomly? I'm pretty much just trying to think of something based on what 
>> 'works' in Go. :) Because of the uncertainty in the distribution of cards 
>> gives so many possible combinations, it seems impracticable to create a 
>> tree with all possible distributions.
>> 
>> If no, what alternatives are there? Neural networks?
>
> Tichu is far closer to bridge than to Go, or Poker.  There has been some 
> successful work on programming bridge.  I suggest you talk to a bridge 
> programmer.  I don't know any, but there is at least one who follows the 
> usenet group rec.games.bridge.

As far as I have understood, bridge programs would indeed use a MC
approach.
Typically, they will simulate 100 hands coherent with the information
they have. They then build the whole minimax tree with total information
(as if everybody knows everybody's hands) for each of these hands, and choose the card with the best mean result, or that which gives the contract most often. At the beginning, they might not build the whole tree but play a few cards in the simulation using heuristics, but they will build it when each player has ten cards.
If they had much more computing power, they would make simulations where
the players do not know the other hands (I think these are called ┬źdouble dummy┬╗), but that means that after the first card is played *in the simulation*, the other simulated players have to make simulations themselves... More or less the square of the number of simulations is then required.

I think you can find a few explanations on Wbridge5's site, but I would
not swear it.

And here I've yielded all my knowledge.

Jonas



More information about the Computer-go mailing list