Heads-up limit hold’em poker is solved

    • Cornholio
      Cornholio
      Bronze
      Dabei seit: 05.02.2006 Beiträge: 25.674
      Michael Bowling / Neil Burch / Michael Johanson / Oskari Tammelin (2015): Heads-up limit hold’em poker is solved. In: Science [!] 9 January 2015, Vol. 347 no. 6218, 145-149.

      discuss
  • 21 Antworten
    • HannesZ
      HannesZ
      HeadAdmin
      HeadAdmin
      Dabei seit: 30.06.2010 Beiträge: 16.311
      Noch der Link zum Science Artikel:
      http://news.sciencemag.org/math/2015/01/texas-hold-em-poker-solved-computer
    • Cornholio
      Cornholio
      Bronze
      Dabei seit: 05.02.2006 Beiträge: 25.674
      Danke! Ist allerdings nur eine laiengerechte Zusammenfassung. Die Einsicht in den Volltext über die Science-Website kostet z.Zt 20$.
    • sonnensb
      sonnensb
      Bronze
      Dabei seit: 21.03.2007 Beiträge: 2.545
      das war gestern meine abend lektüre.
      wird wohl einen heftigen impact haben. dass das in einem high profile journal wie science landet wundert mich nicht.
      offenbar hat auch der gute alte bryce paradis informell mitgewirkt, aus den acknowledgments im paper selbst "... and B. Paradis for insights into the conventional wisdom of top human poker players."
    • Gambler2k6
      Gambler2k6
      Bronze
      Dabei seit: 28.11.2006 Beiträge: 2.025
      Schon jemand gegen ihn gespielt?
    • cjheigl
      cjheigl
      Moderator
      Moderator
      Dabei seit: 09.04.2006 Beiträge: 24.495
      Cepheus (so heisst das Programm) ist erreichbar unter http://poker-play.srv.ualberta.ca/ Momentan ist es aber offline und meldet temporary maintenance. Das Analysetool funktioniert.

      Cepheus Projekt Seite: http://poker.srv.ualberta.ca/

      Das sind die selben Leute, die schon Polaris (Gewinner des Mensch-Maschine Wettbewerbs) und den mehrfachen Computerpoker Weltmeister Hyperborean entwickelt haben.

      Erste Erkenntnisse:

      Cepheus spielt fast alle Hände mit gemischter Strategie, abgesehen von den bottom 16%, die er immer foldet (auf BU). Gemischte Strategie heisst aber meistens 99,95% raise, 0,05% call oder in der Art. Also fast immer raise. Es gibt zwei grössere Ausnahmen: T4o = ~75% raise, 25% fold, 0,19% call und 74o = 5,5% raise, 94,5% fold, 0,03% call.

      Auf BU nach bet und 3-bet mehr oder weniger alles 100% call (manche Hände mit bis zu 0,06% cap).

      Als BB spielt Cepheus gegen einen Raise ca. 28% 3-bet, 8% fold und 64% call. Viele Hände mit gemischter Strategie (call oder 3-bet), aber 44+, A4s+, K6s+, Q9s+, JTs, 76s, 65s, 54s, AQo+ (14% Range) mit 100% 3-bet.
    • aspirin
      aspirin
      Bronze
      Dabei seit: 27.06.2006 Beiträge: 1.007
      Bin mir nicht sicher, ob ich das Projekt richtig verstanden habe und möchte mal schildern, wie ich es verstanden habe und bitte um Korrektur.

      Zu Beginn kennt das Programm nur die Regeln, weiß also zu jeder Spielsituation, welche Aktionen möglich sind (unabhängig von ihrer Qualität).
      Ferner kann es den Spielausgang bewerten.

      Nach Hand 1 hat sich daran nicht viel geändert.
      Bsp. : Hand 1 hat das Programm 7c2h im SB und hat per Zufall geraised. Gegner hatte AdAh. Board ist AsAcKs. 72 bet, AA fold. Der fold mit den nuts ist natürlich schwach, aber da das Programm keinen Eintrag zu diesem Szenario in der DB hat, entscheided halt der Zufall, also hier mal fold.
      Nach Hand 1 hat sich das Programm also folgendes "Pokerwissen" angeeignet :
      OR mit 7c2h hat 100% Gewinnerwartung.
      conti flop auf AsAcKs mit 7c2h hat 100% Gewinnerwartung.
      passiver defend mit AdAh hat 100% Verlusterwartung.

      Das fließt in Hand 2 schon ein. 7c2h hat nun eine höhere Wahrscheinlichkeit für OR, AdAh eine höhere Wahrscheinlichkeit für 3b oder fold.
      Auf exakt diesem Flop hat 7c2h nun eine höhere Wahrscheinlichkeit für bet und AdAh eine höhere Wahrscheinlichkeit für call oder raise.

      Das ganze wird nun Milliarden mal wiederholt, bis jede Hand auf jedem Board mit jeder Line x mal gespielt wurde.

      Dabei findet zu keinem Zeitpunkt irgendwelche "Pokerintelligenz" statt. Also keine Berechnungen über Ranges, Equity, Adaption, Gegneranalyse o.ä.
      Das Programm wird also niemals z.B. berechnen, dass es am Turn eine 200 Kombo Range hat und davon 35 Kombos bluffen sollte, wofür diese und jene Kombo am besten geeignet wären.

      Für die o.g. Hände wird am Ende dann rauskommen, dass bei 72o in den meisten Fällen fold gut ist, bei AA aber in den wenigsten Fällen.
      Und für 54s wird rauskommen, dass 3b pf den meisten EV verspricht. Das aber nicht, damit man "in der pf 3b range genug deceptive Hände mit guter Equity hat", sondern einfach, weil es sich in Milliarden Tests als (vmtl. leicht) besser als call herausgestellt hat und es so in der DB steht.

      Oder ist es so, dass das Programm während der Trainingsphase gar nichts lernt, aber natürlich alle Ergebnisse in seine DB einträgt. Und aus dem Endergebnis dann die korrigierten Wahrscheinlichkeiten ermittelt, die es zur Entscheidungsfindung nutzt?

      Macht es für das Endergebnis einen Unterschied, ob es ohne Lernen trainiert oder nicht?

      Oder funktioniert das alles ganz anders?
    • Grinsemann1
      Grinsemann1
      Silber
      Dabei seit: 05.10.2006 Beiträge: 88
      Hm ich habs so verstanden das es wohl eine Methode gibt , für eine gegebene Strategie die optimale exploitive Strategie zu finden. Es wird mit der bisherigen besten gto Annäherung begonnen, dann wird der optimale exploit gefunden, dann von der exploitive Strategie wieder der beste exploit, usw. , bis sich exploit und Ursprungsstrategie gleichen, was bedeutet ein Nash Gleichgewicht ist gefunden.
      edit: wundert mich btw dass der thread so kurz ist, ich fands sehr beeindruckend und dachte der thread explodiert bestimmt.
    • Grinsemann1
      Grinsemann1
      Silber
      Dabei seit: 05.10.2006 Beiträge: 88
      The researchers developed their strategy by pitting the computer against itself in a series of training rounds. After playing itself, the computer examined its moves to see if making different choices would have improved its result. It then calculated its "regret" for not doing so—a mathematical measure of how much it lost because of its imperfect move.

      Aus dem oben verlinkten Artikel, also es spielt "a series of Training rounds" und guckt wo die eigene Strategie verbesserungsfähig ist(making different choices would have improved its result) , also wo die eigene Strategie exploitbar ist(da es ja gegen sich selber spielt), und baut dann die exploits in die nächste Trainingsrunde ein. So verstehe ich das. Interessant wie menschlich diese Herangehensweise ist^^. Die Ursprungsstrategie wird wohl deren polaris gto ding sein? Weiß ich natürlich aber nicht.
    • balrog25
      balrog25
      Silber
      Dabei seit: 03.11.2006 Beiträge: 656
      Auf Spiegel Online gabs gestern nen zusammenfassenden Artikel dazu, der sich natürlich an Nicht-Pokerspieler richtet. Dort stand sinngemäß, das Programm hätte so oft gegen sich selbst gespielt, bis alle möglichen Spielsituationen so oft durchlaufen worden sind, so dass es die für jede mögliche/einzelne Spielsituation die optimale Strategie gefunden hat. Daher würde das auch mit "solved" passen:

      http://www.spiegel.de/wissenschaft/mensch/texas-hold-em-computer-schlaegt-erstmals-menschen-beim-poker-a-1011800.html

      [...] "Bei der Variante Heads-up Limit Texas Hold'em gebe es 3,16 * 1017 [lies: 10 hoch 17] mögliche Spielsituationen, schreiben die Forscher der University of Alberta. Um den für jede Situation optimalen Spielzug zu finden, nutzten sie einen intelligenten Brute-Force-Ansatz. Der Computer habe immer wieder gegen sich selbst gespielt, anfangs waren die Aktionen zufällig, berichtet Neil Burch von der University of Alberta, der an der Studie beteiligt war.

      Dann habe die Software begonnen, den Erfolg der Schritte zu bewerten, und so die Strategie immer mehr verbessert. Dies sei immer und immer wieder wiederholt worden, bis der Computer schließlich die für jede Spielsituation optimale Aktion gefunden habe. Die Berechnung auf einem Parallelcomputer mit 200 2,1-GHz-Prozessoren dauerte fast 70 Tage. Ihr Ergebnis ist eine 11 Terabyte große Datei, in der die für jede Spielsituation beste Aktion gespeichert ist."

      :profit: Und bald hacken irgendwelche Russen den Alberta-Computer, Copy und Paste und gut ist's mit Heads Up Limit Holdem for Real Money oder was?

      Naja, 6max hat noch ein paar Jahre/Monate:

      [...]
      "Um aber bei großen Turnieren oder der Pokerweltmeisterschaft antreten zu können, müssten die Forscher ihre Software enorm erweitern. Denn dabei sitzen bis zu zehn Spieler an einem Tisch, je nach Variante wird auch ohne Limit gespielt. Dies erhöht die Zahl der Spielsituationen und damit den Rechenaufwand dramatisch."
    • Sendrafreak
      Sendrafreak
      Bronze
      Dabei seit: 31.05.2011 Beiträge: 2.074
      Original von Grinsemann1 ... edit: wundert mich btw dass der thread so kurz ist, ich fands sehr beeindruckend und dachte der thread explodiert bestimmt ...
      Echt? Mich nicht, ist doch Fixed Limit (Wird das heute wirklich noch gespielt?)
    • Progamer
      Progamer
      Bronze
      Dabei seit: 17.09.2006 Beiträge: 1.088
      Den Artikel kriegt man an jeder Uni umsonst.

      Die Authoren sagen auf ihrer Website auch, dass FL HU tot ist:

      At of the time of writing this article on a Saturday evening there are, on Pokerstars, the current market leader, thirty-five heads-up limit hold’em tables above the one dollar level where players are waiting for an opponent and one table at which two players are actually competing. Cepheus will undoubtedly prove a valuable sparring partner and research tool for casino players and enthusiasts looking to sharpen their skills, but the heyday of heads-up cash play has, unfortunately, already passed.
      http://poker-blog.srv.ualberta.ca/2015/01/08/humans-robots-and-the-consequences.html

      Aber mal aus Interesse, was sagen denn die HU experten hier zu der Strategie? Hab schon lang nicht mehr gespielt, aber erinner mich noch an opening und defending ranges von ca. 90 %. Die openingrange von Cepheus ist da etwas tighter. Kann mir schon vorstellen, dass die Strategie vor allem bei 2/3 Blindstrukturen angreifbar ist.

      Zu 3-betting: Warum mit 22 nur call? Dachte immer dass genau diese Hand ne schwache Playability hat und sehr von Protection profitiert.

      Hat jemand das Programm schon ausprobiert? Wie macht es sich postflop?
    • cjheigl
      cjheigl
      Moderator
      Moderator
      Dabei seit: 09.04.2006 Beiträge: 24.495
      Das Programm/die Webseite ist offenbar ziemlich überlastet. Fast immer kommt temporarily offline wegen Wartung. Wenn es doch mal läuft, gibt es ingesamt 4 Plätze, um gegen das Programm zu spielen. Ich bin bisher nicht reingekommen.

      "Die Autoren", die über die Situation im menschlichen Poker geschrieben haben war Bryce Paradis. An der Entwicklung des Programms selbst war er wohl nicht beteiligt. (Das waren Dr. Michael Bowling, Neil Burch, Michael Johanson, Oskari Tammelin.)
    • aspirin
      aspirin
      Bronze
      Dabei seit: 27.06.2006 Beiträge: 1.007
      Ich überlege immer noch, wie das funktioniert.

      Wollte mal ausrechnen, wieviele Situationen es für eine bestimmte Starthand (egal welche) gibt.

      Komme auf folgendes Ergebnis :

      Lines zählen

      a = Hand endet am Flop = 7
      b = Hand sieht Turn = 7
      c = Hand endet am Turn = 8
      d = Hand sieht River = 9
      e = Hand endet vor SD = 8
      f = Hand sieht SD = 9

      n = Anzahl Lines = a + b * ( c + d) + d * (e + f) = 279

      Richtig?

      Jetzt noch ausrechnen, wieviele DB-Einträge man braucht, wenn man für jede Spielsituation einen Eintrag haben will.

      af = Anzahl Flops = 50 über 3 = 19600
      at = Anzahl Turns = 50 über 4 = 230300
      ar = Anzahl River = 50 über 5 = 2118760

      z = Anzahl DB Einträge = a * af + b * (c + d) * at + d * (e + f) * ar = 180093620

      z / 1024 / 1024 = ca. 172 MB

      D.h., man käme für alle Starthände mit ca. 222 GB hin ohne weitere Tricks (viele Hände sind ähnlich, man könnte die Situationen verringern).

      Das kann doch nicht stimmen.

      Was ist falsch?
    • Django3
      Django3
      Bronze
      Dabei seit: 16.10.2009 Beiträge: 1.339
      Ich hab keine Ahnung wie du auf die Anzahl der Lines kommst.
      Nur mal als Beispiel:
      Hero ist BB
      Möglichkeiten SB openraist: fold, call, 3-bet (SB calls or folds), 3-bet (SB 4-bets, Hero calls), 3-bet (SB 4-bets, Hero folds)
      Möglichkeiten SB openlimps: check, raise (SB calls or folds) , raise (SB 3-bets, Hero folds), raise (SB 3-bets, Hero calls), raise (SB 3-bets, Hero 4-bets)

      Damit hat man allein schon 10 (wenn ich keine vergessen habe) unterschiedliche Möglichkeiten eine Hand preflop im BB zu spielen. Hinzu kommen noch alle Möglichkeiten sie im SB zu spielen... und dann hat man erst preflop abgearbeitet. Entsprechend müssen alle von dir aufgezählten Möglichkeiten nochmal deutlich höher liegen.
    • aspirin
      aspirin
      Bronze
      Dabei seit: 27.06.2006 Beiträge: 1.007
      Richtig, habe nur 1 Starthand aus einer Position berücksichtigt. Endergebnis müsste also ca. doppelt so hoch sein.

      Ich sehe gerade, dass da was fehlt.
      Brauche
      - endet PF
      - sieht F
      - endet F
      - sieht T
      - endet T
      - sieht R
      - endet R
      - sieht SD

      Ich check das morgen nochmal.

      Erläuterung zu a (was richtig "endet pf" heißt) :

      fold
      call check
      call raise fold
      call raise call
      call raise raise fold
      call raise raise call
      call raise raise raise fold
      call raise raise raise call
      raise fold
      raise call
      raise raise fold
      raise raise call
      raise raise raise fold
      raise raise raise call

      14 Varianten, jede 2. endet pf, also 7.
    • aspirin
      aspirin
      Bronze
      Dabei seit: 27.06.2006 Beiträge: 1.007
      endet PF = 7
      sieht F = 7
      endet vor T = 8
      sieht T = 9
      endet vor R = 8
      sieht R = 9
      lines R = 17

      Lines = 7 + 7 * ( 8 + 9 ) + 9 * ( 8 + 9 ) + 9 * 17 = 432

      Kombos :

      endet PF = 1
      endet F = 19600
      endet T = 230300
      endet R = 2118760

      DB ist Kombos multipliziert mit Lines

      DB = 1 * 7 + 19600 * 7 * ( 8 + 9 ) + 230300 * 9 * ( 8 + 9 ) + 2118760 * 17 = 361738587

      DB für eine Hand aus beiden Positionen ist das doppelte.

      DB-Einträge für eine Hand also 690 MB bei 1 Byte pro Kombo und Line.

      Kommt mir immer noch zu klein vor.

      Ich probier das einfach mal aus mit vereinfachten Pokerregeln wegen Laufzeit.
    • wuerstchenwilli
      wuerstchenwilli
      Black
      Dabei seit: 07.04.2008 Beiträge: 18.676
      Poker ist dann tot, wenn jeder es erkannt hat. Solange es aber noch Spieler gibt, die mit schlechten Taktiken spielen, ist es nicht tot.

      Das Programm ändert imo nix. Denn auf Grund des Rates War es vorher schon tot, es sei denn es kommen schwächere Spieler.
    • Progamer
      Progamer
      Bronze
      Dabei seit: 17.09.2006 Beiträge: 1.088
      http://www.pokerupdate.com/news/entertainment/01272-pokerstars-adds-cepheus-to-pro-roster/
    • Binipoker
      Binipoker
      Bronze
      Dabei seit: 21.08.2007 Beiträge: 1.369
      ..
    • 1
    • 2