Noul algoritm de computer joacă poker aproape perfect

Nici cel mai bun chip de poker nu va funcționa împotriva unui nou cardsharp supraomenesc.

Pentru prima dată, un algoritm computerizat a rezolvat un joc de poker, heads-up limit Texas Hold’em, făcându-l imbatabil pe termen lung împotriva oricărui adversar. Realizarea, detaliată în 9 ianuarie Ştiinţăpoate ajuta la dezvoltarea strategiilor care maximizează rentabilitatea unei negocieri de afaceri sau minimizează riscul atacurilor teroriste – chiar dacă un adversar cunoaște strategia.

„Este un pas mare către înțelegerea jocurilor care sunt mai aproape de problemele din lumea reală”, spune Murray Campbell, un informatician la Centrul de Cercetare Thomas J. Watson al IBM din Yorktown Heights, NY. Campbell nu a fost implicat în studiu, dar a contribuit la dezvoltarea Deep Blue. , computerul care l-a învins pe campionul de șah Garry Kasparov în 1997.

Algoritmul, dezvoltat de informaticianul Michael Bowling și echipa sa de la Universitatea Alberta din Edmonton, este primul care abordează un joc de informații imperfecte jucat în mod obișnuit, în care participanții nu au cunoștințe complete despre evenimentele trecute. Așa cum jucătorii de poker trebuie să acționeze fără să cunoască cărțile pe care le deține adversarul lor, cercetătorii doresc algoritmi care să poată lua decizii eficiente bazate pe seturi de date solide, dar incomplete.

Timp de zeci de ani, oamenii de știință au încercat să creeze algoritmi care câștigă jocurile umane, combinând priceperea de calcul a computerelor cu strategiile de luare a deciziilor din teoria jocurilor. Teoria jocurilor este ramura matematicii care calculează strategiile optime în confruntările competitive. În 2007, informaticianul din Alberta Jonathan Schaeffer și colegii săi au rezolvat jocul damelor simulând acțiunile jucătorilor care fac mișcarea perfectă la fiecare rând (SN: 21.07.07, str. 36). A fost o realizare impresionantă, dar algoritmul avea o sarcină relativ simplă: pentru fiecare tură, revizuia pozițiile tuturor pieselor, își evalua opțiunile și apoi alegea cea mai bună.

Acest lux nu este oferit unui jucător de poker pe computer pentru că nu știe ce cărți deține un adversar. O altă problemă este că jucătorii de poker de succes sunt imprevizibili. La dame, cea mai bună mișcare într-o anumită situație este aceeași pentru fiecare joc. Dar în poker, este înțelept să blufezi din când în când, poate mărind miza o parte din timp cu o mână slabă pentru a arunca adversarul. „Majoritatea algoritmilor nu pot face față acestui tip de incertitudine”, spune Bowling.

Bowling și colegii săi de la Computer Poker Research Group din Alberta, în vârstă de 20 de ani, au ales să abordeze Texas Hold’em limită heads-up pentru că este popular și relativ simplu. Doi jucători primesc câte două cărți fiecare și apoi pot paria o sumă fixă ​​de un anumit număr de ori, pe măsură ce cinci cărți comunitare sau partajate sunt dezvăluite. Jocul are peste 300 de trilioane de situații diferite în care un jucător trebuie să plătească pariul, să ridice pariul sau să renunțe.

Echipa a dezvoltat un algoritm numit Cepheus care s-a apropiat treptat de perfecțiune, jucând împotriva lui însuși. După fiecare mână, Cepheus a calculat o măsură de regret, exploatând beneficiul retroviziunii pentru a determina cât de mult s-a îndepărtat de strategia optimă. Timp de două luni, Cepheus a rulat pe peste 4.000 de computere, fiecare jucând peste 6 miliarde de mâini pe secundă; algoritmul s-a îmbunătățit constant, deoarece și-a folosit regretul trecut pentru a-și ghida jocul. După aproximativ un miliard de miliarde de mâini – „sunt mai multe mâini de poker decât a jucat vreodată omenirea”, spune Bowling – regretul algoritmului a ajuns foarte aproape de zero, echivalentul matematic al jocului perfect.

Venind cu un set optim de probabilități pentru fiecare scenariu posibil dintr-o mână, cercetătorii s-au asigurat că Cepheus nu va pierde niciodată bani pe termen lung, în ciuda pierderii unor mâini. Asta ar fi valabil chiar dacă adversarul ar cunoaște strategia computerului. Bowlingul spune că Cepheus nu este un jucător perfect, dar jocul său nu se distinge de ideal în ceea ce privește numărul de mâini pe care o persoană le-ar putea juca într-o viață.

Deși Bowling nu plănuiește nicio confruntare de poker între computer și oameni (un computer a învins deja profesioniștii pokerului la limit Hold’em în 2008), el spune că programul, care este disponibil online, ar putea fi un instrument excelent pentru amatorii care învață jocul. Jucătorii aspiranți se pot confrunta cu un adversar perfect gratuit, mai degrabă decât să riscă bani mari împotriva unor profesioniști experimentați, dar inevitabil imperfecți.

Dincolo de poker, spune Bowling, oamenii de știință pot aplica această combinație fără precedent de inteligență artificială și teoria jocurilor la probleme majore din lumea reală, cum ar fi prinderea teroriștilor în aeroporturi și prinderea evasiva a tarifelor în sistemele de tranzit. În fiecare dintre aceste situații, oficialii trebuie să vină cu un plan de securitate care este eficient chiar dacă infractorii fie folosesc un atac surpriză, fie pun mâna pe plan.

Acum că Bowling și colegii au cucerit heads-up limit Hold’em, ei continuă să lucreze la Hold’em cu trei jucători și no-limit. Cercetătorii doresc, de asemenea, să dezvolte programe care exploatează adversarii slabi, spune Schaeffer. Cepheus nu pierde niciodată pe termen lung, dar nici nu se abate niciodată de la strategia sa. Profesioniștii de poker, pe de altă parte, își vor asuma cu plăcere riscuri pentru a sângera un adversar previzibil de jetoane. „Oamenii sunt ciudat de buni la asta”, spune Schaeffer.