levb
New Member
Posts: 18
|
Post by levb on Mar 12, 2014 12:27:00 GMT -8
I see some game-theory games have appeared on Tiltyard, e.g., Iterated Prisoner's Dilemma. Nothing we have learned seems applicable here.
Does anybody have any idea how to deal with these? How to recognize them?
Some general thoughts: Recognize specifically Repeated Prisoner's Dilemma and implement Tit for Tat. But Tit for Tat only works well if the opponents have sensible strategies. These games require assessing the opponent's strategy. Such assessment is useful in other games, too. The Centipede Game is not very interesting, because it doesn't let a player assess the opponent's strategy.
|
|
levb
New Member
Posts: 18
|
Post by levb on Mar 12, 2014 12:34:26 GMT -8
My player tends to lose to Quixote but, surprisingly, win over GreenShell in game-theoretic games.
|
|
|
Post by Sam Schreiber on Mar 12, 2014 14:32:39 GMT -8
I have no idea how to deal with these games. That's why I added them. :-)
I think that it's not enough to just recognize things like Nash equilibria; these games are really about "playing your opponent" rather than just "playing the game." One needs an interesting sophisticated opponent model. Or something.
Also we can definitely incorporate game theory elements into ordinary strategic games (like Connect Four, Tic Tac Toe, Knight-Through) so I'm personally avoiding the approach of "if it's a game theory game then do X otherwise do Y". I'm hoping to come up with a gaming algorithm that works for ordinary strategic games and also game theory games.
|
|
|
Post by Steve Draper on Mar 13, 2014 10:01:53 GMT -8
I handle them slightly cheesily in Quixote/Sancho. It heuristically detects iterated games, then assumes the opponent will use a more-or-less consistent strategy profile, but the same one every turn. It then looks for a good strategy profile to use itself and just runs the iterated game simulation using the profiles it is searching on, so that the only thing it needs to evaluate is the (extremely rapidly findable) end result. It does adjust its strategy weights as the game goes along, based on changing its model of the opponent's strategy as it sees the opponent's moves. This is an extremely simplistic special-case routine for iterated games - totally separate code from any other game type (all they have in common is state machine implementation machinary)
|
|
levb
New Member
Posts: 18
|
Post by levb on Apr 20, 2014 2:01:02 GMT -8
|
|
wat
New Member
Posts: 32
|
Post by wat on Jun 8, 2014 15:33:32 GMT -8
I was also thinking about how to implement tit-for-tat in GGP.
As far as I know, it IS about recognizing Nash equilibrium. But these games have multiple Nash equilibria, tit-for-tat being only one of many.
The trick is how to make MCTS converge to the Nash equilibrium you want. Simply doing UCT evaluation makes MCTS converge to a random Nash equilibrium, which is rarely tit-for-tat.
|
|