เกมรวมเลขสองเกม คำถามเดียว: เกมใดเกมหนึ่งเล่นได้อย่างไร้ที่ติหรือไม่? คำตอบลากผ่านมุมของกระดาน คู่ต่อสู้ที่ไม่มีวันมาถึง และตัวเลขที่สูงถึงสิบเจ็ดเลขชี้กำลัง
เขียนและเรียบเรียงเป็นภาษาอังกฤษ ฉบับภาษาไทยนี้จัดทำขึ้นด้วยการแปลด้วยเครื่อง ในจุดที่ความแม่นยำมีความสำคัญ ให้ถือต้นฉบับภาษาอังกฤษเป็นหลัก อ่านต้นฉบับภาษาอังกฤษ →
เริ่มจากเกมที่ทุกคนรู้จัก 2048 ซึ่งมีสี่ทิศทาง ตาราง 4×4 และไทล์ที่เพิ่มเป็นสองเท่าเมื่อชนกัน ในทางเคร่งครัดแล้วยังไม่มีใครไขได้ ยังไม่มีใครเขียนอัลกอริทึมที่เล่นมันได้อย่างสมบูรณ์แบบ สิ่งที่เรามีคือการประมาณที่แข็งแกร่งมาก การค้นหาแบบ expectimax ที่มองล่วงหน้าไปราวแปดตาเดิน และให้คะแนนกระดานแต่ละแบบด้วยฮิวริสติกที่ปรับด้วยมือเพียงไม่กี่ข้อ ได้แก่ จำนวนช่องว่าง ไทล์ใหญ่ที่ถูกตรึงไว้กับขอบ และความราบเรียบ ไปถึงไทล์ 32768 ได้ในเกมมากกว่าหนึ่งในสาม 1 และเอนจินสาธารณะที่แข็งแกร่งที่สุดไปแตะไทล์ 65536 ได้ในไม่กี่เปอร์เซ็นต์ของเกม 2 เมื่อขยายเป็นกระดาน m×n แบบทั่วไป เพียงแค่การตัดสินว่าไทล์เป้าหมายไปถึงได้หรือไม่ก็เป็นปัญหา NP-hard แล้ว 3 เก่งไม่ได้แปลว่าไขได้
ไทล์เดียวไต่ขึ้นไปได้สูงแค่ไหน? บนสิบหกช่อง คำตอบคือการนับเล็ก ๆ ที่งดงาม วางกระดานเป็นบันไดไล่ลง 65536, 32768, 16384 ลงไปเรื่อย ๆ จนถึงเลข 2 ตัวเดียว ไทล์แต่ละตัวต่ำกว่าตัวข้างเคียงหนึ่งกำลังของสองพอดี ดังนั้นกำลังที่แตกต่างกันทั้งสิบหกค่าตั้งแต่ 21 ถึง 216 จึงเติมกระดานได้พอดี และ 65536 = 216 ก็อยู่บนยอดสุด หนึ่งเลขชี้กำลังต่อหนึ่งช่อง นั่นคือเพดานหากเกมให้คุณแต่เลข 2 เท่านั้น แต่ 2048 สร้างเลข 4 หนึ่งครั้งในสิบครั้ง และเลข 4 ที่มาถูกจังหวะเพียงตัวเดียวก็ลักลอบนำเลขชี้กำลังตัวที่สิบเจ็ดเข้ามา ยกค่าสูงสุดที่แท้จริงขึ้นเป็น 131072 = 217 คือกำลังมูลค่าสิบเจ็ดไทล์ที่อัดอยู่ในสิบหกช่อง 4 ยังไม่มีมนุษย์คนใดสร้างมันได้ มี AI เพียงไม่กี่ตัวที่เฉียดเข้าไปใกล้
ทำไมกระดานเหล่านี้จึงให้รางวัลกับการซุกไทล์ที่ใหญ่ที่สุดไว้ในมุม? ไทล์ที่อยู่ตรงกลางถูกดันได้สี่ทาง และมันจะถูกพรากจากไทล์ที่มันอยากรวมด้วยอยู่ร่ำไป ไทล์ที่มุมแตะผนังสองด้าน การดันเข้าหาผนังที่มันแนบอยู่แล้วไม่อาจขยับมันได้ และตราบใดที่คุณเลี่ยงการดันออกจากผนังเหล่านั้น มันก็จะอยู่นิ่งขณะที่ทุกอย่างจัดระเบียบรอบตัวมัน ร้อยไทล์ที่เหลือเป็นงูที่เรียงลำดับทางเดียว ตัวสูงสุดอยู่ที่มุม แล้วพับไปพับมาตามลำดับจากมากไปน้อย การปัดเพียงครั้งเดียวก็อาจจุดชนวนการรวมต่อเนื่องเป็นทอด ๆ ได้ 1 นี่คือฮิวริสติกที่ครองการเล่นแบบลำลองของมนุษย์ และแทบจะเป็นสิ่งเดียวกับที่ AI ค้นพบซ้ำเมื่อคุณปล่อยให้มันปรับน้ำหนักของตัวเอง
เกมรวมเลขที่ไทล์ใหม่เกิดแบบสุ่มไม่มีคู่ต่อสู้ มีเพียงดินฟ้าอากาศ การ “ไข” มันคือการเอาชนะลูกเต๋าโดยเฉลี่ย ไม่ใช่การเอาชนะจิตใจของใคร
ทีนี้ลองเอียงกระดานเข้าสู่สามมิติ 3927 คือญาติทรงลูกบาศก์ของ 2048 เป็นโครงตาข่าย 3×3×3 ที่มี 27 ช่อง มีทิศทางการเลื่อนหกทิศแทนที่จะเป็นสี่ และไทล์ที่หลอมรวมกันทีละสาม 3 เป็น 9 เป็น 27 เป็น 81 เป็นฐานสามในขณะที่ 2048 เป็นฐานสอง 5 การซ้อนไทล์ไว้ที่มุมจะยังได้ผลในมิติที่เพิ่มขึ้นหรือไม่? ลูกบาศก์มีแปดมุม และช่องที่มุมตอนนี้แตะหน้าสามด้านแทนที่จะเป็นสอง มันจึงน่าจะมั่นคงยิ่งขึ้นไปอีก เพราะถูกผนังสามด้านตรึงไว้พร้อมกัน แม้ว่าหกทิศทางจะทำให้กระดานมีวิธีเขย่าโครงสร้างของคุณให้หลุดได้มากขึ้นก็ตาม งูกลายเป็นเส้นทางพับที่ร้อยผ่านทั้งสามชั้น เท่าที่ฉันค้นหาได้ ยังไม่มีใครพิสูจน์ว่าการเปรียบเทียบนี้ใช้ได้จริงหรือไม่ นี่คือการใช้เหตุผล ไม่ใช่การวัด
แล้วเพดานล่ะ? กฎหนึ่งเลขชี้กำลังต่อหนึ่งช่องจะชี้ว่า 327 ≈ 7.6 ล้านล้าน เป็นขอบเขตบนอย่างหลวม ๆ แต่การเปรียบเทียบนี้ขาดวิ่นอย่างหนัก เลขชี้กำลังส่วนเกินของ 2048 มาจากเลข 4 ที่โชคดี ส่วน 3927 สร้างเพียงไทล์ที่เล็กที่สุด คือเลข 3 เปล่า ๆ เท่านั้น จึงไม่มีโบนัสใด ๆ ที่แย่กว่านั้นคือ การรวมสามต้องการไทล์สามตัวที่เรียงอยู่ในแนวเดียวกัน และทุกแถว ทุกคอลัมน์ และทุกเสาบนลูกบาศก์ 3×3×3 ยาวสามช่องพอดี ดังนั้นการรวมทุกครั้งจะกินทั้งแนวไปหมด ข้อจำกัดนี้กัดแรงกว่าสิ่งใดในเกมแบบแบนราบมาก และแทบแน่นอนว่าจะฉุดค่าสูงสุดที่แท้จริงให้ต่ำกว่า 327 ไปไกล ตัวเลขที่แท้จริงนั้นเป็นเท่าใด ฉันไม่พบว่ามีใครคำนวณไว้ที่ไหนเลย (นี่คือการใช้เหตุผลที่ระบุไว้ชัดเจน ส่วนกลไกข้างต้นวัดจากเอกสารการออกแบบของเกม)
นี่คือความละเอียดอ่อนที่ทำให้ “การเล่นที่สมบูรณ์แบบ” จับต้องได้ยาก เกมรวมเลขที่ไทล์ใหม่เกิดแบบสุ่มคือเกมเชิงสุ่มสำหรับผู้เล่นคนเดียว เป็นเกมเล่นคนเดียวที่แข่งกับลูกเต๋า ไม่ใช่การดวล ไม่มีสิ่งใดเลือกการเกิดไทล์ที่เลวร้ายที่สุดเพื่อทำลายคุณ มีเพียงตัวสร้างเลขสุ่ม (RNG) ที่ไม่แยแส ดังนั้นแนวคิดที่ถูกต้องของการเล่นที่เหมาะสมที่สุดคือ expectimax คือการทำให้ผลลัพธ์คาดหมายสูงสุดตามการกระจายของการเกิดไทล์ มันไม่ใช่ minimax อย่างเด็ดขาด เพราะ minimax สันนิษฐานว่ามีปรปักษ์ และหากคุณปล่อยให้ปรปักษ์เป็นผู้วางไทล์ทุกตัวจริง ๆ (“evil 2048”) เกมจะกลายเป็นสิ่งที่โหดร้ายกว่าซึ่งคุณอาจถูกบีบให้แพ้ได้ เนื่องจากโดยหลักการแล้วลูกเต๋าสามารถแจกลำดับใดก็ได้ กลยุทธ์ที่รับประกันว่าจะได้ไทล์หนึ่ง ๆ จึงอาจไม่มีอยู่เลย ดังนั้นคำตอบที่ซื่อตรงต่อคำถาม “มีกลยุทธ์ที่สมบูรณ์แบบหรือไม่?” คือ สำหรับเกมเชิงสุ่ม สิ่งที่ดีที่สุดที่เราจะนิยามได้ก็คือกลยุทธ์ที่ดีที่สุดโดยเฉลี่ย และการคำนวณมันออกมาอย่างแม่นยำนั้นเกินเอื้อมสำหรับ 2048 6 และยังเป็นคำถามเปิดกว้างสำหรับ 3927