Arimaa Forum - Print Page


    
      
        Arimaa Forum
        (http://arimaa.com/arimaa/forum/cgi/YaBB.cgi)
      

        Arimaa >> Off Topic Discussion >> Man vs. Machine poker match (polaris)
        
(Message started by: Fritzlein on Jul 23^rd, 2007, 6:24pm)

Title: Man vs. Machine poker match (polaris)
Post by Fritzlein on Jul 23^rd, 2007, 6:24pm

The humans were on the ropes in round one of the Man vs. Machine poker match (http://www.cs.ualberta.ca/~games/poker/man-machine/), and just barely fought back to a draw. Three rounds to go! Which will weigh heavier, the learning ability of the humans, or their fatigue? (Of course, the computers are learning too, and they aren't getting tired...)

Title: Re: Man vs. Machine poker match (polaris)
Post by UruramTururam on Jul 24^th, 2007, 1:18am

Poker against humans is a psychological game. Assuming no cheating the better psychologist wins. Poker against machines is a game of pure chance.

Title: Re: Man vs. Machine poker match (polaris)
Post by arimaa_master on Jul 24^th, 2007, 2:28am

Second game and rather convincing victory for computer - wow!

It seems that human will be ruined even in games with imperfect information (like poker is) - this will be very good for arimaa comunity coz hopefully this will cause more popularity to arimaa thus more people to come to play arimaa :)

But Ururam is quite right - it is mainly about probabilities which should be computed perfectly by computer - but I think that psychology with bets is playing it's role too.

Title: Re: Man vs. Machine poker match (polaris)
Post by chessandgo on Jul 24^th, 2007, 3:33pm

Hey great, thanks for the news, Karl. I completely disagree, UruramTururam, chance has no role to play here, especially since the same cards are delivered (reversed) on the two parallel games, so obviously there's only strategy that matters.
Still, this is limit hold'em, and we'll have to wait that computers get strong at no-limit holdem before claiming that arimaa is the only fun game where humans are significantly stronger than machines besides go :)

Title: Re: Man vs. Machine poker match (polaris)
Post by UruramTururam on Jul 24^th, 2007, 4:11pm

Strategy in poker against machines? It is only calculating the probability that the comp has stronger set and acting accordingly... The only 'strategy' there is finding optimal weights for various types of bids, but it all sums up in a rock/paper/scissors dilemma.

Title: Re: Man vs. Machine poker match (polaris)
Post by 99of9 on Jul 24^th, 2007, 5:32pm

I know a little about rock scissors paper against machines, and much of what I learnt was from Darse Billings (the author of this Poker robot).

Once you've calculated the odds, performing well at R-S-P is about psychology, so is poker.

In RSP, if you play the odds alone (1/3, 1/3, 1/3)-randomly... then you will lose to nobody, but you will also beat nobody. Therefore you do better if you try to sense if your opponent is playing some kind of pattern. If they are, you exploit it, if you can't find one, you play the odds (so that you yourself are not predictable).

In poker, an easy example of this is if you are playing an over-aggressive opponent. Noticing this is vital. However, you might say that a computer is never over-aggressive? Well it would be if it thought you were playing a pattern which could be beaten by aggressive play... so you may be able to sucker it in if you play well.

Jean, unfortunately chance cannot be eliminated completely. Even in a completely *fair* experiment, chance can still play a role in short games, because some strategies require probabilistic play, and you may suffer just because of the random choice you made. After many many games, this effect will reduce.

Title: Re: Man vs. Machine poker match (polaris)
Post by 99of9 on Jul 25^th, 2007, 3:44am

If anyone is further interested by what I mean in the post above, you may like the Myth's section of this page:
http://www.cs.ualberta.ca/~darse/rsb-results1.html

Title: Re: Man vs. Machine poker match (polaris)
Post by UruramTururam on Jul 25^th, 2007, 4:23am

Yes, this is famous "You think than I think than you think than ... so I'll play this way - but I'll play the opposite way!". Surely the optimal strategy in this case is to play randomly and seeking a pattern in the opponents moves then try to exploit this pattern. But if both players play consequently that way no pattern occurs and the game ends in a draw with a statistical margin... If one wants to really win he must assume that other players don't play optimally! But it makes him vulnerable to the ones who do.

Title: Re: Man vs. Machine poker match (polaris)
Post by chessandgo on Jul 25^th, 2007, 5:24am

I'm not sure I get what you mean, Toby. Do you mean that, in an arimaa match between Gnobby and a bot using randomness, their would be some non-fairness due to the random choices which might make the random bot make good or bad moves all the same, this getting uniformed only when the number of games played tends to infinite ?
If this is it, then chance doesn't come from the game of poker itself, or I am completely besides the point ?

Title: Re: Man vs. Machine poker match (polaris)
Post by 99of9 on Jul 25^th, 2007, 6:32am

on 07/25/07 at 05:24:22, chessandgo wrote:

Yes. I wouldn't call it non-fairness, but I would say "chance has a role" whenever a bot has an element of randomness.

Quote:

this getting uniformed only when the number of games played tends to infinite ?

Yes, after many games, it becomes possible to identify statistically significant differences between the two players. This convergence is slightly faster if the hands are paired, which is presumably why they did it.

Quote:

If this is it, then chance doesn't come from the game of poker itself, or I am completely besides the point ?

The difference here between arimaa and poker is that (as Uraram just mentioned), poker demands that you should play somewhat randomly, but arimaa does not.

Another way of seeing that there is still some chance involved:

A perfect arimaa player would never score less than 1 out of 2 in a paired (one gold, one silver) set of games.

A perfect poker player would sometimes score less than 1 out of 2 in a paired (reversed) set of hands.

Title: Re: Man vs. Machine poker match (polaris)
Post by 99of9 on Jul 25^th, 2007, 6:48am

on 07/25/07 at 04:23:17, UruramTururam wrote:

If one wants to really win he must assume that other players don't play optimally!

Which is a correct assumption if the opponent is willing to play non-randomly whenever they think they have picked your pattern.

[And it's also obviously a correct assumption in a contest like this - clearly neither player knows how to play optimally.]

Quote:

But it makes him vulnerable to the ones who do.

So the question that runs through his mind is "am I sure I've picked his pattern, or has he set me up?" That sounds like psychology to me! (if the word can be applied to machines...)

Title: Re: Man vs. Machine poker match (polaris)
Post by UruramTururam on Jul 25^th, 2007, 8:12am

on 07/25/07 at 06:32:19, 99of9 wrote:

The difference here between arimaa and poker is that (as Uraram just mentioned), poker demands that you should play somewhat randomly, but arimaa does not.

It can be proved that for any complete information and no-randomness game the optimal algorithm contains needs not to contain any randomness. It is just "when the position is Px play the move Mx". That is the way how Mariendbad or Checker solutions work and it is true for Arimaa too, but it may take a long time until a solution is found.

However when a game is not of full information and a random factor is in (e.g. card dealing) it does usually mean that the optimal strategy should have a random part too. But not always! For example the optimal algorithm in 52-card Blind Black Jack is "if you have 15 points or less - draw a card, if you have 16 or more - don't".

And finally if an optimal algorithm contains a random part it will lose from time to time, as 99of9 said. but on average it would win more frequently... But (as it has been said in the "Cheater King" movie): "To win in poker you don't need to win every game. You just need to win 51 out of 100 ones.".

Title: Re: Man vs. Machine poker match (polaris)
Post by Fritzlein on Jul 25^th, 2007, 10:04am

on 07/25/07 at 04:23:17, UruramTururam wrote:

If one wants to really win he must assume that other players don't play optimally!

In very simple games like rock-scissors-paper, playing the optimal strategy means you can't lose and you can't win on average, but that is very unusual for games of hidden information. In any game of moderate complexity, playing your optimal strategy all the time will lead to gain against almost all of the opponent's sub-optimal strategies. In heads-up limit poker this will almost certainly be true. A perfect computer in poker would not have to detect weaknesses in the opponent's play and adapt to those weaknesses; it could win on average with a (non-adaptive) optimal strategy just because the opponent's weaknesses are there.

If I understand my game theory, then heads-up limit poker can be mathematically solved by building the entire game tree and calculating the Nash equilibrium strategy for each player. A bot playing the (non-adaptive) equilibrium strategy would be unbeatable on average, but would almost certainly win on average against any human player, since humans have only imperfect strategies. Also almost certainly, the equilibrium strategy would require randomized play (i.e. bluffing) in some situations.

However, this theory is all moot, because computers are not powerful enough to build the entire game tree and perform the necessary calculation. There are too many possible game states. To say, "It is only calculating the probability that the comp has stronger set and acting accordingly..." is completely missing the point. It's like saying that a chess computer only has to look at every possible move, and every possible reply, and so on until checkmate. Why say that it is "only" a matter of doing X, when X is beyond the computational ability of any computer? I could also fly to the moon if I could only hold my breath long enough and jump hard enough to exceed escape velocity.

I expect that computers will become better at poker than any humans, not by solving poker and finding the optimal strategy, but rather by playing "well enough" according to some heuristics. This is what happened in Othello, checkers, backgammon, chess, Scrabble, etc., and poker seems likely to follow suit.

It is interesting, however, that apparently the University of Alberta team was not sure whether their adaptive bot or their non-adaptive bot would do better against the humans. Apparently in the fourth round they used an "equilibrium" bot. Surely it wasn't a true equilibrium bot in the sense of having found the Nash equilibrium, since it would then have been unbeatable on average. Therefore I suspect they were trying to approximate the Nash equilibrium, hoping if they approximated it well enough they would not have to adapt to win. But the bot lost in that round.

In round two when the bot had a crushing win, it was apparently an adaptive bot that would willingly play sub-optimal strategies in order to take advantage of human weaknesses. This suggests that even top humans have weaknesses in their play that they don't understand. It also suggests that the University of Alberta might have won if they had been less interested in research and more interested in doing whatever works!

There may be an analogy to chess, where a computer can gain from playing an aggressive attack, even if the attack is objectively unsound, because the humans are likely to crack and blunder under pressure. Similarly overly-aggressive poker play, with lots of raising on good hands as well as bad, is probably objectively unsound, but may be effective against humans anyway, because the humans are more likely to blunder under pressure. However, this is getting into tenuous speculation on my part; hopefully the official match commentary will shed more light.

Title: Re: Man vs. Machine poker match (polaris)
Post by UruramTururam on Jul 25^th, 2007, 11:25am

The space of two-player classic poker is not so big...

The player receives 5 cards and can change up to 4 of them (there are versions where he can change 5) so he can see 5 to 9 cards.
Another datum is the number of cards the opponent changed. The task "what is the probability of the opponent having finally any valuable set of cards under these circumstances" is surely not beyond the computing power of even a small comp.

on 07/25/07 at 10:04:08, Fritzlein wrote:

the University of Alberta might have won if they had been less interested in research and more interested in doing whatever works!

This is the key sentence I believe.

Title: Re: Man vs. Machine poker match (polaris)
Post by Fritzlein on Jul 25^th, 2007, 1:59pm

on 07/25/07 at 11:25:33, UruramTururam wrote:

The space of two-player classic poker is not so big...

The space of poker is not so big? To borrow from Shakespeare, "'Tis not deep as a well, nor wide as a church door, but 'tis enough, 'twill serve"

For two-player limit hold'em there are up to nine cards involved: two in each hand, three on the flop, one on the turn, and one on the river. From the cards alone there are 52!/43!/2!/2!/3!/1!/1! = 55,627,620,048,000 states.

But for solving a game, the number of strategies is more important than the number of states. We must specify what decision to make in each situation, but the decision has to be the same regardless of the opponent's. We can only base our own action on the cards we can see plus the the previous actions of both players. For the cards we can see there are only 52!/45!/2!/3!/1!/1! = 56,189,515,200 possibilities.

The number of possible actions piles on to this, though. There are four betting rounds, and each round can can progress to the next round in nine different ways. For example, the state in the second round of betting depends on whether the first round was bet-raise-call, or check-bet-raise-raise-raise-call. Thus, when the last card shows after three rounds of betting, we can be in one of 9^3 * 52!/45!/2!/3!/1!/1! = 40,962,156,580,800 different states.

Let's restrict ourselves to only considering what our first bet will be on the final round of betting. We have at least two choices in each state in which we might be, which gives us at least 2^(9^3 * 52!/45!/2!/3!/1!/1!) = 10^12,330,837,817,905 different pure strategies.

Admittedly, one part of the game tree can sometimes be isolated from another, i.e. one can say that what I do when the board shows three of a kind has no bearing on what I do when the board shows two pair. In the case of poker, however, it is very difficult to say that my strategy in one part of the game tree has no bearing on my strategy in another. The optimal way to bet in earlier rounds will be affected by how hands tend to play out in later rounds.

Nevertheless, let's make a very generous assumption that when I get to my first bet on the river, I can isolate my strategy to consideration of only the decisions given the actual cards in play and only the actions leading to that point. One thing I certainly can't do is claim that the way I play a pair of aces is unaffected by the way I play a pair of eights in a similar circumstance, because my opponent doesn't know which I have. At a minimum a pure strategy must simultaneously declare what to do for each pair of held cards in that situation, i.e. at least decide on a (call/raise) decision for 52*51/2 = 1,326 states which are indistinguishable to the opponent. Thus even being very conservative, there are at least 2^1326 * 9^3 * 52!/47!/3!/1!/1! = 5.55 * 10^409 pure strategies.

The icing on the cake is that, even if you could enumerate all the pure strategies, finding the optimal mixed (probabalistic) strategy would still be tougher than bubbling up the minimax value through the game tree in chess. Last I knew there was no better method of solving a game than treating it as a linear program, which can be solved in O(n^3.5) by Karmarkar's interior point algorithm. Taking our large number to the power 3.5 yields approximately 1.27 * 10^1434.

Well, I probably messed up something about the math, but even so I'm pretty sure the space of two-player limit Texas Hold'em is "big enough" to make solving the game computationally infeasible at the moment.

Title: Re: Man vs. Machine poker match (polaris)
Post by UruramTururam on Jul 26^th, 2007, 1:40am

on 07/25/07 at 13:59:49, Fritzlein wrote:

For two-player limit hold'em there are up to nine cards involved: two in each hand, three on the flop, one on the turn, and one on the river.

We are talking about different pokers then.

Title: Re: Man vs. Machine poker match (polaris)
Post by chessandgo on Jul 29^th, 2007, 6:52am

Excellent, humans won :-)
Do you guys know whether there are people making bots play for themselves limit hold'em over internet to make money ? Sounds like it would really be profitable, if bots can play as strongly as top pros ...
And how about no limit hold'em ?

Title: Re: Man vs. Machine poker match (polaris)
Post by Fritzlein on Aug 2^nd, 2007, 5:09pm

I'm several years out of date. Last I knew there were people who connected bots to real-money Internet poker rooms to make money at limit Texas Hold'em. The on-line game rooms are naturally very concerned, and try to detect and prevent such behavior. In some games if you don't respond to chat, the other humans in the game assume that you are a bot.

I believe multi-player limit games are harder for bots than heads-up limit games. Five years ago I couldn't beat the University of Alberta bots heads up, but I could still beat them in a ring game. I don't know if I could win against modern bots in a ring game or not. Very likely they have advanced too much in the intervening years.

I don't know the state of the art in no-limt Hold'em, but I expect that it is too difficult for bots at present, even the two-player game, never mind the ring game. But that is only against top humans. I would bet that UofA bots could destroy me at no-limit heads up.