1. 2008-07-12 22:32:48

   The machines are coming for us all: Polaris wins!

   You may have read about Polaris last year, when the poker-playing AI program narrowly lost its match against two poker pros. Well, it's back, and this time it won, with a score of 2 wins, one loss, and one draw.

   Polaris was designed by the same team of computer scientists that solved checkers. To solve a game, you have to build a database of every possible state and the best move to make in that state. This means that you have to know the complete state of the game at all times. Chess, othello, and mancala could also potentially be solved, although chess has orders of magnitude more possible states than checkers. Unlike these games, poker can't be solved since it you can't know the full state of the game all the time. This makes it a fascinating problem for computer science nerds like me.

   What's interesting about this match is that Polaris is now learning and switching strategies:

   Before the Las Vegas match, this newest version of Polaris had only played two matches against champion poker players, resulting in one loss and one victory. Polaris repeated the pattern of improving as it learned, falling to humans in the first two rounds, but defeating them in rounds three and four. "Repeatedly, I heard players exclaim that they had never seen a human do that before," said Bowling. "Switching strategies really threw the humans for a loop."

   Don't throw in the towel yet, though. The match Polaris played was quite contrived and was heads-up, which is a much simpler problem to tackle than multiple players. I'll be curious to see how well it will do multi-handed.

   Posted by Ethan at 2008-07-12 22:32:48

   View all posts

Comments on “The machines are coming for us all: Polaris wins!”

1. • Posted by Ethan g 2008-07-15 18:03:28
   • 

   • Krishna - what I meant by "solved" is that every possible board configuration had been analyzed and the best possible move picked, thus the computer plays perfectly, and the best you could ever hope for is a draw.

     You are right when you say that paring down states is important - it's one of the things humans do far better than computers. Another is pattern matching. Humans are much better at figuring out - sometimes subconsciously - that the current board configuration is really similar to some other board configuration, and then using that previous knowledge in this "new" situation.

     These two skills apply to chess, checkers, and poker. We are much, much better at them than computers, which is why they can only beat us in poker in a very contrived setting.

     A game that computers utterly fail at is Go. It's a theoretically solvable game like checkers, only it has on the order of 10^170 possible board states--vastly more than the number of atoms in the known universe (around 10^80). Just a few moves in to the game, the number of possible paths the game could take explodes to something like 10^400.

     The only way for humans to play this game is to see patterns and think in shapes and generalizations. This is why even the best Go playing computer can't even beat a skilled amateur.

     In any case, I will be excited to see how Polaris does multi-handed...if Jason and I don't get there first :)

2. • Posted by Jason M g 2008-07-15 06:25:22
   • 

   • Thanks for the links, man. Yeah, no limit is definitely much harder because of the bet sizes variability. Multiplayer raises aren't capped at only 3, too, which definitely makes the "big pot" states pretty complex.

3. • Posted by Krishna g 2008-07-15 04:30:13
   • 

   • The team was saying that bet sizing or multiplayers(>2) makes poker infinitely complex to solve.
     I guess that is why I am bad at nolimit.

4. • Posted by Krishna g 2008-07-15 03:01:35
   • 

   • HHs:
     http://www.stoxpoker.com/mvm/ijay-matt/

     Some quotes from Day 4:
     http://www.cs.ualberta.ca/~games/poker/man-machine/Live/Day4/

5. • Posted by Graham g 2008-07-15 01:58:04
   • 

   • I'd like to see more actual hands from the man vs. machine games to get a feel for how it actually went down. Calling down a 10-high with J-high is pretty absurd depending on some things.
     After thinking about it for a bit, even though it's not possible to 'solve' a game like poker, it should be easy enough to 'beat' poker with a computer. Especially heads up, limit, online. Computers never tilt. They never lose focus. They don't feel pressure. They are as good on hand 1000 as on hand 1. They never forget what to do, either they know or they don't. All of their brainpower goes toward a single goal and the brainpower of multiple humans went into constructing each one. I'd rather have a computer that could clean my place, though... now there is a complex system!

6. • Posted by Jason M g 2008-07-15 00:12:59
   • 

   • I didn't see that quote anywhere. Did I miss a link?

     That's interesting that the number of states doesn't necessarily directly relate to the complexity. In any case, AI algorithms frequently condense all possible states into many fewer states in order to make what seem to be "good judgment" decisions. I'm definitely intrigued by poker-playing computers. It combines my two favorite things :) Some day when I don't need to work on real work any more, that's what I'm going to do! Hah.

7. • Posted by Krishna g 2008-07-14 23:45:45
   • 

   • Some thoughts:
     HU Limit is relatively easier to play mathematically. Of course it is still a hard problem to solve.

     An interesting misnomer about problem complexity. Interestingly a great researcher who solves problems of enormous size mentioned this.

     Why are some problems hard to find an answer? Is it because there are so many possible solutions?
     Surprisingly - NO!
     If you think umber of possible solutions is the reason behind COMPLEXITY, I can easily give a counter example.
     Minimum spanning tree problem on a dense graph is trivial to solve even though there are exponential number of spanning trees.
     A similar problem of finding minimum distance tour is exponentially hard to solve even though there are less number of tours possible than the number of spanning trees.

     Human knowledge is still limited in the area of computational complexity.
     It was only recently proved that determining if a number is prime number is polynomial.

     Another thought is that all the "states" are not really useful for solving problems because they are either irrelevant or improbable or can be proved to be sub optimal without even examining them. So I expect Polaris to produce near optimal answers even though it is not technically exploring "all possible' states.
     No wonder it is making decisions like this one.

     2:49pm "Ooh Polaris!" says Hoss and his ten high bluff is unsuccessfull on the river as Polaris calls with J high.

8. • Posted by Jason M g 2008-07-14 20:38:24
   • 

   • Yeah, I think you have the setup correct. They do that multiple times and the humans get to talk to each other to compare notes between matches, which is only fair (Polaris gets to talk to itself about the other match is just played). In fact, I'm sure Polaris gets an interesting amount of information just by playing both sides and therefore having complete knowledge of all the hands, right? For example, after the fact, it would know what the opponent had on hand 5 when they folded without showing. I think...

     AK23 is money. I don't know if I'd push that hard preflop, or you might give your hand away.

9. • Posted by Graham g 2008-07-14 18:59:04
   • 

   • That's an interesting setup. If I have it right, each match consists of Polaris vs. human in room A and Polaris vs. another human in room B simultaneously. In each room, the cards are fixed and swapped, so that in room A, Polaris gets the same cards as the human in room B and vice versa. This way each team plays each side of the cards to balance the luck factor. Seems they thought of everything.

     Ethan, how long before your poker mantra becomes WWPD?

     Captcha = ak23 bet pot?

10. • Posted by Jason M g 2008-07-14 05:06:03
    • 

    • Anyway, back to computers playing poker. Awesome :) Let me know when they go multi-handed so I can leverage the AI and make a poker bot. K TKS Bye.

11. • Posted by Graham g 2008-07-13 19:14:23
    • 

    • Come on, Ethan, that's if we start now. I've got to believe some positions are solved already and some positions are totally irrelevant. When you factor all that in with the doubling effect and a really big cluster of computers, it will probably really only take a few hundred thousand times longer than the age of the universe to solve =)

12. • Posted by Ethan g 2008-07-13 02:32:18
    • 

    • Actually, chess hasn't been solved. Checkers has on the order of 10^20 possible states, while Chess has on the order of 10^43, or almost a trillion-trillion times more.

      Checkers took 18 years to solve. Since computers double in speed every 18 months or so, we can estimate that it would only take 1 year right now. At that rate, it would take 2 x 10^22 years to solve chess, or over a billion times longer than the age of the universe.

      Of course, if you factor in the doubling effect, it might only take half that :)

13. • Posted by Nick L g 2008-07-13 02:06:53
    • 

    • Wow that is interesting I would like to see how it computes multi handed. That is just crazy to compute every possible math equation in chess that is impressive.