CFR

Ikhtisar

Minimalisasi Penyesalan Kontrafaktual (CFR) adalah algoritma untuk menyelesaikan keseimbangan Nash dalam permainan zero-sum dua pemain. Algoritma ini diusulkan oleh Hart dan Mas-Colell dan kemudian diperkenalkan ke penelitian poker teori permainan oleh Zinkevich dkk. CFR merupakan tonggak sejarah dalam AI poker dan merupakan salah satu teknologi inti dari AI poker terkemuka seperti Libratus dan Pluribus. ## Prinsip Inti CFR secara iteratif menghitung 'penyesalan kontrafaktual' di setiap simpul keputusan—imbalan tambahan yang bisa diperoleh pemain dengan memilih tindakan alternatif daripada tindakan sebenarnya. Algoritma menyesuaikan strategi selanjutnya berdasarkan akumulasi nilai penyesalan, secara bertahap konvergen menuju keseimbangan Nash. Proses spesifik meliputi:

• Melintasi semua set informasi dalam pohon permainan.
• Menghitung nilai kontrafaktual dari setiap tindakan (dengan asumsi pemain mencapai set informasi tersebut dengan strategi saat ini).
• Memperbarui nilai penyesalan yang terakumulasi dan menghasilkan strategi baru sesuai (biasanya menggunakan pencocokan penyesalan). ## Aplikasi di Texas Hold'em Texas Hold'em adalah permainan informasi tidak sempurna yang khas dengan ruang keadaan yang sangat besar. CFR dan versi perbaikannya (misalnya, CFR+, Deep CFR) mengurangi kompleksitas komputasi melalui teknik abstraksi (seperti pengelompokan keadaan, pengelompokan tindakan) dan kemudian dilatih dengan komputasi paralel skala besar. Misalnya, Libratus menggunakan algoritma CFR yang dimodifikasi untuk mengalahkan pemain manusia top di Texas Hold'em tanpa batas. ## Fitur
• Jaminan teoretis: Dalam permainan zero-sum, CFR menjamin bahwa strategi rata-rata konvergen ke keseimbangan Nash.
• Tidak memerlukan pengetahuan sebelumnya: Mulai dari strategi acak seragam, secara otomatis mempelajari strategi optimal.
• Biaya komputasi tinggi: Melintasi pohon permainan lengkap tidak layak di Texas Hold'em tanpa batas dan memerlukan abstraksi dan pengambilan sampel. ## Keterbatasan CFR terutama cocok untuk permainan zero-sum dua pemain. Dalam permainan multipemain, konvergensi tidak dijamin secara teoretis, tetapi modifikasi (seperti Minimalisasi Penyesalan Kontrafaktual dengan pencarian maju) dapat mencapai hasil yang baik dalam praktik.