เกมที่ถูกแก้แล้วหมายความว่าอย่างไร
เกมถูกแก้แล้วเมื่อรู้ผลลัพธ์ที่จะได้ถ้าผู้เล่นทั้งสองเล่นสมบูรณ์แบบตั้งแต่ตำแหน่งเริ่มต้น โดยทั่วไปมีสามระดับ ในการแก้แบบ «อ่อนมาก» รู้เพียงว่าใครชนะหรือเสมอ โดยไม่รู้กลยุทธ์ ในแบบ «อ่อน» รู้ด้วยว่ามีกลยุทธ์ที่รับประกันผลนั้นตั้งแต่ต้น ในแบบ «เข้ม» รู้ผลลัพธ์ที่ดีที่สุดจากตำแหน่งใดก็ได้
กรณีของ Connect 4 บนกระดานคลาสสิก 7 คอลัมน์ 6 แถว ผลลัพธ์ชัดเจน: ถ้าเล่นสมบูรณ์แบบ ผู้เล่นที่เริ่มก่อนชนะ ไม่ได้หมายความว่าจะชนะเสมอในทางปฏิบัติ เพราะต้องเดินให้ถูกในทุกตา และเกมระหว่างคนเต็มไปด้วยความผิดพลาด
ใครแก้ได้และเมื่อไร
เรื่องนี้มีตัวเอกสองคนที่สรุปได้ตรงกันโดยอิสระในเดือนตุลาคม 1988 คนแรกคือเจมส์ ดาว อัลเลน ซึ่งประกาศวิธีแก้ของเขาเมื่อวันที่ 1 ตุลาคม 1988 ในข้อความถึงกลุ่มสนทนา rec.games.programmer สิบห้าวันต่อมา วันที่ 16 ตุลาคม นักวิจัยชาวดัตช์ วิกเตอร์ อัลลิส นำเสนอวิธีแก้ของเขาเอง ซึ่งอธิบายไว้ในงาน «A Knowledge-based Approach of Connect-Four» จาก Vrije Universiteit
วิธีของอัลลิสเป็นแบบ «อิงความรู้» แทนที่จะตรวจทุกตำแหน่ง เขาตั้งกฎเชิงกลยุทธ์ เช่น ควรคุมช่องไหนและการคุกคามแบบไหนสำคัญ แล้วรวมกับการค้นหาเพื่อพิสูจน์ว่าผู้เล่นคนแรกบังคับให้ชนะได้ ต่อมามีผู้ได้ผลเดียวกันด้วยกำลังดิบ โดยใช้ฐานข้อมูลตำแหน่งและคอมพิวเตอร์ที่ทรงพลัง เช่น จอห์น ทรอมป์ โปรแกรมเมอร์ สร้างฐานข้อมูลของทุกตำแหน่งที่มีหมาก 8 ตัว ซึ่งใช้เป็นจุดเริ่มต้น ทั้งสองเส้นทางสอดคล้องกัน
กุญแจของการเปิดเกม: คอลัมน์กลาง
ตาแรกแบบไหนก็ได้ไม่พอ ผลลัพธ์ขึ้นอยู่กับคอลัมน์ที่ผู้เล่นคนแรกเริ่ม
| ตาแรก | ผลลัพธ์เมื่อเล่นสมบูรณ์แบบ |
|---|---|
| คอลัมน์กลาง (คอลัมน์ที่ 4) | ผู้เริ่มก่อนชนะ |
| คอลัมน์ข้างกลาง (คอลัมน์ที่ 3 และ 5) | เสมอ |
| คอลัมน์นอก (1, 2, 6 และ 7) | ผู้เล่นคนที่สองชนะ |
«ผู้เริ่มก่อนชนะ» ในทางปฏิบัติหมายความว่าอย่างไร
ทฤษฎีที่บอกว่าผู้เล่นคนแรกชนะ ไม่ได้รับประกันอะไรถ้าคู่ต่อสู้เล่นดี ความได้เปรียบมีจริง แต่ต้องการความแม่นยำ ถึงอย่างนั้น การเริ่มก่อนให้สองสิ่งที่จับต้องได้ สิ่งแรกคือเป็นฝ่ายริเริ่ม คุณเดินก่อน และคู่ต่อสู้มักต้องตอบสนองต่อการคุกคามของคุณ สิ่งที่สองคือความสมดุลของคู่คี่ ซึ่งเป็นกฎเชิงปฏิบัติที่ผู้เล่นรู้จักกันกว้างขวาง คือเพราะกระดานมี 6 แถว ซึ่งเป็นเลขคู่ และเล่นสลับตา ช่องในแถวคี่ (แถวที่ 1, 3 และ 5 นับจากล่าง) มักตกเป็นของผู้เริ่มก่อน และช่องในแถวคู่ตกเป็นของผู้เล่นที่สอง ดังนั้นการคุกคามในแถวคี่จึงมักมีค่ามากกว่าสำหรับผู้เล่นคนแรก
ทำไมตรงกลางจึงมีค่ามาก
หมากในคอลัมน์กลางอยู่ในเส้นที่เป็นไปได้มากกว่าคอลัมน์อื่นใด จากตรงกลางสร้างสี่ตัวเรียงได้ทั้งแนวนอน แนวตั้ง และทแยงสองทิศด้วยชุดผสมที่หลากหลาย หมากที่ขอบแทบใช้ได้เพียงหนึ่งหรือสองทิศ ด้วยเหตุนี้โปรแกรมที่แข็งแกร่งจึงเรียงลำดับการเดินจากตรงกลางออกไปด้านนอก และตำราการเปิดเกมจึงเริ่มจากคอลัมน์ 4
สำหรับคุณ กฎเชิงปฏิบัติง่าย ๆ คือ เมื่อไม่มีการเดินที่ดีกว่าอย่างชัดเจน ให้เลือกคอลัมน์ใกล้ตรงกลาง และถ้าคู่ต่อสู้ยึดตรงกลางก่อน ก็ไม่ต้องท้อ คอลัมน์ข้างเคียงยังดีมากอยู่
เคล็ดลับชนะบ่อยขึ้นเมื่อเล่นกับคน
- ถ้าเริ่มก่อน ให้เปิดที่คอลัมน์กลาง เป็นการเปิดเพียงแบบเดียวที่ชนะเมื่อเล่นสมบูรณ์แบบ
- มองหาการคุกคามคู่: สองเส้นของหมากสามตัวที่มีช่องปิดว่างอยู่พร้อมกัน คู่ต่อสู้บล็อกได้เพียงเส้นเดียว เป็นวิธีที่พบบ่อยที่สุดในการชนะคน
- คิดถึงการคุกคาม «ลอยอยู่กลางอากาศ»: เส้นของหมากสามตัวที่ช่องสุดท้ายยังเอื้อมไม่ถึง เพราะต้องมีหมากอยู่ด้านล่างก่อน ถ้าช่องนั้นอยู่ในแถวที่เหมาะกับคุณตามความสมดุลคู่คี่ ไม่ช้าก็เร็วคู่ต่อสู้ต้องเดินด้านล่างและมอบให้คุณ
- ก่อนปล่อยหมาก ดูว่าช่องที่ว่างอยู่เหนือขึ้นไปคือช่องไหน ถ้าคุณมอบช่องที่ทำให้คู่ต่อสู้ปิดเส้นได้ คุณก็แพ้แล้ว
- บล็อกเส้นของหมากสามตัวที่เปิดทั้งสองด้านก่อนที่จะเกิดขึ้น เพราะเป็นการแพ้แน่นอน มองไปข้างหน้าหนึ่งตา
- ช่วงท้ายเกม สิ่งสำคัญคือใครหมดการเดินที่ปลอดภัย ดูแลคอลัมน์ที่ยังเดินได้โดยไม่เสี่ยง
- ถ้าเป็นผู้เล่นที่สอง ให้มุ่งไปที่ช่องในแถวคู่ และบล็อกการคุกคามในแถวคี่ทุกครั้งโดยไม่รีบ เป็นทางที่ดีที่สุดไปสู่การเสมอหรือให้คู่ต่อสู้พลาด
แล้วคอมพิวเตอร์แพ้ไม่ได้หรือเปล่า
โปรแกรมที่เล่นสมบูรณ์แบบตั้งแต่ต้นและเริ่มก่อนจะไม่แพ้เลย แต่นั่นเป็นข้อความเกี่ยวกับผลเฉลยเชิงทฤษฎีของเกม ไม่ใช่เกี่ยวกับโปรแกรมใดก็ได้ การแก้เกมทั้งเกมจากตำแหน่งเริ่มต้นต้องคำนวณมหาศาล และในเบราว์เซอร์ที่มีเวลาเพียงหนึ่งวินาทีครึ่งต่อการเดิน ทำไม่ได้
ด้วยเหตุนี้ ระดับ «ไร้เทียมทาน» ของ Connect 4 ของเราจึงถูกนำเสนอตามความเป็นจริง คือระดับที่แข็งแกร่งที่สุด ใช้การค้นหาแบบ alpha-beta ด้วยการลึกซ้ำ ตารางที่จำตำแหน่งที่เคยเห็นแล้ว ลำดับคอลัมน์ที่เริ่มจากตรงกลาง และตำราเปิดเกมสั้นมาก วิเคราะห์การเดินล่วงหน้าหลายตาและแทบไม่ปล่อยให้พลาด แต่เราไม่รับประกันว่าชนะไม่ได้ ถ้าคุณเอาชนะได้ คุณชนะจริง ๆ
วิธีฝึก
วิธีพัฒนาฝีมือที่ดีคือเล่นกับคอมพิวเตอร์ในระดับยาก แล้วค่อยเล่นกับระดับไร้เทียมทาน สลับกันว่าใครเริ่ม เมื่อแพ้ ให้ทบทวนเกมและระบุว่าการคุกคามคู่ปรากฏตอนตาไหน แทบทุกครั้งสืบย้อนไปถึงการเดินเงียบ ๆ ก่อนหน้าได้ ควรลองแบบอื่นด้วย เช่น กระดานที่ใหญ่ขึ้นหรือโหมด PopOut ซึ่งบังคับให้คิดต่างออกไปและฝึกการมองกระดาน
คำถามที่พบบ่อย
ใครพิสูจน์ว่า Connect 4 ถูกแก้แล้ว
เจมส์ ดาว อัลเลน ประกาศเมื่อวันที่ 1 ตุลาคม 1988 และวิกเตอร์ อัลลิส นำเสนอวิธีแก้ของเขาโดยอิสระเมื่อวันที่ 16 ตุลาคม 1988 หลังจากนั้นมีการยืนยันด้วยกำลังดิบ
ใครชนะใน Connect 4 ถ้าเล่นสมบูรณ์แบบ
ผู้เล่นที่เริ่มก่อน ถ้าหมากแรกลงที่คอลัมน์กลางของกระดานคลาสสิก 7×6 ถ้าเริ่มที่คอลัมน์ข้างกลาง เกมเป็นการเสมอเชิงทฤษฎี และถ้าเริ่มที่หนึ่งในสี่คอลัมน์ริม ผู้เล่นที่สองชนะ
แปลว่าผู้เริ่มก่อนชนะเสมอไหม
ไม่ นั่นคือผลเมื่อไม่มีใครทำผิดพลาด ในทางปฏิบัติต้องเดินถูกในทุกตา และคนพลาดได้ การเริ่มก่อนเป็นความได้เปรียบ ไม่ใช่การรับประกัน
กระดานขนาดอื่นถูกแก้แล้วด้วยไหม
หลายขนาดถูกแก้แล้ว แต่ผลเปลี่ยนไปตามขนาด เช่น จอห์น ทรอมป์ รายงานว่ากระดาน 8×8 เป็นชัยชนะของผู้เล่นคนที่สอง บทความนี้หมายถึงเฉพาะกระดานคลาสสิก 7 คอลัมน์ 6 แถว
ระดับไร้เทียมทานไม่เคยแพ้หรือ
เราไม่รับประกัน เป็นระดับที่แข็งแกร่งที่สุดที่เรามี ด้วยการค้นหาลึกและคำนวณมากต่อการเดิน แต่ไม่ได้แก้เกมทั้งเกมในเวลาที่มี มีเฉพาะกระดานคลาสสิก 7×6
Connect 4 มีกี่ตำแหน่ง
มีการนับตำแหน่งที่ถูกกติกา 4,531,985,219,092 ตำแหน่งบนกระดาน 7×6 ตัวเลขที่ สเตฟาน เอเดลแคมป์ และ ปีเตอร์ คิสมันน์ ยืนยันโดยอิสระในปี 2008