Poker Hand Evaluator and Mpok Erot (Part 1)

Bismillah

Disclaimer: this is a repost about poker hand evaluator written in
Bahasa Indonesia. If you search for English translation, visit
references section at the end of this post. Any comment or critic is
always welcomed. I always check my mailbox at 2 using scheduled
download (that means once every 12 hours), so don't be shame to drop
an email to prabowo.murti [AT] gmail [DOT] com.

Maaf, lagi2 gak sedang kesurupan jin Inggris..

Permainan poker di Facebook karya Zynga yang diberi nama
texasholdempoker entah kenapa membuat permainan poker Texas Holdem
Poker menjadi "sedikit" lebih terkenal di negeri ini, padahal kita
tahu situs poker online sudah menjamur sejak bertahun2 lalu. Orang
menjadi betah duduk berjam-jam di depan komputer, menjadi screen
sucker, untuk meraih chip demi chip. Tulisan ini
_bukan_ dimaksudkan untuk membuat Anda selalu menang
di permainan Texas Holdem Poker, _bukan_ pula untuk
menyiasati agar Anda bisa meraih jutaan chip. Tapi, kalau Anda mungkin
ingin berterima kasih, kirim aja cendol ijonya Gan.. Ntar saya cek
kolkas saya.. :D

Saya tahu sedikit aturan Texas Holdem Poker (bila Anda belum kenal
sama sekali dengan poker, mungkin ada baiknya Anda membaca tulisan
tentang aturan
bermain poker, karena terdapat banyak istilah poker dalam tulisan
ini). Yang tidak saya mengerti, bagaimana caranya Zynga (atau
pengembang software poker lain) membuat rangking dari poker hands yang
dimiliki para pemain? Hebatnya, dalam waktu singkat. Bayangkan, jika
permainan terus berlanjut hingga show down, artinya semua pemain terus
call/check hingga akhir, pemenang harus ditentukan dengan cara
0. Ambil 5 kartu terbaik yang mungkin dari 7 kartu yang tersedia, dari
masing2 pemain.
1. Tentukan rangking poker hands yang dibuat pemain, bandingkan dengan
poker hands pemain lain.
2. Bila ada lebih dari 1 orang yang memiliki rangking poker hands yang
sama, split pot. Bila hanya ada satu orang yang merajai permainan,
then we got the winner.

Tulisan ini fokus pada dua hal:
0. Menulis ulang tentang Poker Hand Evaluator dalam bahasa
Indonesia, dari tulisan2 yang sudah ada sebelumnya
(kebanyakan saya ambil dari tulisan Kevin Suffecool, namun banyak juga
dari referensi lain. Lebih jelas lihat bagian
"References" di bagian akhir tulisan ini). Apa itu
Poker Hand Evaluator? Hmm.. Apa ya? Hlo, kok malah jadi bingung saya?
Sejauh yang saya tahu, mungkin diterjemahkan menjadi pengevaluasi
poker hand, entah itu fungsi/program/aplikasi yang tujuannya
memberitahu Anda peringkat dari hand yang Anda punya. Dalam permainan
poker nyata, fungsi inilah yang (kira2) dipakai untuk menentukan
pemenang dari sebuah permainan poker, fungsi inilah yang mengetahui
apakah kartu Anda yang full house menang melawan double pair.
1. mPOK ERot, aplikasi sederhana yang "sedang" saya coba buat,
tujuannya mirip dengan poker hand evaluator yang sudah pernah
dibuat orang.

Kita sedikit mengulang pelajaran matematika (pelajaran yang hampir
membuat saya tidak lulus) di SMA, soal statistika sederhana. Ada
kasus: waktu lebaran tiba, keluarga Budi (yang terdiri dari Budi (B),
Ayah Budi (A), Ibu Budi (I), dan Wati(W) kakak budi), saling
bersalaman. Berapa kalikah proses salaman yang terjadi? Kalau kita
urut satu2..

A dengan I
A dengan W
A dengan B
I dengan W
I dengan B
W dengan B

Ada 6 (enam) salaman yang terjadi. Untuk mempermudah, ada yang disebut
dengan kombinasi atau dilambangkan dengan C (short for combination).
Penghitungannya adalah sebagai berikut

C(p, n) = p!/((p-n)! * n!)

dimana p = jumlah populasi, dan n adalah banyak sampel yang diambil.
Tanda "!" adalah faktorial, dimana

x! = x*(x-1)*(x-2)*...4*3*2*1

Sebagai contoh, 4! = 4x3x2x1 = 24, dan 1! = 1.

Apa manfaat dari kombinasi ini? Tujuannya menentukan banyaknya
kemungkinan kombinasi bila kita mengambil n buah sampel dari sejumlah
p. Kembali ke keluarga Budi, berarti kita bisa hitung kemungkinan
banyak salaman yang muncul..
Dari 4 orang yang tersedia, diambil 2 orang untuk bersalaman. Berarti
jumlah populasi = 4 (p=4), dan sampelnya 2 (n = 2).

C(4, 2) = 4!/((4-2)!*2!)
= 4x3x2x1 / (2x1 x 2x1) = 24 / 4 = 6.

Hasilnya sama, bukan? Lebih mudah dengan cara ini daripada mesti
mendaftar satu2 seperti cara sebelumnya.

Kembali ke poker hands. Dengan terdapat 52 kartu dalam deck,
kemungkinan 5 buah kartu yang mungkin dapat dicari.

C(52, 5) = 52! / ((52-5)! x 5!)
= (48x49x50x51x52) / (5x4x3x2x1)
= 2.598.960

Kita bisa lihat, ada lebih dari no tiao gopekceng alias lebih dari dua
juta lima ratus rebu kemungkinan kartu yang bisa dibuat. Walau begitu,
dalam Texas Holdem Poker, karena suit (atau "kembang" kalau sebagian
orang bilang) tidak berpengaruh dalam rangking (misal Straight Flush
23456 yang bersuit diamond sama rangkingnya dengan Straight Flush
23456 yang bersuit club/keriting), maka sebenarnya kita bisa bagi
lebih dari 2,5 juta kartu unik di atas menjadi beberapa grup yang
punya rangking sama. Misal, Royal Flush hanya ada empat macam

TJQKA club/keriting,
TJQKA heart/hati,
TJQKA diamond/wajik,
TJQKA spade/waru(daun hitam)

Dengan cara yang sama, kita bisa bagi kartu2 lain yang jumlahnya
jutaan itu menjadi hanya 7462 grup atau rangking, mulai dari Royal
Flush (TJQKA same suit) di peringkat pertama, hingga High Cards 75432
berbeda suit di peringkat paling bontot. Dari mana angka
7462 didapat? Karena sudah ada orang lain yang
menghitung dan kita tidak usah capek2 lagi.. (hehehe) Bila ingin
melihat urutan rangking hands mulai dari peringkat pertama hingga
7462, silakan lihat link pada bagian Referensi (di akhir tulisan ini).
Tabel ini didapat dari situs Cactus Kev (semua yang saya colong dari
orang, saya sebutin sumbernya)

Jenis Hand	Jumlah Kartu Unik	Dibagi Menjadi
Straight Flush	40	10
Four of a Kind	624	156
Full Houses	3744	156
Flush	5108	1277
Straight	10200	10
Three of a Kind	54912	858
Two Pair	123552	858
One Pair	1098240	2860
High Card	1302540	1277
TOTAL	2598960	7462

Masalah selanjutnya, bagaimana memetakan 2,5 juta kemungkinan kartu
tersebut ke 7462 rangking? Dari mana kita tahu, misal
2spade2spade4spade4club5diamond (untuk menyingkat, spade = s, club c,
diamond d, heart h), memiliki rangking yang sama dengan 2c2c4h4d5c
(kedua kartu sama2 double pair 2,4 dengan kicker 5)? Dalam daftar
peringkat, kedua kartu tersebut memiliki rangking ke 3313. Lalu, agar
problem lebih menarik, bagaimana caranya program mengetahui rangking
dari sebuah hands (lima kartu), walaupun urutannya dibolak-balik?
Misal, sesuai contoh di atas, 2c2c4h5c4d seharusnya sama peringkatnya
dengan 4d2c4h2c5c ?

Daripada mengurutkan lima buah kartu berdasarkan angkanya, yang mana
terlalu membuat program berjalan lebih lambat, cara Kevin Suffecool
adalah dengan memetakan masing rank card (2,3,4,5...dst hingga Ace)
menjadi bilangan prima. Tabelnya menjadi seperti berikut.

Ranking	Dua	Tiga	Empat	Lima	Enam	Tujuh	Delapan	Sembilan	Sepuluh	Jack	Queen	King	Ace
Prima	2	3	5	7	11	13	17	19	23	29	31	37	41

Dengan cara ini, Four of kind Ace dengan Kicker King, biar
bagaimanapun urutannya, pasti memiliki hasil perkalian yang sama.
Namun dengan cara ini, kita masih belum bisa mengetahui apakah kelima
kartu memiliki suit atau kembang yang sama atau berbeda.

Meet a special 4-byte representation of the card.. Empat byte ini
adalah representasi dari masing2 kartu, dengan format sebagai berikut.

xxxAKQJT 98765432 cdhsrrrr xxpppppp

xxx = tidak dipakai (3 bit pertama)
A-2 = menunjukkan rank dari card, mulai dari Ace hingga angka 2 (13bit)
cdhs = menunjukkan jenis suit/kembang (club, diamond, heart, spade) (4 bit)
rrrr = menunjukkan rank card mulai dari 0 (untuk angka 2) sampai 12
(untuk Ace) (4 bit)
xx= tidak dipakai (2 bit)
ppppp = prime number, bilangan yang menunjukkan hasil perkalian
bilangan prima (yang sebelumnya sudah diasosiasikan dengan masing2
rank card, nilainya antara 2, 3, 5, 7, dst hingga 41) (6 bit)

Mengapa kita memerlukan 4x8bit = 32 bit hanya untuk menyimpan
informasi tentang kartu? Kenapa tidak bikin sahaja, 6bit(0-63 alias
64, lebih dari cukup untuk menyimpan informasi kartu yang hanya 52)
saja misalnya? Ibu-ibu dan para remaja putri di rumah, pertanyaan ini
akan lebih jelas terjawab nanti, di penghujung acara.

Sehingga untuk merepresentasikan kartu 9 club/keriting, format kartunya adalah

00000000 10000000 10000111 00001011
xxxAKQJT 98765432 cdhsrrrr xxpppppp


Untuk masing-masing kartu, terdapat satu bentuk card format seperti di
atas. Maka kita punya c1, c2, c3, c4 dan c5. Langkah selanjutnya
adalah mencari tahu apakah hand merupakan flush (bisa flush atau
straight flush) atau tidak. Caranya dengan mengevaluasi
c1 AND c2 AND c3 AND c4 AND c5 AND 0xF000

AND pada operasi di atas adalah operasi bit. Karena diANDkan dengan
0xF000 (11110000 00000000), maka bit yang signifikan hanyalah bit yang
menunjukkan jenis suit card (cdhs). Bila kelima kartu adalah flush,
harusnya hasil dari operasi di atas tidak sama dengan 0 (nol).
Sebaliknya, bila hasilnya sama dengan 0, maka hand tidak membentuk
flush apalagi straight flush.

Bila flush yang terbentuk, langkah selanjutnya menurut langkah Kevin
adalah operasi berikut ini

q = (c1 OR c2 OR c3 OR c4 OR c5) >> 16

Operasi OR yang dipakai adalah operasi bit, dan dishift 16 bit ke
kanan. Hasil signifikannya adalah 16 bit (sebenarnya 13 bit saja dari
bit yang menunjukkan rank card) yang tepat 5 bitnya bernilai 1 (dalam
satu flush hand tidak mungkin ada 2 atau lebih kartu yang memiliki
rank card yang sama. Contoh, tidak mungkin ada dua nilai As dalam satu
kartu flush hand). Pola yang muncul memiliki nilai terkecil = 31 =
0x001F = 00000000 00011111 atau untuk straight flush hand STRAIGHT
FLUSH dengan rank card 23456. Sedangkan nilai yang paling besar adalah
7936 = 0x1F00 = 00011111 00000000 atau untuk straight flush hand
STRAIGHT FLUSH dengan rank card AKQJT.

Untuk mendapatkan nomer peringkat masing2 flush hand (total 1287
flush, baik straight flush (10 jenis), maupun flush biasa (1277
jenis)), Om Kevin yang baik hati membuat array berisi 7937 elemen yang
berisi nomer peringkat hand. Karena kita hanya membutuhkan 1287 elemen
yang berisi nomer peringkat hand, maka tidak heran bila kebanyakan
nilai dari array ini adalah 0 (nol), yakni elemen yang tidak akan
pernah diakses sampai kiamat kelak. Misal bila poker hand kita adalah
flush 98754, maka nilai q = 00000000 11101100 = 236 (desimal), maka
rangking card flush 98754 adalah flushes[236] = peringkat 1551 atau
Nine High Flush. Uhuy!

....sebentar, saya haus, minum dulu...

Bila ternyata hand yang dimiliki bukan flush, maka langkah selanjutnya
menurut Kevin adalah mencari tahu apakah kartu termasuk straight atau
high card (karena bila rank card semua kartu (ada 5 kartu) bersifat
unik dan bukan pada suit yang sama, kemungkinanya hanyalah kartu
tersebut tergolong STRAIGHT atau High Card). Lagi2, terdapat array
unique5[] yang berisi 7937 elemen, di mana indexnya adalah nilai q dan
valuenya adalah peringkat atau ranking dari hand yang bersangkutan.
Sebagai contoh, bila poker hand kita adalah A9763 (non-flush) maka
nilai q = 00010000 10110010 = 4274 (desimal). Maka peringkat/rangkin
hand tersebut adalah unique5[4274] = peringkat 6627. Bila kita lihat
di tabel rangking hands (yang jumlahnya 7462), urutan ke 6627, ketemu
deh, Ace High Card... Voila!

Bila ada 1287 flush, dan 1277 high card, serta 10 straight, maka kita
sudah mengeliminasi 2574 rangking dari 7462 rangking yang ada. Ingat
bilangan prima yang terdapat dalam format kartu di atas? Marii..

q = (c1 AND 0xFF) * (c2 AND 0xFF) * (c3 AND 0xFF) * (c4
AND 0xFF) * (c5 AND 0xFF)

Hasil dari operasi bit di atas adalah hasil perkalian bilangan prima
(yang sudah dipetakan ke masing2 rank card) semua kartu dalam hands.
Hasilnya berkisar antara 48 (untuk kartu 22223 alias 2x2x2x2x3) hingga
104.553.157(untuk kartu AAAAK). Sampai di sini, cara yang digunakan
Kevin untuk mencari nilai rangking dari hands adalah
- menghitung semua hasil perkalian dan menyimpannya dalam sebuah array
- mencari dengan metode pencarian biner (binary search) dalam array
(yang sebelumnya sudah diurutkan)
- nilai index yang didapat, digunakan sebagai index pada array lain
(berukuran 4888), yang isinya adalah rangking dari hands tersebut.

Dalam algoritma yang disempurnakan oleh Paul Senzee, digunakan hash
function (daripada binary search) sehingga waktu pemrosesan dapat
lebih cepat..

...sebentar, saya ngangkat jemuran dulu....

Untuk mencoba poker hand evaluator dari Kevin Suffecool, bisa download
source codenya dari situsnya langsung [0]. Saya coba2 memporting ke
PHP, dan hasilnya untuk yang non-hash sebagai berikut.

Cactus Kev's Hand Evaluator, by Kevin Suffecool
-----------------------------------------------

Enumerating and evaluating all 2,598,960 unique five-card poker hands...

Total time: 70 seconds
Category 1 : 40
Category 2 : 624
Category 3 : 3744
Category 4 : 5108
Category 5 : 10200
Category 6 : 54912
Category 7 : 123552
Category 8 : 1098240
Category 9 : 1302540

Sedang untuk yang menggunakan hash, sampai saat ini saya masih belum
mengerti kenapa hasilnya salah.

Cactus Kev's Hand Evaluator, by Kevin Suffecool
-----------------------------------------------

Enumerating and evaluating all 2,598,960 unique five-card poker hands...

Total time: 58 seconds
Category 1 : 227856
Category 2 : 435628
Category 3 : 18736
Category 4 : 5108
Category 5 : 10200
Category 6 : 108644
Category 7 : 116384
Category 8 : 373864
Category 9 : 1302540

Nanti saya coba ubek2 lagi. Lalu, mana aplikasi Mpok Erot yang saya
buat? Sabar saudara2... Karena tulisan ini bersambung ke bagian ke-2..
:D

References (Thanks to all of these guys)
[0] Cactus Kev's Poker Hand Evaluator by Kevin Suffecool. http://www.suffecool.net/poker/evaluator.html
[1] Paul Senzee (perfect hash optimization) http://www.senzee5.com/2006/06/some-perfect-hash.html
[2] 5-card poker hands. Brian Alspach. http://www.math.sfu.ca/~alspach/comp18
[3] http://pokerforprogrammers.blogspot.com
[4] James Devlin. http://www.codingthewheel.com/archives/poker-hand-evaluator-roundup
[5] Enumerating Five card poker hands, by Kevin Suffecool. http://www.suffecool.net/poker/7462.html