Mastering Stratego เกมคลาสสิกของข้อมูลที่ไม่สมบูรณ์

DeepNash เรียนรู้การเล่น Stratego ตั้งแต่เริ่มต้นโดยการรวมทฤษฎีเกมเข้ากับ Deep RL ที่ไม่มีโมเดล

ระบบปัญญาประดิษฐ์ (AI) สำหรับการเล่นเกมได้ก้าวไปสู่พรมแดนใหม่ ตอนนี้ Stratego เกมกระดานคลาสสิกที่ซับซ้อนกว่าหมากรุกและเกมโกะ และซับซ้อนกว่าโป๊กเกอร์ ได้รับการฝึกฝนจนชำนาญแล้ว เผยแพร่ใน Science เรานำเสนอ ดีพแนชเอเจนต์ AI ที่เรียนรู้เกมตั้งแต่เริ่มต้นจนถึงระดับผู้เชี่ยวชาญของมนุษย์ด้วยการเล่นกันเอง

DeepNash ใช้วิธีการใหม่โดยยึดตามทฤษฎีเกมและการเรียนรู้แบบเสริมแรงเชิงลึกโดยไม่ใช้โมเดล สไตล์การเล่นของมันบรรจบกับสมดุลของแนช ซึ่งหมายความว่าการเล่นของมันนั้นยากมากสำหรับคู่ต่อสู้ที่จะเอาเปรียบ ในความเป็นจริงแล้ว DeepNash ติดอันดับหนึ่งในสามของผู้เชี่ยวชาญด้านมนุษย์บนแพลตฟอร์ม Stratego ออนไลน์ที่ใหญ่ที่สุดในโลก Gravon

ในอดีตเกมกระดานเป็นตัววัดความก้าวหน้าในด้าน AI ทำให้เราสามารถศึกษาว่ามนุษย์และเครื่องจักรพัฒนาและดำเนินกลยุทธ์อย่างไรในสภาพแวดล้อมที่มีการควบคุม Stratego เป็นเกมที่แตกต่างจากหมากรุกและโกะตรงที่ข้อมูลไม่สมบูรณ์: ผู้เล่นไม่สามารถสังเกตตัวตนของชิ้นส่วนของฝ่ายตรงข้ามได้โดยตรง

ความซับซ้อนนี้หมายความว่าระบบ Stratego ที่ใช้ AI อื่น ๆ พยายามดิ้นรนเพื่อให้เกินระดับมือสมัครเล่น นอกจากนี้ยังหมายความว่าเทคนิค AI ที่ประสบความสำเร็จอย่างสูงที่เรียกว่า “game tree search” ซึ่งก่อนหน้านี้เคยใช้เพื่อควบคุมเกมที่มีข้อมูลสมบูรณ์แบบหลายเกมนั้นไม่สามารถปรับขนาดได้เพียงพอสำหรับ Stratego ด้วยเหตุนี้ DeepNash จึงก้าวไปไกลกว่าการค้นหาผังเกมโดยสิ้นเชิง

คุณค่าของการเรียนรู้ Stratego เป็นมากกว่าการเล่นเกม เพื่อบรรลุพันธกิจของเราในการแก้ปัญหาข่าวกรองเพื่อพัฒนาวิทยาศาสตร์และเป็นประโยชน์ต่อมวลมนุษยชาติ เราจำเป็นต้องสร้างระบบ AI ขั้นสูงที่สามารถทำงานได้ในสถานการณ์ที่ซับซ้อนในโลกแห่งความจริงโดยมีข้อมูลที่จำกัดของเจ้าหน้าที่และบุคคลอื่น บทความของเราแสดงให้เห็นว่า DeepNash สามารถนำไปใช้ในสถานการณ์ที่ไม่แน่นอนและสร้างความสมดุลให้กับผลลัพธ์เพื่อช่วยแก้ปัญหาที่ซับซ้อนได้อย่างไร

ทำความรู้จักกับ Stratego

Stratego เป็นเกมแบบเทิร์นเบส ยึดธง มันเป็นเกมแห่งการประจบประแจงและกลยุทธ์ การรวบรวมข้อมูลและการหลบหลีกที่ละเอียดอ่อน และเป็นเกมที่ผลรวมเป็นศูนย์ ดังนั้นการได้แต้มใด ๆ จากผู้เล่นคนใดคนหนึ่งย่อมแสดงถึงความสูญเสียในระดับเดียวกันของฝ่ายตรงข้าม

Stratego เป็นสิ่งที่ท้าทายสำหรับ AI ส่วนหนึ่งเนื่องจากเป็นเกมที่มีข้อมูลที่ไม่สมบูรณ์ ผู้เล่นทั้งสองเริ่มต้นด้วยการจัดชิ้นส่วนการเล่น 40 ชิ้นในรูปแบบเริ่มต้นที่พวกเขาชอบ โดยเริ่มแรกจะซ่อนจากกันเมื่อเกมเริ่มขึ้น เนื่องจากผู้เล่นทั้งสองไม่สามารถเข้าถึงความรู้เดียวกันได้ พวกเขาจึงต้องสร้างสมดุลระหว่างผลลัพธ์ที่เป็นไปได้ทั้งหมดเมื่อทำการตัดสินใจ ซึ่งเป็นเกณฑ์มาตรฐานที่ท้าทายสำหรับการศึกษาปฏิสัมพันธ์เชิงกลยุทธ์ ประเภทของชิ้นส่วนและการจัดอันดับแสดงไว้ด้านล่าง

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

แนวทางการเรียนรู้ของเครื่องซึ่งทำงานได้ดีกับเกมข้อมูลที่สมบูรณ์แบบ เช่น AlphaZero ของ DeepMind นั้นไม่สามารถถ่ายโอนไปยัง Stratego ได้อย่างง่ายดาย ความจำเป็นในการตัดสินใจด้วยข้อมูลที่ไม่สมบูรณ์แบบและศักยภาพในการบลัฟ ทำให้ Stratego คล้ายกับ Texas Hold’em Poker และต้องการความสามารถที่เหมือนมนุษย์ ซึ่งครั้งหนึ่ง Jack London นักเขียนชาวอเมริกันกล่าวไว้ว่า “ชีวิตไม่ได้เป็นเรื่องของการครอบครองเสมอไป ไพ่ดีแต่บางครั้งเล่นไพ่ไม่ดี”

อย่างไรก็ตาม เทคนิค AI ที่ทำงานได้ดีในเกมอย่าง Texas Hold’em นั้นไม่ได้ถ่ายโอนไปยัง Stratego เนื่องจากความยาวของเกม – บ่อยครั้งที่มีการเคลื่อนไหวหลายร้อยครั้งก่อนที่ผู้เล่นจะชนะ การให้เหตุผลใน Stratego ต้องทำกับการกระทำตามลำดับจำนวนมากโดยไม่มีข้อมูลเชิงลึกที่ชัดเจนว่าการกระทำแต่ละอย่างส่งผลต่อผลลัพธ์สุดท้ายอย่างไร

สุดท้าย จำนวนสถานะของเกมที่เป็นไปได้ (แสดงเป็น “ความซับซ้อนของแผนผังเกม”) นั้นผิดไปจากแผนภูมิเมื่อเทียบกับหมากรุก โกะ และโป๊กเกอร์ ทำให้ยากต่อการแก้ปัญหาอย่างมาก นี่คือสิ่งที่ทำให้เราตื่นเต้นเกี่ยวกับ Stratego และเหตุใดจึงเป็นตัวแทนของความท้าทายที่ยาวนานหลายทศวรรษสำหรับชุมชน AI

แสวงหาความสมดุล

DeepNash ใช้แนวทางใหม่โดยอิงจากการผสมผสานระหว่างทฤษฎีเกมและการเรียนรู้เชิงลึกแบบไม่ต้องใช้โมเดล “ไม่มีโมเดล” หมายความว่า DeepNash ไม่ได้พยายามจำลองสถานะเกมส่วนตัวของฝ่ายตรงข้ามอย่างชัดเจนในระหว่างเกม โดยเฉพาะอย่างยิ่งในช่วงแรกของเกม เมื่อ DeepNash รู้เพียงเล็กน้อยเกี่ยวกับชิ้นส่วนของฝ่ายตรงข้าม การสร้างแบบจำลองดังกล่าวจะไม่ได้ผลหรือเป็นไปไม่ได้

และเนื่องจากความซับซ้อนของแผนผังเกมของ Stratego นั้นกว้างใหญ่มาก DeepNash จึงไม่สามารถใช้วิธีการที่เข้มงวดของเกมที่ใช้ AI – การค้นหาแผนผังมอนติคาร์โล การค้นหาแบบต้นไม้เป็นส่วนประกอบสำคัญของความสำเร็จที่สำคัญมากมายใน AI สำหรับเกมกระดานและโป๊กเกอร์ที่ซับซ้อนน้อยกว่า

DeepNash ขับเคลื่อนโดยแนวคิดอัลกอริทึมเชิงทฤษฎีเกมใหม่ที่เราเรียกว่า Regularized Nash Dynamics (R-NaD) การทำงานในระดับที่เหนือชั้น R-NaD นำพาพฤติกรรมการเรียนรู้ของ DeepNash ไปสู่สิ่งที่เรียกว่าสมดุลของแนช (ดูรายละเอียดทางเทคนิคในเอกสารของเรา

พฤติกรรมการเล่นเกมที่ส่งผลให้เกิดความสมดุลของแนชนั้นไม่สามารถใช้ประโยชน์ได้เมื่อเวลาผ่านไป หากบุคคลหรือเครื่องจักรเล่น Stratego ที่ไม่สามารถใช้ประโยชน์ได้อย่างสมบูรณ์แบบ อัตราการชนะที่แย่ที่สุดที่พวกเขาสามารถบรรลุได้คือ 50% และเฉพาะเมื่อเผชิญหน้ากับคู่ต่อสู้ที่สมบูรณ์แบบในทำนองเดียวกันเท่านั้น

ในการแข่งขันกับบอท Stratego ที่ดีที่สุด – รวมถึงผู้ชนะหลายคนของ Computer Stratego World Championship – อัตราการชนะของ DeepNash สูงถึง 97% และมักจะสูงถึง 100% เมื่อเทียบกับผู้เล่นที่เป็นมนุษย์ที่เชี่ยวชาญบนแพลตฟอร์มเกม Gravon แล้ว DeepNash ได้รับอัตราการชนะถึง 84% ทำให้ติดอันดับสามอันดับแรกตลอดกาล

คาดหวังที่ไม่คาดคิด

เพื่อให้บรรลุผลลัพธ์เหล่านี้ DeepNash ได้แสดงพฤติกรรมที่โดดเด่นบางอย่างทั้งในช่วงเริ่มต้นของการปรับใช้ชิ้นส่วนและในช่วงการเล่นเกม เพื่อให้ใช้ประโยชน์ได้ยาก DeepNash ได้พัฒนากลยุทธ์ที่คาดเดาไม่ได้ ซึ่งหมายความว่าการสร้างการปรับใช้ครั้งแรกจะแตกต่างกันมากพอที่จะป้องกันไม่ให้ฝ่ายตรงข้ามตรวจพบรูปแบบในชุดเกม และในระหว่างช่วงของเกม DeepNash จะสุ่มระหว่างการกระทำที่ดูเหมือนเท่าเทียมกันเพื่อป้องกันแนวโน้มที่จะเอารัดเอาเปรียบ

ผู้เล่น Stratego พยายามที่จะคาดเดาไม่ได้ ดังนั้นการปกปิดข้อมูลจึงมีประโยชน์ DeepNash แสดงให้เห็นว่ามันให้คุณค่ากับข้อมูลในรูปแบบที่โดดเด่นมากเพียงใด ในตัวอย่างด้านล่าง กับผู้เล่นที่เป็นมนุษย์ DeepNash (สีน้ำเงิน) ได้สังเวย 7 (พันตรี) และ 8 (พันเอก) ในช่วงต้นเกม และเป็นผลให้สามารถระบุตำแหน่ง 10 (จอมพล) ของฝ่ายตรงข้ามได้ 9 (ทั่วไป), 8 และ 7 สองตัว

ความพยายามเหล่านี้ทำให้ DeepNash เสียเปรียบด้านวัตถุอย่างมาก มันสูญเสีย 7 และ 8 ในขณะที่ฝ่ายตรงข้ามที่เป็นมนุษย์รักษาชิ้นส่วนทั้งหมดของพวกเขาในอันดับที่ 7 ขึ้นไป อย่างไรก็ตาม DeepNash ประเมินโอกาสชนะที่ 70% และชนะ

ศิลปะของการบลัฟ

เช่นเดียวกับในโป๊กเกอร์ ผู้เล่น Stratego ที่ดีต้องแสดงถึงความแข็งแกร่งในบางครั้ง แม้ว่าจะอ่อนแอก็ตาม DeepNash ได้เรียนรู้กลยุทธ์การบลัฟที่หลากหลาย ในตัวอย่างด้านล่าง DeepNash ใช้ 2 (ลูกเสือที่อ่อนแอซึ่งฝ่ายตรงข้ามไม่รู้จัก) ราวกับว่ามันเป็นชิ้นส่วนระดับสูงไล่ตามฝ่ายตรงข้ามที่ทราบ 8 ฝ่ายตรงข้ามที่เป็นมนุษย์ตัดสินใจว่าผู้ไล่ตามน่าจะเป็น 10 และพยายาม เพื่อล่อให้มันเข้ามาซุ่มโจมตีโดย Spy ของพวกเขา กลยุทธ์นี้โดย DeepNash ซึ่งเสี่ยงเพียงเศษเสี้ยวเล็กๆ ประสบความสำเร็จในการล้างข้อมูลและกำจัด Spy ของฝ่ายตรงข้ามซึ่งเป็นชิ้นส่วนสำคัญ

ดูเพิ่มเติมด้วยการดูวิดีโอทั้งสี่ของเกมความยาวเต็มซึ่งเล่นโดย DeepNash กับผู้เชี่ยวชาญของมนุษย์ (ไม่เปิดเผยชื่อ): เกมที่ 1 เกมที่ 2 เกมที่ 3 เกมที่ 4

“ระดับการเล่นของ DeepNash ทำให้ฉันประหลาดใจ ฉันไม่เคยได้ยินเกี่ยวกับผู้เล่น Stratego เทียมที่เข้าใกล้ระดับที่จำเป็นในการชนะการแข่งขันกับผู้เล่นที่มีประสบการณ์ แต่หลังจากเล่นกับ DeepNash ด้วยตัวเอง ฉันไม่แปลกใจกับการจัดอันดับ 3 อันดับแรกที่ประสบความสำเร็จในภายหลังบนแพลตฟอร์ม Gravon ฉันคาดหวังว่ามันจะทำได้ดีมากหากได้รับอนุญาตให้เข้าร่วมการแข่งขันชิงแชมป์โลกของมนุษย์”
‍
– Vincent de Boer ผู้เขียนร่วมและอดีตแชมป์โลก Stratego

ทิศทางในอนาคต

ในขณะที่เราพัฒนา DeepNash สำหรับโลกแห่ง Stratego ที่มีคำจำกัดความสูง วิธีการ R-NaD แบบใหม่ของเราสามารถนำไปใช้กับเกมผลรวมศูนย์ที่มีผู้เล่นสองคนอื่นๆ ได้โดยตรง ทั้งข้อมูลที่สมบูรณ์แบบและไม่สมบูรณ์ R-NaD มีศักยภาพในการสรุปได้มากกว่าการตั้งค่าเกมสำหรับผู้เล่นสองคนเพื่อแก้ไขปัญหาในโลกแห่งความเป็นจริงขนาดใหญ่ ซึ่งมักมีลักษณะเฉพาะจากข้อมูลที่ไม่สมบูรณ์และช่องว่างทางดาราศาสตร์

นอกจากนี้ เรายังหวังว่า R-NaD จะสามารถช่วยปลดล็อกแอปพลิเคชันใหม่ของ AI ในโดเมนที่มีผู้เข้าร่วมจำนวนมากที่เป็นมนุษย์หรือ AI ที่มีเป้าหมายต่างกัน ซึ่งอาจไม่มีข้อมูลเกี่ยวกับความตั้งใจของผู้อื่นหรือสิ่งที่เกิดขึ้นในสภาพแวดล้อมของพวกเขา เช่น ในสภาพแวดล้อมขนาดใหญ่ -ปรับขนาดการจัดการจราจรให้เหมาะสมเพื่อลดเวลาการเดินทางของผู้ขับขี่และการปล่อยมลพิษของยานพาหนะที่เกี่ยวข้อง

ในการสร้างระบบ AI ที่ใช้งานทั่วไปได้ซึ่งแข็งแกร่งเมื่อเผชิญกับความไม่แน่นอน เราหวังว่าจะนำความสามารถในการแก้ปัญหาของ AI มาสู่โลกที่คาดเดาไม่ได้ของเรา

‍

เรียนรู้เพิ่มเติมเกี่ยวกับ DeepNash โดยอ่านเอกสารของเราใน Science

สำหรับนักวิจัยที่สนใจทดลองใช้ R-NaD หรือทำงานกับวิธีการที่เราเสนอใหม่ เราได้เปิดซอร์สโค้ดของเราแล้ว