‘Othello’ ถูกแก้ได้แล้วหรือยัง?

 (arxiv.org)
3 คะแนน โดย GN⁺ 2023-11-05 | 1 ความคิดเห็น | แชร์ทาง WhatsApp
  • 8×8 Othello/Reversi ได้รับการพิสูจน์เชิงคำนวณว่า เมื่อทั้งสองฝ่ายเล่นอย่างสมบูรณ์แบบ ผลลัพธ์สุดท้ายจะเป็น เสมอ จึงบรรลุสถานะการแก้แบบอ่อนตามเกณฑ์ของนักวิจัย
  • พื้นที่การค้นหามีขนาดใหญ่มาก โดยคาดว่าบันทึกเกมที่เป็นไปได้มีประมาณ 10^58 และตำแหน่งบนกระดานมีประมาณ 10^28 ทำให้ยังคงเป็นปัญหาที่ยากกว่ากรณีที่เคยแก้ได้อย่าง checkers มาก
  • ผลลัพธ์ครั้งนี้คือการหาค่า game-theoretic value ของตำแหน่งเริ่มต้นและกลยุทธ์ที่ทำให้ได้ค่านั้น ไม่ใช่การแก้แบบแข็งที่คำนวณตำแหน่งระหว่างเกมทั้งหมด
  • นักวิจัยใช้การค้นหาแบบฮิวริสติกบนซอฟต์แวร์ Othello และ alpha-beta search พร้อมอธิบายว่าขนาดการค้นหาที่จำเป็นสำหรับคำตอบที่แม่นยำนั้นเล็กกว่าที่เคยคาดการณ์ไว้
  • ข้อมูลดิบและโปรแกรมสำหรับทำซ้ำผลลัพธ์ถูกเผยแพร่บน GitHub, Zenodo และ figshare จึงสามารถใช้เป็นกรณีศึกษาที่ตรวจสอบได้ในการวิจัยการแก้เกมกลยุทธ์บริสุทธิ์

การแก้ Othello ด้วยการคำนวณ

  • Othello บนกระดาน 8×8 ถูกแก้แบบอ่อนแล้ว และค่าเชิงทฤษฎีเกมของตำแหน่งเริ่มต้นถูกคำนวณว่าเป็น เสมอ
  • หากทั้งสองฝ่ายเล่นอย่างดีที่สุดโดยไม่ผิดพลาด ผลจะเสมอ และงานวิจัยนี้ได้พิสูจน์เรื่องดังกล่าวเชิงคำนวณ
  • Figure 1 แสดงบันทึกเกมที่เหมาะที่สุดหนึ่งแบบและผลลัพธ์สุดท้าย
    • หากมีการออกนอกลำดับเดินดังกล่าว ณ จุดใดก็ตาม ซอฟต์แวร์ของนักวิจัยในฐานะฝ่ายตรงข้ามจะรับประกันผลเสมอหรือชนะได้
  • ผลลัพธ์นี้สอดคล้องกับการคาดการณ์ของผู้เชี่ยวชาญ Othello ที่เป็นมนุษย์ว่าเกมจะเสมอ นักวิจัยจึงมองว่าผลลัพธ์เองไม่ได้เหนือความคาดหมาย

ขอบเขตของการแก้และค่าเชิงทฤษฎีเกม

  • การแก้เกมที่มีข้อมูลสมบูรณ์หมายถึงการกำหนดผลลัพธ์สุดท้ายเมื่อทั้งสองฝ่ายเล่นอย่าง สมบูรณ์แบบ หรือก็คือ game-theoretic value
  • เกมที่ถูกแก้มักแบ่งออกเป็นสามระดับ
    • การแก้แบบอ่อนมาก (ultra-weakly solved): รู้เพียงค่าเชิงทฤษฎีเกมของตำแหน่งกระดานเริ่มต้น
    • การแก้แบบอ่อน (weakly solved): รู้ค่าเชิงทฤษฎีเกมของตำแหน่งเริ่มต้น และรู้กลยุทธ์ที่ทั้งสองฝ่ายจะทำให้ได้ค่านั้นภายในทรัพยากรคำนวณที่สมเหตุสมผล
    • การแก้แบบแข็ง (strongly solved): คำนวณผลลัพธ์ของทุกตำแหน่งที่เป็นไปได้ซึ่งอาจเกิดขึ้นระหว่างเกม
  • งานวิจัยนี้เป็นกรณีที่แก้ Othello แบบ อ่อน ไม่ใช่การแก้แบบแข็งที่คำนวณทุกตำแหน่งที่เป็นไปได้
  • checkers ก็ถูกยกเป็นตัวอย่างเกมที่ถูกแก้แบบอ่อนในความหมายเดียวกัน

เหตุผลที่ Othello ยังคงเหลืออยู่มานาน

  • Othello เป็นเกมยอดนิยมที่มีความลึกเชิงกลยุทธ์สูง ถูกประดิษฐ์ขึ้นในอังกฤษช่วงศตวรรษที่ 19 ก่อนที่รูปแบบปัจจุบันจะแพร่หลายในญี่ปุ่นช่วงศตวรรษที่ 20 และถูกเล่นทั่วโลก
  • การแข่งขันชิงแชมป์โลกจัดขึ้นทุกปีตั้งแต่ 1977 สะท้อนถึงความนิยมระดับโลก
  • พื้นที่การค้นหามีขนาดใหญ่มาก
    • เฉลี่ยประมาณ 10 ตาเดิน ต่อหนึ่งตำแหน่ง
    • เฉลี่ยประมาณ 58 ตาเดิน ต่อเกมทั้งหมด
    • บันทึกเกมที่เป็นไปได้ประมาณ 10^58
    • ตำแหน่งบนกระดานที่เป็นไปได้ประมาณ 10^28
  • ขนาดนี้ถูกระบุว่าใหญ่กว่าเกมที่เคยถูกแก้ในฐานะปัญหายากมาก่อน โดยเฉพาะ checkers อย่างมาก
  • ด้วยพื้นที่การค้นหาขนาดใหญ่ Othello จึงยังคงเป็นโจทย์ระยะยาวในวิทยาการคอมพิวเตอร์

วิธีการค้นหาและประสิทธิภาพการคำนวณ

  • นักวิจัยใช้ alpha-beta search โดยมีเป้าหมายเป็นการแก้แบบอ่อน
  • อัลกอริทึมแก้เกมแตกต่างกันไปตามเป้าหมายและลักษณะของเกม
    • การแก้แบบอ่อนมักใช้ alpha-beta search
    • การแก้แบบแข็งมักใช้ retrograde analysis
    • สำหรับพัซเซิลที่มีลำดับคำตอบยาวมาก มีการพัฒนาวิธีอย่าง df-pn search
  • alpha-beta search เป็นอัลกอริทึมที่ค้นหากราฟเกมตามลำดับในแบบ depth-first จึงยากที่จะเพิ่มประสิทธิภาพการค้นหาได้มากด้วยการทำ parallelization แบบง่าย ๆ เพียงอย่างเดียว
  • มีการศึกษาวิธีการค้นหาแบบขนานหลายแบบ
    • ในสภาพแวดล้อมหน่วยความจำร่วม YBWC และ Lazy SMP เป็นวิธีที่ได้รับความนิยม
    • ในสภาพแวดล้อมหน่วยความจำแบบกระจาย APHID และ ABDADA ถูกนำเสนอเป็นอัลกอริทึมที่เกี่ยวข้อง
  • ในสภาพแวดล้อมหน่วยความจำแบบกระจาย เงื่อนไขอย่างแบนด์วิดท์และเวลาแฝงระหว่างโหนดแตกต่างกันมาก นักพัฒนาจึงอาจต้องเลือกอัลกอริทึมที่เหมาะกับสภาพแวดล้อมหรือพัฒนาใหม่
  • แม้ใช้คลัสเตอร์คอมพิวเตอร์สมัยใหม่ การแก้ Othello ก็ยังเป็นอุปสรรคใหญ่ และจุดที่ทำให้เกิดความก้าวหน้าคือการปรับแต่งซอฟต์แวร์ Othello รุ่นใหม่เพื่อเพิ่มประสิทธิภาพการค้นหา

เกมอื่นที่ถูกแก้และความเป็นไปได้ในการนำไปใช้

  • ก่อน Othello ตัวอย่างล่าสุดของปัญหายากที่ถูกแก้ได้คือ checkers
  • เกมที่ไม่เรียบง่ายอย่าง Connect Four, Qubic, Go-Moku, Nine Men’s Morris และ Awari ก็ถูกระบุเป็นตัวอย่างที่ถูกแก้แล้ว
  • ความยากในการแก้เกมโดยทั่วไปขึ้นอยู่กับจำนวนตำแหน่งหรือสถานการณ์ภายในเกมเป็นอย่างมาก
  • การแก้เกมไม่ได้จำกัดอยู่แค่การเปิดเผยผลลัพธ์สุดท้าย แต่ยังสามารถนำไปใช้กับการ สร้างพัซเซิล ที่อิงจากเกมนั้นได้ด้วย
  • นักวิจัยจัดเตรียมข้อมูลดิบและโปรแกรมสำหรับทำซ้ำผลลัพธ์ไว้ที่ GitHub, Zenodo และ figshare

บทความที่เกี่ยวข้อง

1 ความคิดเห็น

 
GN⁺ 2023-11-05
ความคิดเห็นจาก Hacker News

  • บอกว่า “เลือก 2,587 ตำแหน่ง จากทั้งหมด 2,958,551 ตำแหน่ง แล้วตั้งสมมติฐานเกี่ยวกับผลลัพธ์ไว้ และถ้าสมมติฐานเหล่านี้ถูกทั้งหมด ก็จะพิสูจน์ได้ว่าตำแหน่งเริ่มต้นเป็นการเสมอ” แต่ไม่มีคำอธิบายละเอียดกว่านั้น
    ฟังดูเหมือนผู้เขียนพยายามหาลำดับเดินที่ชนะอย่างหนักแต่หาไม่เจอ มากกว่าจะเป็นการแก้เกมได้อย่างสมบูรณ์

    • ผมอ่านผ่าน ๆ แล้วเหมือนประโยคถัดไปและ Algorithm 1 จะอธิบายส่วนนี้
      มีเขียนไว้ว่า “มีหลายวิธีในการเลือกเซตย่อยที่สามารถพิสูจน์ได้ว่าตำแหน่งเริ่มต้นเป็นการเสมอ แต่เราใช้ Algorithm 1 เพื่อให้ได้เซตย่อยขนาดเล็ก”
      Algorithm 1 อธิบายว่า รับคะแนนทำนายของทุกตำแหน่งที่มีช่องว่าง 50 ช่อง แล้วคืนค่าเซตย่อยที่ “หากทุกตำแหน่งในเซตย่อยนั้นถูกแก้ และคำตอบตรงกับค่าทำนาย ตำแหน่งเริ่มต้นก็จะถูกแก้ตามไปด้วยในที่สุด”
    • ผมก็สับสนตรงนี้เหมือนกัน อ่าน论文สองรอบแล้วยังไม่แน่ใจว่าเข้าใจวิธีการหรือเปล่า
      โดยรวมแล้วการเขียนของ论文ไม่ค่อยเป็นเชิงสัญชาตญาณ ผู้เขียนอาจจะถูกก็ได้ แต่คงต้องนั่งไล่ตรรกะอย่างจริงจัง และความประทับใจแรกของผมคือยังค่อนข้างกังขา
    • การตีความที่ดูเป็นไปได้มากกว่าคือ 2,587 ตำแหน่งนั้นครอบคลุมความเป็นไปได้ทั้งหมด
      การพิสูจน์ลักษณะนี้มีที่อื่นด้วย เช่น ทฤษฎีบทสี่สี ก็ลดรูปเป็นจำนวนรูปแบบจำกัด แล้วใช้การลงสีด้วยมือ
    • ดูเหมือนว่าเขาคำนวณผลลัพธ์ของ ตำแหน่งที่มีช่องว่าง 36 ช่อง จำนวนมากบนคลัสเตอร์ แล้วอัปโหลดไว้ที่ https://figshare.com/articles/dataset/Analyses_of_the_Game_o...
      สคริปต์ที่ https://github.com/eukaryo/reversi-scripts/blob/main/reversi... เล่นได้อย่างสมบูรณ์ภายใต้สมมติฐานว่าทั้งหมดถูกต้อง สคริปต์อื่น ๆ ในรีโพซิทอรีใช้ข้อมูลที่คำนวณจากคำตอบของตำแหน่งว่าง 36 ช่อง และระดับนี้ดูเหมือนทำได้บนเครื่องทั่วไปด้วย
      โดยแก่นแล้วโครงสร้างน่าจะเป็นการค้นหาใน ตารางขนาดไม่เกิน 300GB ที่บรรจุตำแหน่งทั้งหมดที่มีช่องว่าง 37~64 ช่องซึ่งเข้าถึงได้จาก weak solution และแก้ตำแหน่งที่มีช่องว่างไม่เกิน 36 ช่องด้วย -solve ของ edax

  • Othello เป็นเกมที่เหมาะมากสำหรับแสดงให้เห็นว่าแค่ ฮิวริสติก พื้นฐานก็ทำให้แข็งแกร่งได้แค่ไหน
    ระหว่างเล่นเกมจะมีช่องที่ห้ามลงเด็ดขาด และในทางกลับกันก็มีช่องที่ถ้าเป็นไปได้ควรลงให้ได้
    แค่ทำกฎพวกนี้ก็กลายเป็นคู่ต่อสู้ที่ใช้ได้ทีเดียว และน่าสนใจที่เห็นว่าผู้คนมอบความเป็น “ปัญญา” ให้กับสิ่งที่เรียบง่ายมากได้รวดเร็วแค่ไหน

    • นานมาแล้วเคยอ่านบทความเกี่ยวกับการเขียนโปรแกรม Othello น่าจะเป็น BYTE Magazine ช่วงต้นทศวรรษ 1980
      เขาบอกว่าเอาแอปที่ใช้ฮิวริสติกง่าย ๆ คล้ายกัน ไปแข่งกับแอปที่ใช้กลยุทธ์ “พลิกให้ได้มากที่สุด” ซึ่งง่ายพอ ๆ กันแต่แย่มาก
      อัลกอริทึมแบบฮิวริสติกชนะขาดลอย จำได้ว่า 60 ต่อ 4 หรืออาจจะหนักกว่านั้นอีก
    • ผมยังจำได้ว่า โปรแกรม Pascal 200 บรรทัด ที่รันบน PDP-11 เคยชนะทุกคนในแล็บ
      พอเหลือช่องว่าง 19 ช่อง มันก็แก้เกมที่เหลือทั้งหมดได้เลย น่าทึ่งมาก
    • ไม่รู้จริง ๆ ว่าใครกันที่มอบ “ปัญญา” ให้กับสิ่งนี้
      Othello เป็นเกมที่เคยอยู่ใน เครื่องเกม LCD ราคา 10 ดอลลาร์ ที่ใส่ถ่าน AA สองก้อนด้วยซ้ำ

  • ถ้าสนใจเกม ตอนนี้ การแข่งขันชิงแชมป์โลก Othello ซึ่งได้รับความนิยมในหมู่นักวิทยาการคอมพิวเตอร์และนักวิจัยปัญญาประดิษฐ์ กำลังจัดอยู่ที่กรุงโรม ประเทศอิตาลี
    การแข่งขันถ่ายทอดสดที่ liveothello.com และ Youtube @WorldOthello -论文นี้ทำให้การแข่งขันชิงแชมป์หมดความหมายหรือเปล่า? ก็สงสัยด้วยว่ามีซอฟต์แวร์ที่อิงจาก论文นี้เข้าร่วมหรือไม่
    สงสัยว่า Othello เป็นเกมที่แมตช์ระดับสูงส่วนใหญ่จบเสมอเหมือนหมากฮอสหรือเปล่า

  • เจ๋ง
    ประมาณ 15 ปีก่อน ผมเคยแก้เกมที่ง่ายกว่านี้ซึ่งเล่นกับพี่น้อง เป็นเกมแอฟริกันที่มีหลุมประมาณฝั่งละ 10 หลุมบนกระดานและใส่เมล็ดหินลงไป
    พอเขียนเอนจิน alpha-beta มันก็พบ กลยุทธ์ที่ชนะเสมอ แบบเหลือเชื่อซึ่งปรับกับวิธีที่เราเล่นอยู่ หลังจากนั้นผมก็ชนะทุกกระดานขึ้นมาทันที และพี่น้องก็ไม่ยอมเล่นด้วยอีกเลย เป็นการดวลแบบคลาสสิกระหว่างนักวิทยาการคอมพิวเตอร์กับนักทัศนมาตรศาสตร์

    • เจ๋งจริง ผมเล่น Mancala มาหลายปีและอยากฟังเพิ่ม
      การดูชาวแอฟริกันสูงวัยเล่น Mancala มีอะไรให้เรียนรู้เยอะมาก พวกเขาเล่นเร็วมาก และให้ความรู้สึกเหมือนโป๊กเกอร์ที่การหลอกลวงเป็นส่วนหนึ่งของเกม
      ถ้าโปรยเมล็ดหินเร็วพอ ก็อาจข้ามถ้วยหนึ่งใบหรือหย่อนเมล็ดเพิ่มอีกเมล็ดเพื่อให้ได้เปรียบได้
      ผมไม่ได้ชำนาญขนาดนั้น และเล่นกับครอบครัวจึงไม่โกง แต่ถึงอย่างนั้นมันก็กลายเป็นเกมที่ต่างไปมาก เหมือนความแตกต่างระหว่างสุภาพสตรีอังกฤษจิบชาแล้วเล่น Mahjong ช้า ๆ กับการเล่นพนันเอาเงินจริงในบ่อนจีน
    • ถ้าอยากรู้เพิ่มเติม ดูได้ที่ https://en.wikipedia.org/wiki/Mancala
    • จำแหล่งที่มาไม่ได้ แต่เคยได้ยินว่าคนเราจะชอบเกมก็ต่อเมื่ออัตราชนะอยู่ในช่วง 30~70%
      ถ้าชนะมากเกินไปหรือแพ้มากเกินไป ก็จะไม่สนุกกับเกม
    • Mancala และ Connect Four เป็นตัวอย่างคลาสสิกของ เกมที่ถูกแก้แล้ว
      แต่ไม่รู้ว่าอาชีพนักทัศนมาตรศาสตร์เกี่ยวข้องอะไรตรงนี้

  • นี่จริงหรือเปล่า? รู้สึกแปลกนิดหน่อยที่ผู้เขียนมีคนเดียว และสังกัด สตาร์ทอัพด้านดีปเลิร์นนิง ที่ไม่เคยได้ยินชื่อมาก่อน

    • ตอนที่เขาเรียกผลงานตัวเองว่า monumental ผมถึงกับเลิกคิ้ว
      คงกำลังอยู่ระหว่างการ peer review อยู่ละมั้ง?
    • คนไร้ชื่อเสียงแก้ปัญหาใหญ่ได้ไม่ใช่เรื่องที่ไม่เคยเกิดขึ้น
      และ Othello ก็ไม่ได้อยู่ระดับเดียวกับสมมติฐานรีมันน์เสียทีเดียว งานวิจัยเกี่ยวกับมันจึงน้อยกว่า และอาจยังมีผลไม้ห้อยต่ำเหลืออยู่ก็ได้

  • Othello เป็นหนึ่งในเกมที่เหมาะมากสำหรับเล่นกับเด็ก ๆ
    กติกาเรียบง่าย มีแพตเทิร์นให้เรียนรู้ และยังสนุกกับการพลิกหมากจำนวนมากด้วย ที่สำคัญคือไม่ใช่แค่เด็ก ๆ แต่ผู้ใหญ่ก็สนุกได้พอ ๆ กัน
    ผมเองก็สนุกได้เต็มที่ โดยไม่ทำให้เด็ก 6 ขวบรู้สึกถูกกดดันจนเกินไป และก็ไม่รู้สึกเหมือนเป็นเกมที่พึ่งดวงล้วน ๆ

    • ในทำนองเดียวกัน เกมตระกูลหมากแอฟริกันอย่าง Hus ก็น่าลองดู
      https://mancala.fandom.com/wiki/Hus
      ในทางทฤษฎีไม่มีดวงเข้ามาเกี่ยว แต่ในทางปฏิบัติ ผลแบบลูกโซ่ทำให้คำนวณไปได้ไม่ไกลขนาดนั้น
      กระดานทำเองได้ง่าย ๆ
    • ด้วยเหตุผลคล้ายกัน ผมก็ชอบ Blokus ด้วย

  • ถ้าอยากลองเล่นเกมนี้ ผมอัปโหลดสิ่งที่ทำไว้กับเด็ก ๆ ไว้ที่นี่: https://jawj.github.io/fliptiles
    ผู้เล่น “AI” อ่อนมาก

    • ไม่รู้ว่าการเสมอนั้นน่าทึ่งแค่ไหน แต่ตาแรกได้ 32-32
      ได้เรียนรู้เกมใหม่แล้ว
    • น่าประทับใจ ตอนเด็ก ๆ ผมเล่นเกมนี้อยู่ตลอด แต่ลืมไปพักใหญ่แล้วว่ามันมีอยู่ พอกลับมาเล่นอีกทีก็สนุกดี
      คอมพิวเตอร์ได้ 33 คะแนน ส่วนผมได้ 31 คะแนน

  • ถ้าคิดว่า Othello เป็นเรื่องง่าย ๆ ลอง Zebra ดูก็ได้
    เว็บไซต์ผู้เขียนต้นฉบับ: http://radagast.se/othello/
    ซอร์สบน GitHub: https://github.com/hoshir/zebra

    • ถ้าไม่รู้จัก Othello มันก็ถูกเรียกว่า Reversi ด้วย

  • สิ่งที่ผมชอบใน Othello คือ ความขัดแย้งระหว่างการลงมือกับพื้นที่ครอบครอง
    ระหว่างที่เกมดำเนินไป การวางหมากในตาของตัวเองในแง่หนึ่งเป็นผลเสียต่อตัวเอง แต่ก็ยังจำเป็นต้องวาง
    ดังนั้นจนกว่าจะถึงจุดที่พื้นที่เล็กเกินไปและต้องกู้คืนอิทธิพลที่แน่นอนกลับมา คุณจึงต้องครอบครองพื้นที่ไปพร้อมกับรักษาตำแหน่งให้เล็กและอยู่ด้านใน

  • ที่เกี่ยวข้องกัน ยังมีการเล่น 6x6 Reversi แบบสมบูรณ์แบบด้วย
    https://mame.github.io/6x6-reversi-oracle/
    ที่มา: https://twitter.com/mametter/status/1476379841004183556
    เพิ่งรู้ตอนนี้เองว่า 8x8 ยังไม่ถูกแก้จนสมบูรณ์

    • ผมยังยึดหมากดำไม่ได้สักเม็ดเลย นี่คือความหมายของคำว่า “สมบูรณ์แบบ” หรือเปล่า?