On Fri, 14 May 2010, Nick Wedd wrote:
In message <[email protected]>, Isaac Deutsch
<[email protected]> 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
_______________________________________________
Computer-go mailing list
[email protected]
http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
