reno
reno
  • Threads: 124
  • Posts: 721
Joined: Jan 20, 2010
June 5th, 2015 at 9:26:01 AM permalink
I stumbled across an unbelievable statistic in this Wired magazine article about Carnegie Mellon University's attempt to build a computer that can beat humans at no limit Texas hold 'em:

Quote: Wired

Even better, computers have already solved most of the simpler problems. No-limit hold ‘em is the last big challenge. [Carnegie Mellon researcher Tuomas] Sandholm estimates that the number of unique situations that can arise in a game is greater than the number of atoms in the universe—squared. “The game is so big that you can’t even fit it into memory,” he says.



Greater than the number of atoms in the universe squared! Is this correct?
3for3
3for3
  • Threads: 1
  • Posts: 51
Joined: Jan 29, 2014
June 5th, 2015 at 9:30:14 AM permalink
Well, if your stack is $100, say, you have 10000 different betting amounts on each street, sometimes multiple times on the same street. Certainly you can pare that tree significantly by just limiting the bets to integer amounts. I still find number of atoms in universe squared to be on the high side.
cyrus
cyrus
  • Threads: 7
  • Posts: 41
Joined: Jan 23, 2015
June 5th, 2015 at 9:47:05 AM permalink
Also, part of any gaming analysis is examining results of decisions and the next decision after that, etc. So on decision #1, you need to examine your opponents possible moves (#2), and then your possible responses to those moves (#3), etc. When each of those moves has, say, 1000 options available, the resultant possible decision tree / forks is ridiculous.
ThatDonGuy
ThatDonGuy
  • Threads: 122
  • Posts: 6693
Joined: Jun 22, 2011
June 5th, 2015 at 12:11:57 PM permalink
Even if you limit "situations" it to flop / turn / river and hole cards:
There are combin(52,3) possible flops; for each one, there are 49 turns; for each one, there are 48 rivers
That's 15,288,800 right there.
In heads-up, there are combin(47,2) = 1081 possible pairs of hole cards for the first player, and for each one of those, there are combin(45,2) = 990 pairs of hole cards for the second player, so in a heads-up game, that's 16.36 trillion possibilities.
Add a third player: that's combin(43,2) = 903 pairs of hole cards, or 14.774 quadrillion possibilities.

Technically, you can divide the result by "about" 24, as each set of cards has 23 "partners" that are the same except that the specific suits are different. (I say "about" as the sets of cards with only 2 suits only have 11 partners, and the ones that are all the same suit only have 3 partners.) That makes the heads-up total about 682 trillion, and the 3-player total about 615 quadrillion. If there are seven players, that's 3.64 octillion possibilities, but keep in mind that the vast majority of those will be "fold immediately."

And did I miss a memo? Who came up with a computer that can play Go at, say, Shodan level?
  • Jump to: