CFR

ภาพรวม

การลดความเสียใจเชิงตรงกันข้าม (CFR) เป็นอัลกอริธึมสำหรับแก้สมดุลแนชในเกมผลรวมเป็นศูนย์สองผู้เล่น อัลกอริธึมนี้ถูกเสนอโดย Hart และ Mas-Colell และต่อมาถูกนำเข้าสู่การวิจัยโป๊กเกอร์ทฤษฎีเกมโดย Zinkevich และคณะ CFR เป็นจุดเปลี่ยนสำคัญใน AI โป๊กเกอร์และเป็นหนึ่งในเทคโนโลยีหลักของ AI โป๊กเกอร์ชั้นนำ เช่น Libratus และ Pluribus ## หลักการสำคัญ CFR คำนวณ 'ความเสียใจเชิงตรงกันข้าม' ซ้ำๆ ที่แต่ละโหนดการตัดสินใจ—ผลตอบแทนเพิ่มเติมที่ผู้เล่นจะได้รับหากเลือกการกระทำอื่นแทนการกระทำจริง อัลกอริธึมจะปรับกลยุทธ์ที่ตามมาตามค่าความเสียใจที่สะสม ค่อยๆ ลู่เข้าสู่สมดุลแนช กระบวนการเฉพาะรวมถึง:

• วนซ้ำเซตข้อมูลทั้งหมดในแผนภูมิเกม
• คำนวณค่าเชิงตรงกันข้ามของการกระทำแต่ละอย่าง (สมมติว่าผู้เล่นไปถึงเซตข้อมูลนั้นด้วยกลยุทธ์ปัจจุบัน)
• อัปเดตค่าความเสียใจที่สะสมและสร้างกลยุทธ์ใหม่ตามนั้น (โดยปกติใช้ regret matching) ## การประยุกต์ใช้ในเท็กซัสโฮลเดม เท็กซัสโฮลเดมเป็นเกมข้อมูลไม่สมบูรณ์ทั่วไปที่มีพื้นที่สถานะมหาศาล CFR และเวอร์ชันที่ปรับปรุงแล้ว (เช่น CFR+, Deep CFR) ลดความซับซ้อนในการคำนวณผ่านเทคนิคนามธรรม (เช่น การจัดกลุ่มสถานะ การจัดกลุ่มการกระทำ) จากนั้นฝึกด้วยการคำนวณแบบขนานขนาดใหญ่ ตัวอย่างเช่น Libratus ใช้อัลกอริธึม CFR ที่ดัดแปลงเพื่อเอาชนะผู้เล่นระดับสูงในเท็กซัสโฮลเดมไม่มีขีดจำกัด ## คุณสมบัติ
• การรับประกันทางทฤษฎี: ในเกมผลรวมเป็นศูนย์ CFR รับประกันว่ากลยุทธ์เฉลี่ยลู่เข้าสู่สมดุลแนช
• ไม่ต้องมีความรู้ล่วงหน้า: เริ่มจากกลยุทธ์สุ่มสม่ำเสมอ เรียนรู้กลยุทธ์ที่เหมาะสมที่สุดโดยอัตโนมัติ
• ต้นทุนการคำนวณสูง: การวนซ้ำแผนภูมิเกมทั้งหมดไม่สามารถทำได้ในเท็กซัสโฮลเดมไม่มีขีดจำกัด และต้องมีการนามธรรมและการสุ่มตัวอย่าง ## ข้อจำกัด CFR เหมาะสำหรับเกมผลรวมเป็นศูนย์สองผู้เล่นเป็นหลัก ในเกมหลายผู้เล่น การลู่เข้าไม่ได้รับการรับประกันทางทฤษฎี แต่การดัดแปลง (เช่น การลดความเสียใจเชิงตรงกันข้ามรวมกับการค้นหาไปข้างหน้า) สามารถให้ผลลัพธ์ที่ดีในทางปฏิบัติ