Connect Four AI — เล่นกับเอนจิน Minimax

AI Connect Four นี้เป็นคู่ต่อสู้ที่ใช้การค้นหาจริง ไม่ใช่บอตที่เขียนสคริปต์ไว้ล่วงหน้าหรือเล่นแบบสุ่ม คุณเลือกเล่นเป็นแดงหรือเหลือง (แดงเริ่มก่อนตามกติกามาตรฐาน) เลือกระดับความยาก แล้วเริ่มหยอดหมากโดยคลิกที่คอลัมน์หรือลูกศรเหนือคอลัมน์ หมากจะเคลื่อนที่ลงมาแบบมีอนิเมชันจนถึงแถวล่างสุด การเรียงสี่ตัวติดกันจะถูกตรวจจับทันทีในทุกทิศทาง — แนวนอน แนวตั้ง และแนวทแยงทั้งสอง — และบรรทัดสถานะสั้น ๆ จะบอกเสมอว่าตอนนี้เป็นตาของใครหรือประกาศผู้ชนะ

กลไกเบื้องหลัง AI คือการค้นหาแบบ negamax พร้อม alpha-beta pruning ซึ่งเป็นอัลกอริทึมตระกูลเดียวกับที่ใช้ในเอนจินเกมกระดานคลาสสิก: มันสำรวจแผนภูมิของตาเดินที่เป็นไปได้ในอนาคต โดยให้แต่ละฝ่ายพยายามเพิ่มผลลัพธ์ของตัวเองให้มากที่สุดในขณะที่สมมุติว่าคู่ต่อสู้ก็เล่นดีเช่นกัน และตัดกิ่งที่ไม่สามารถเปลี่ยนผลลัพธ์ได้เมื่อพบบรรทัดที่ดีกว่าแล้ว เนื่องจาก Connect Four มีเพียงเจ็ดคอลัมน์ให้เลือก การค้นหานี้จึงมองไปข้างหน้าได้หลายตาอย่างรวดเร็ว มันทำงานด้วย iterative deepening — ค้นหาทีละความลึก หนึ่งชั้น สองชั้น สามชั้น ไปเรื่อย ๆ — ภายในงบเวลาสั้น ๆ ต่อตา (ประมาณหนึ่งในสี่วินาทีในระดับง่าย ไปจนถึงประมาณหนึ่งวินาทีครึ่งในระดับยาก) เบราว์เซอร์จึงไม่ค้างระหว่างรอตาเดิน

เมื่อการค้นหาไม่สามารถไปถึงจุดสิ้นสุดของเกมภายในความลึกที่กำหนด ตาเดินจะถูกตัดสินด้วย heuristic การประเมินตำแหน่งจริง ไม่ใช่การเดา: ทุกหน้าต่างสี่ช่องต่อเนื่องกันบนกระดานจะถูกให้คะแนนตามจำนวนหมากของแต่ละสีที่อยู่ในนั้น (หน้าต่างว่างไม่มีคะแนน หน้าต่างที่มีแต่หมากของคุณยิ่งเต็มยิ่งได้คะแนนมากขึ้น หน้าต่างที่ถูกทั้งสองสีปิดกั้นไม่มีคะแนน) และช่องในคอลัมน์กลางจะนับคะแนนมากกว่าเพราะมีส่วนร่วมในแนวที่เป็นไปได้มากกว่า ระดับง่ายและปานกลางจะเพิ่มการสุ่มแบบควบคุมเล็กน้อยในกลุ่มตาเดินที่คะแนนใกล้เคียงกันมาก ทำให้ AI รู้สึกเป็นมนุษย์และเอาชนะได้มากขึ้น ระดับยากจะเลือกตาเดินที่ดีที่สุดที่พบเสมอ นี่คือคู่ต่อสู้แบบ minimax ที่แข็งแกร่งจริง ๆ ซึ่งสร้างจากการค้นหาและการประเมินจริง — ไม่ใช่การอ้างว่าเล่นไม่แพ้หรือสมบูรณ์แบบ และไม่ใช่การจำลองอะไรทั้งสิ้น: ทุกตาเดินเป็นผลลัพธ์จริงจากอัลกอริทึมข้างต้น