AI: bluffen, Geld aus der Bevölkerung nehmen und Unsicherheit überwinden

Published on January 30, 2017

AI: bluffen, Geld aus der Bevölkerung nehmen und Unsicherheit überwinden



    Während Sie diese Zeilen lesen, geschieht gerade in der Welt ein erstaunliches Ereignis - künstliche Intelligenz besiegt den Mann im nächsten Spiel. Überraschend ist nicht die Überlegenheit von Maschinen, sondern die Tatsache, dass wenig darüber geschrieben wird. Vielleicht aufgrund der Tatsache, dass die Maschine diesmal nicht im legendären Spiel „go“ antritt, nicht in DOOM, lapta oder hide and seek, sondern im Sportkarten-Poker.

    Poker wird oft verächtlich als Glücksspiel bezeichnet, dessen Gewinn ausschließlich vom Fall abhängt. Heute wird es in einigen Ländern (mit Ausnahme von Russland) als offizieller Sport anerkannt. Das Interessanteste für uns und die Maschinen ist, dass beim Poker Gewinnstrategien mithilfe der Wahrscheinlichkeitstheorie vorhergesagt werden können. Und was am wichtigsten ist, Poker ist ein Spiel mit unvollständigen Informationen, im Gegensatz zu Schach, Dame, Backgammon, bei dem beide Spieler die Position aller Teile auf dem Brett sehen. Zuvor konnte AI nicht dort gewinnen, wo Unsicherheit herrscht. Was hat sich also geändert?

    Die größten Spiele



    Haftungsausschluss: Um das Material aus diesem Artikel zu verstehen, sind keine Kenntnisse über Poker erforderlich. Für ein tieferes Eintauchen in das Thema müssen Sie jedoch zumindest die Grundlagen des Spiels kennen.

    In Science-Fiction kämpfen Roboter oft gegen Roboter („gut“ gegen „schlecht“), aber in Wirklichkeit ziehen Maschinenmeisterschaften mit Ausnahme der bekannten mechanischen „Kämpfe“ nur wenige Zuschauer an. Bootkämpfe untereinander sind emotionslos und wettbewerbsfähig und nur für ein begrenztes Fachpublikum von Interesse. Ob es ein Kampf mit Menschen ist! Bis 2016 konnten Computer in zwei Dutzend intellektuellen Spielen von einer Person gewinnen (oder eine mathematische Lösung finden, um Positionen zu gewinnen): Ihn, Tic-Tac-Toe, Ghost, vier in einer Reihe, Gomoku (15x15), eine Mühle (mit 9 Chips), Lentomino, Ovalhu, quarto, tiko, pangki, rendzu (ohne debüt-regeln), unfall (mankala family), maharadscha, tiger und ziegen, fanarona, englische kontrolleure, drei musketiere, hex (8x8), calah (6x6), chinesische stöcke, Pentago, los (5x5 und das klassische Spiel gegen Lee Sedol).

    Nicht alle diese Spiele sind Ihnen vielleicht bekannt, aber Sie können zu jedem einzelnen einen separaten Artikel mit einem dramatischen Kapitel über den Kampf gegen Autos schreiben. Eine der interessantesten und angespanntesten Auseinandersetzungen (neben den bekannten Peripeteias mit dem Spiel "go") war der Kampf um die Drachenkrone. Sie können mehr über diese Periode in unserem ersten Artikel aus dem Zyklus über AI lesen , aber erinnern Sie sich zunächst an eine interessante Zahl: Englische Kontrolleure sind die größten Spiele, die bisher vollständig gelöst wurden. Der Suchraum hat eine Größe von 5 × 10 20 . Um eine Lösung zu finden, hat ein Netzwerk von Personalcomputern (von 50 bis 200 Stück) für 18 Jahre 10 14 Berechnungen angestellt.

    Wenn Sie unsere vorherigen Artikel über AI lesen, wissen Sie bereits, dass die Maschine bei komplexen Spielen nicht durch alle möglichen Kombinationen von Zügen gewinnt. Die geschätzte Mindestanzahl nicht wiederkehrender Schachspiele, die 1950 von dem amerikanischen Mathematiker Claude Shannon berechnet wurde, beträgt etwa 10.118 . Zum Vergleich: Die Anzahl der Atome im beobachtbaren Universum liegt nach verschiedenen Schätzungen zwischen 4 × 10 79 und 10 81 , also 10 40- fach unter der Shannon-Zahl.

    Es ist undenkbar, alle Schachspiele "auswendig" zu kennen. Es ist auch nicht möglich, die Anzahl der möglichen Positionen zu berechnen. Und die Regel bezieht sich nicht nur auf Schach. Aufgrund der Entwicklung von Algorithmen und der Verbesserung der neuronalen Faltungsnetzwerke konnten Computer jedoch dort gewinnen, wo das menschliche Gehirn schneller oder zumindest nicht schlechter arbeitet.

    Was ist der Platz des Pokers im Vergleich zu anderen würdigen Spielen? Nehmen Sie zum Beispiel die heute populärste Pokerform - Texas Hold'em mit begrenzten Einsätzen. Limit Hold'em ist aufgrund seiner begrenzten Einsätze stark von der Mathematik abhängig und eignet sich gut für Algorithmen: Für das Einzelspiel gibt es etwa 10 18Spielsituationen. Wenn wir berücksichtigen, dass einige Kartenkombinationen gleichwertig sind (z. B. sind zwei Asse unterschiedlicher Farbe identisch mit anderen Assen), erhalten wir etwa 10 14 verschiedene Spielkombinationen. Zum Vergleich: Es gibt 10.160 No-Limit Hold'em und im Spiel "Go" -Entwicklungsoptionen 10.170 .

    10 14 - es scheint, dass dies im Vergleich zu Schach sehr viel kleiner ist und die englischen Kontrolleure viel einfacher sind. Die Schwierigkeit besteht darin, dass die Spieler bei Poker die Karten des Gegners nicht kennen und nicht wissen, welche Kombination ihre eigenen Karten in der nächsten Runde bilden werden.

    Wenn Sie außerdem die Pokerlimits entfernen (d. H. Sie können auf das gesamte Geld setzen, das dem Spieler zur Verfügung steht) und die Anzahl der Spieler von zwei auf drei oder fünf erhöhen, werden wir einen solchen viskosen Sumpf mathematischer Unsicherheiten erhalten, dass die mächtigsten Supercomputer zu sinken beginnen. Die menschliche Erfahrung erlaubt es auf intuitiver Ebene, die Handlungen eines Gegners zu betrachten, die fehlenden Informationen auszuwerten und sogar einige Schlussfolgerungen und Vorhersagen zu treffen. So wird Poker zu einer hervorragenden Plattform, um die Fähigkeiten von AI zu testen, denn es erhöht die Komplexität auf Kosten von Leuten, die nicht nur Logik verwenden, sondern auch versuchen, Konkurrenten mit Bluffs und anderen Tricks zu überlisten. KI hat nur Spieltheorie, um nach optimalen Strategien zu suchen.

    Bots gegen die Menschheit




    Die ersten ernsthaften Versuche, einen Poker-Bot zu erstellen, wurden in den frühen 80ern gemacht. 1984 stellte der bekannte Pokerspezialist Mike Caro das Orac-Programm vor, das viele mit seinen Fähigkeiten beeindruckte. Orac zum Beispiel könnte den Bluff des Gegners relativ erfolgreich berechnen, indem er lediglich die Zeit misst, die der Gegner benötigt, um sich zu bewegen - je länger eine Person denkt, desto höher ist die Wahrscheinlichkeit eines Bluffs.

    Im Jahr 1991 begann die University of Alberta (Kanada) mit der Entwicklung des Polaris One-to-One-Hold'em-Programms. Nach 16 Jahren Arbeit an einem Projekt, das aus mehreren Poker-Bots bestand, die eine ganze Familie von Algorithmen zur Ermittlung von Gleichgewichtsstrategien berücksichtigten, fand 2007 ein Match gegen mehrere Poker-Profis statt. Unter den Bedingungen des Spiels wurden die gleichen Karten an die Person und den Computer verteilt, sodass der Zufallseffekt im Spiel minimiert wurde. Zunächst gewann Polaris deutlich, aber nachdem mehrere Spiele analysiert worden waren, fanden die Spieler die sich wiederholenden Merkmale des Spielprogramms und konnten gewinnen.

    Im Juli 2008 konnte die Polaris endlich die Meisterschaft zwischen Mensch und Auto gewinnen. Die Gesamtpunktzahl der Sitzungen war 3 Siege, 2 Niederlagen, 1 Unentschieden. Dieser Sieg markierte jedoch nicht den Beginn einer Ära der Maschinenherrschaft und des Todes von Online-Poker. Wie bereits erwähnt, wird „Machine Poker“ mit einer Reihe von Einschränkungen gespielt, die in echten Online-Spielen nicht beachtet werden.

    Die erste große Herausforderung für die Menschen war das Turnier 2015, bei dem vier der TOP 10 besten Spieler in Texas Hold'em vom Claudico-Programm abgelehnt wurden. In Brains Vs. Menschen mit künstlicher Intelligenz waren stärker.

    Ein weiteres Tartanian7-Pokerprogramm an der Carnegie Mellon University im Jahr 2014 konnte einige Neulinge und Computer-Bots schlagen. Die Besonderheit dieses Programms besteht darin, dass sie nach zehn Jahren Entwicklung gelernt hat, mit Novizen einigermaßen No Limit Hold'em zu spielen.

    Bis vor kurzem fühlte sich die KI in Limit-Spielen mit einer Person mehr oder weniger zuversichtlich und verlor sich in No-Limit- und Multi-Seat-Poker-Disziplinen. Trotzdem hat es immer Menschen gegeben, die dafür gesorgt haben, dass die Bots besser spielen können als Menschen. Der Grund ist einfach - Geld.

    Maschine verdient in Spielen




    Ein Bot kann einer Person weichen, aber hundert Bots erhöhen mathematisch die Gewinnchancen. Im Jahr 2010 kam es zu einem großen Skandal, als auf einer bekannten Pokerseite Bots entdeckt wurden, die insgesamt mehr als zweihunderttausend Dollar erzielten. Spezialisten auf der PokerTableRatings-Website haben eine auffällige Ähnlichkeit aller Parameter über einen langen Abstand mit mehreren Spielern festgestellt . Statistisch konnte nachgewiesen werden, dass alle diese verdächtigen Spieler in allen Situationen identisch handelten.

    Haben die Bots immer nur beim Massenphänomen gewonnen und "verbrannt"? Nicht genau Die Online-Plattform für das Spiel, der sogenannte "Pokerraum", gibt den Spielern eine Provision, die vom Einsatz jedes Spielers berechnet wird. Die Rendite, Rakeback genannt, ist ein zusätzlicher Bonus, durch den Pokerräume weitere Spieler anziehen.

    Im Durchschnitt beträgt die Gebühr für ein Pokerspiel 5% und kann 3-5 cu nicht überschreiten. für 1 Spiel. Rakeback ist ein großer Gewinn für Bots: Auf Kosten davon können Sie 0 mit Leuten spielen, aber gleichzeitig auf Kosten von Prozent vom Pokerraum verdienen. Die Anwesenheit von Bots, die erfolgreich gegen Anfänger spielen, ist eine Tatsache. Sie haben jedoch keinen Einfluss auf den Weltmarkt für die Entwicklung künstlicher Intelligenz.

    Ganzheitlicher Sieg im Bereich der Unsicherheit




    Nach den Erfolgen von Tartanian7 an der Carnegie Mellon University begannen sie mit der Entwicklung eines neuen, viel anspruchsvolleren Poker-Bots - Libratus. Während das DeepStack-Programm der Konkurrenz University of Alberta in ersten Tests recht gute Ergebnisse zeigte , lehnte Libratus im Januar 2017 echte Poker-Profis ab. Die Berechnungen im Entwicklungsprozess von Libratus dauerten 15 Millionen Kernstunden (Claudico kostete 2-3 Millionen Kernstunden. Während des Spiels nutzt Libratus die Leistung des Bridges-Supercomputers (1,35 Petaflops / Sek).

    Wie zu Beginn erwähnt, könnten die Programme (wie sie es taten), um die Anzahl der möglichen Pokerhände zu reduzieren, eine Vereinfachung verwenden, wonach einige Kartenkombinationen als identisch betrachtet wurden. In den meisten Fällen ist dies akzeptabel, aber nicht gegen die besten Profis der Welt, wo der Unterschied zwischen allen Karten erheblich ist. Libratus verwendet für jede Situation, in der er sich befindet, eine einzigartige Strategie.

    Am 11. Januar begann ein Turnier, bei dem Libratus insgesamt 120.000 Hände zu einem Texas Hold'em No-Limit spielte. Das Spiel geht an virtuelles Geld, aber der Preis für den Sieg - 200.000 US-Dollar - ist absolut real für vier professionelle Pokerspieler, von denen zwei bereits Erfahrung mit dem Bot hatten und Claudico 2015 gewonnen haben. Damit das Ergebnis des Wettbewerbs nicht zu zufällig ist, wird jedes Spiel dupliziert, so dass Spieler A die Karten erhält, die der Computer im Spiel mit Spieler B erhalten hat, und umgekehrt.

    Von Anfang an übernahm Libratus die Führung, gewann am ersten Tag Menschen und verdoppelte den Abstand zum zweiten Tag mehr als. Je länger das Spiel dauert, desto mehr Informationen erhält die KI über die Spieler, sodass sie stärker wird. Jedes Mal, wenn die Leute Mängel in der Programmstrategie bemerkten, erfuhr sie davon und passte ihr Spiel am nächsten Tag an. Zum Ende der vergangenen Woche hatte Libratus bereits fast 800.000 USD gewonnen. Bis zum 30. Januar hat der Preis eine Million Dollar überschritten.

    Die Maschine spielt ausgewogen - das macht alles ein bisschen. Sie kann mit schlechten oder guten Karten bluffen, sie kann hohe Einsätze machen oder niedrig spielen - ihr Spiel passt sich jedes Mal an die Handlungen einer Person an und wird besser.

    Wie funktioniert Libratus eigentlich? Die Antwort auf diese Frage noch. Wissenschaftler werden das Geheimnis, wie das Programm gewinnt, zumindest bis zum Ende des Turniers nicht verraten. Wir wissen, dass das Programm auf einem speziell entwickelten Algorithmus zur Berechnung optimaler Strategien für Spiele mit unvollständigen Informationen basiert. Eine neue Technologie wird auch verwendet, um das Nash-Gleichgewicht zu erreichen - eine Strategie, bei der keiner der Spieler seine Gewinne durch Änderung der Strategie erhöht, wenn der andere wiederum die Strategie nicht ändert.

    Wird Libratus Online Poker zerstören?




    Der Standard für die Forschung ist Texas Hold'em, aber die verwendeten Entwicklungsmethoden sind nicht an eine Pokerart gebunden. Im Allgemeinen ist es möglich, einen ähnlichen Bot für andere Arten (und nicht nur) zu erstellen. Am wichtigsten ist jedoch, dass Wissenschaftler ein Arbeitsinstrument zur Lösung von Problemen im Bereich der Ungewissheit erhalten. Und dies ist nicht nur eine große Klasse anderer Spiele (die Leute schlagen immer noch den Computer im ersten Teil von StarCraft), sondern auch viele reale Aufgaben auf der ganzen Welt.

    Wie beim gewöhnlichen Poker äußern normale Spieler bereits die Befürchtung, dass die Programme das übliche Online-Spiel beenden oder zumindest das Spiel erheblich erschweren könnten, sodass jeder die Webcam einschalten und seine Aktionen an das Netzwerk senden muss. Aber wie wir aus der Vergangenheit wissen, haben Programme das Schachspiel nicht zerstört, und Schachturniere mit großen Geldmitteln sind nach wie vor beliebt. Aber auch wenn Online-Poker allmählich der Vergangenheit angehört, wird letztlich alles, was mit der Rechenleistung von Computern verbunden ist, der Menschheit zugute kommen.

    Quellen: