După cum știti dintr-un post mai vechi, m-am decis să-mi dezvolt puțin abilitățile de game developer și să încerc să implementez câteva jocuri micuțe ca exercițiu de programare și să mă având puțin în afara tehnicilor arhicunoscute din programarea de zi cu zi din cadrul job-ului.
După ce mi-au trebuit câteva zile să învâț lucruri noi despre JavaScript și să implementez o versiune de Tetris, am început să mă gândesc la un joc care să necesite AI. Deși planul era să implementez Snake sau Escape, m-am apucat să studiez mai mult algoritmii despre Poker.
Am plecat cu ideea greșită că nu o să fie foarte complex, dar ca de obicei m-am înșelat. După ce am citit câteva articole mi-am dat seama că sunt multe probleme care trebuiesc rezolvate de AI-ul pentru poker, asta pe lângă aplicația de joc în sine (structuri pentru memorarea datelor, implementarea mesei de joc cu toate interacțiunile necesare, etc…)
Lista cu situațiile importante care trebuiesc rezolvate de un AI de poker am găsit-o deja într-un articol, și m-am gândit că ar fi interesant să fac o trecere în revistă (pentru cei care credeau că e simplu – la fel ca mine). Regulile se referă la Texas Hold’em, însă cu mici modificări cred că se poate aplica și la alte tipuri de poker.
1. Hand value
Sau determinarea câștigătorului e destul de simplă în aparență, însă procesarea poate dura destul de mult. De obicei se folosesc tabele de cu valori precalculate ca să micșoreze timpul de calcul. În general valoarea cărților din mână este evalută în câțiva pași. De asemenea, salvarea datelor în format binar poate ușura procesarea și ajută la micșorarea duratei de calcul.
2. Probabilitatea de câștig (hand strength)
Aici lucrurile nu stau deloc cum mă așteptam. Văzând în jocurile de poker și chiar la TV cifrele cu șansele de câștig afișate, putem să pun pariu că există o metodă clară de a stabili șansele de câștig. Citind însă diverse articole despre implementarea algoritmilor de poker se pare că nu este așa. Ca să determine probabilitatea de câștig, algoritmul simulează jocul de câteva ori (100-1000). În funcție de numărul de victorii în urma simulărilor, se determină șansele de câștig la un moment dat.
Simularea în principiu e simplă. Se amestecă pachetul de cărți. Se extrag cărțile jucătorilor, iar apoi se împart cărțile rămase. Se numără victoriile pentru fiecare jucător de fiecare dată, și aia e probabilitatea. Însă pentru a da mai multă acuratețe și a fi mai aproape de realitatea, simularea trebuie să țină cont de probabilitatea ca un jucător să iasă de la masă. Ceea ce nu chiar ușor de calculat, din moment ce ține cont de cărțile din mână, poziția la masă, numărul de jetoane pariate până la momentul respectiv, numărul de jetoane rămase, comportamentul din jocurile precedente.
Probabilitatea de câștig se salvează de obicei ca număr real având valori între 0 și 1, unde 1 înseamnă câștig sigur iar 0 infrângere sigură.
3. Fold, Call, Raise
La fiecare tură, calculatorul (AI) trebuie să decidă dacă se retrage, rămâne la masă, sau mărește miza jocului. Astfel de decizii se iau ținând cont de mai mulți factori:
- pot odds (cât plătești / cât poți câștiga)
- rate of return (probabilitatea de câștig / pot odds) – uneori, o stragetie simplă e să rămâi în joc când rate of return este mai mare ca 1
Mai departe decizia de fold/call/raise poate fi implementată folosind rate or return (RR).
- Dacă RR este sub 0.8, atunci 95% șanse ca playerul să iese din joc, 0% șanse să plătească miza, 5% șanse să crească miza (bluff)
- Dacă RR este între 0.8 și 1 atunci șansele sunt pentru 80% fold, 10% call și 10% raise (bluff)
- Dacă RR este între 1 și 1.3, atunci șansele de fold sunt 0%, call 60% și raise 40%
- Dacă RR este peste 1.3 atunci șansele sunt 0% fold, 30% call și 70% raise
- Dacă regulile de mai sus returnează fold, și suma cerută este 0, se face totuși call pentru a rămâne la masă
Ca reguli generale pentru a stabili acțiunea fold/call sau raise, niciodată nu trebuie să aveți 100% în dreptul unei acțiuni în niciuna din situații. Asta ar face ca adversarul să-și dea seama ușor ce mână ai în funcție de acțiunile tale. De aceea algoritmul mărește miza și când are o mână foarte proastă și când are o mână foarte bună.
De asemenea, modificând procentele de mai sus, se pot obține mai multe “caractere”, fiecare având stil de joc diferit.
Și o altă problemă încă neelucidată este cu cât să mărești miza atunci când o faci?
4. Ai grijă de jetoanele tale
Cu alte cuvinte AI trebuie să evite să ia decizii riscante atunci când mai are puține jetoane, iar șanse de câștig sunt mici.
5. Testarea
Ca să-ți dai seama cam cât de bun este caracterul creat, ar trebui ca acesta să joace contra unui adversar uman. Cum asta durează de obicei ceva timp, în viața de zi cu zi, se folosesc suite de teste (pentru situații specifice) și se practică jocul între diverse caractere AI. Astfel de jocuri (între algoritmi) pot să dureze și câteva secunde. În final testarea umană se face doar pentru a determina dacă există modalități de exploatare a modului de joc al unui “caractere”.
________
Cu atâtea chestii de rezolvat, cred că implementarea efectivă o să fie amânată puțin, sau dacă o încep o să fie fără AI, doar o platformă de Poker simplă. Se pare că jocul de poker are o întreagă industrie și cultură în spate. S-au scris cărți despre joc în sine, despre strategii. Am găsit chiar blog-uri dedicate implementării AI pentru poker. Există de asemenea librării C++ care pot fi folosite pentru a dezvolta cât mai rapid un astfel de joc. Sursa de inspirație pentru acest articol o găsiți aici.