การสำรวจกราฟแบบมอนติคาร์โลที่เริ่มจากหลักการพื้นฐาน

 (github.com/lightvector)
3 คะแนน โดย GN⁺ 2024-03-11 | 1 ความคิดเห็น | แชร์ทาง WhatsApp

หลักการพื้นฐานของการสำรวจกราฟแบบมอนติคาร์โล

  • Monte Carlo Tree Search (MCTS) เมื่อนำไปใช้กับกราฟมีทิศทางแทนที่จะเป็นต้นไม้ จะกลายเป็น "Monte Carlo Graph Search" ("MCGS") ซึ่งบางครั้งถูกมองว่านำไปติดตั้งใช้งานได้ยาก
  • เอกสารอ้างอิงทางวิชาการที่มีอยู่มักอธิบาย MCTS แบบ "มาตรฐาน" สำหรับต้นไม้ จึงทำให้การทำความเข้าใจเชิงแนวคิดในการขยายไปสู่กราฟเป็นเรื่องยาก
  • เอกสารนี้นำเสนอคำอธิบายที่มองว่าเข้าใจได้ตรงไปตรงมามากกว่า ซึ่งโดยแก่นแล้วเทียบเท่ากันแต่สะอาดกว่า และอนุมานจากหลักการพื้นฐานว่าทำไมการสำรวจกราฟจึงต้องทำงานในลักษณะนี้

บทนำ / พื้นหลัง

  • ในการสำรวจต้นไม้ของเกมหรือการประยุกต์ใช้การสำรวจต้นไม้อื่น ๆ อาจพบลำดับของการเดินหรือการกระทำหลายแบบที่นำไปสู่สถานะเดียวกันได้
  • ตัวอย่างเช่น ในหมากรุก 1. d4 d5 2. Nf3 จะนำไปสู่ตำแหน่งเดียวกับ 1. Nf3 d5 2. d4
  • เมื่อสถานการณ์แบบนี้เกิดขึ้นได้ในเกม จำนวนความเป็นไปได้จะเพิ่มขึ้นแบบทวีคูณตามความลึกของการสำรวจ ทำให้การสำรวจลึกมีต้นทุนสูงเกินความจำเป็น
  • ในอุดมคติ เราต้องการให้กิ่งก้านของการสำรวจลักษณะนี้แชร์การคำนวณร่วมกัน
  • อย่างไรก็ตาม การติดตั้งใช้งาน MCTS แบบมาตรฐานจะมองเกมเป็นต้นไม้แตกกิ่ง และสำรวจตำแหน่งที่ซ้ำกันในต้นไม้ซ้ำอย่างไม่มีประสิทธิภาพ

คำอธิบายทั่วไปของ MCTS - ต้นไม้ของสถิติการรัน

  • MCTS มักถูกอธิบายว่าเป็นอัลกอริทึมที่ติดตามสถิติการรันของ playout ที่ผ่านโหนดต่าง ๆ ในต้นไม้
  • แต่ละโหนดแทนสถานะหนึ่งเดียวของเกม และติดตามจำนวนครั้งที่เข้าชม (N) กับค่าเฉลี่ยสะสม (Q) ของค่าอรรถประโยชน์ที่ถูกสุ่มตัวอย่างโดย playout
  • การวนซ้ำหนึ่งครั้งหรือ playout หนึ่งครั้งของ MCTS ประกอบด้วยการไล่ลงไปตามต้นไม้พร้อมสุ่มตัวอย่างการกระทำถัดไปที่จะสำรวจ ขยายต้นไม้เมื่อไปถึงสถานะใหม่ ประเมินค่าอรรถประโยชน์ U ของสถานะใหม่นั้น แล้วไล่ย้อนกลับขึ้นต้นไม้โดยเพิ่ม N ที่แต่ละโหนดและอัปเดตค่าเฉลี่ย Q ด้วยค่าอรรถประโยชน์ U ใหม่ที่สุ่มได้

อะไรที่ผิดพลาดเมื่ออยู่บนกราฟ?

  • หากนำอัลกอริทึมข้างต้นไปใช้แบบตรง ๆ กับกราฟมีทิศทางแบบไม่มีวัฏจักรแทนต้นไม้ อัลกอริทึมอาจไม่ถูกต้อง
  • นี่เป็นเพราะโดยทั่วไป MCTS ถูกอธิบายในแง่ของสถิติการรันของ playout ในฐานะที่เป็นส่วนขยายของวิธีการแบบ multi-armed bandit
  • Czech, Korus และ Kersting ได้แก้ปัญหานี้และพัฒนาอัลกอริทึมที่มีความถูกต้องเชิงทฤษฎี แต่ยังมีอีกแนวทางหนึ่งที่มอง MCTS จากมุมของการเรียนรู้นโยบายออนไลน์
  • ในคำอธิบายทางเลือกนี้ การทำให้เป็นกราฟทั่วไปจะเกิดขึ้นอย่างค่อนข้างเป็นธรรมชาติ

มอง MCTS ใหม่ในฐานะการหาค่านโยบายที่เหมาะที่สุดแบบทำให้เป็นมาตรฐาน

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

การทำ Monte Carlo Graph Search อย่างถูกต้อง

  • ปัญหาทั้งหมดที่เกิดขึ้นเมื่อต่อยอด MCTS ไปเป็นกราฟ มีต้นตอมาจากการสมมติว่าการเข้าชมโหนดลูกมาจากโหนดพ่อแม่เพียงอย่างเดียว
  • ทฤษฎีรับประกันว่าจำนวนการกระทำสะสมที่ PUCT เลือกนั้นให้ค่านโยบายภายหลังที่ประมาณนโยบายที่ถูกปรับให้เหมาะที่สุด π ดังนั้นจึงควรติดตามสิ่งนี้
  • หากใช้การตีความว่าค่า Q ที่โหนดรายงานคือค่าคาดหมายของนโยบายภายหลัง ก็สามารถใช้สูตร Q แบบเวียนเกิดซ้ำได้โดยไม่ต้องไปจัดการว่าควรคำนวณ playout รายตัวอย่างไร

การอภิปรายเกี่ยวกับตัวเลือกในการติดตั้งใช้งาน

  • อัลกอริทึมที่นำเสนอในเอกสารนี้คล้ายกับอัลกอริทึมของ Czech, Korus และ Kersting มาก แต่มีตัวเลือกด้านการติดตั้งใช้งานและความแตกต่างเล็กน้อยบางประการ
  • มีหลายวิธีที่อาจเลือกใช้เพื่อให้การติดตั้งใช้งานง่ายขึ้น เช่น กลยุทธ์เพื่อลดความ "ล้าสมัย" ของค่า Q หรือการใช้อัปเดตแบบเดียวกันแทนการอัปเดตแบบค่อยเป็นค่อยไป

ความเห็นของ GN⁺

  • บทความนี้อาจดึงดูดผู้ที่สนใจด้านปัญญาประดิษฐ์และทฤษฎีเกม ด้วยการนำเสนอความซับซ้อนของ Monte Carlo Graph Search (MCGS) และแนวทางใหม่ในการทำความเข้าใจมัน
  • อัลกอริทึมอย่าง MCTS มีบทบาทสำคัญในเกมวางกลยุทธ์ที่ซับซ้อน เช่น หมากรุกและโกะ และมีส่วนช่วยต่อการพัฒนา AI สำหรับเกมเหล่านี้
  • อย่างไรก็ตาม เนื้อหาที่บทความนี้กล่าวถึงอาจค่อนข้างยากสำหรับวิศวกรซอฟต์แวร์ระดับเริ่มต้น และต้องอาศัยพื้นฐานทางทฤษฎี
  • ประเด็นที่ต้องพิจารณาเมื่อทำ MCGS คือจะสร้างสมดุลระหว่างประสิทธิภาพกับความถูกต้องของอัลกอริทึมอย่างไร ซึ่งอาจส่งผลอย่างมากต่อประสิทธิภาพในสภาพแวดล้อมเกมจริง
  • โครงการหรือผลิตภัณฑ์อื่นที่ให้ความสามารถคล้ายกัน ได้แก่ AlphaZero ของ DeepMind ซึ่งไปถึงระดับที่เหนือกว่ายอดมนุษย์ในหมากรุก โกะ และโชกิ

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

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

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

  • การสำรวจกราฟเป็นสิ่งจำเป็นต่อความก้าวหน้าในการให้เหตุผลของปัญญาประดิษฐ์ และ LLM แบบเรียบง่ายเพียงอย่างเดียวคงจะล้มเหลว ลิงก์นี้มีแหล่งอ้างอิงดี ๆ มากมาย รวมถึง Zobrist hashing สำหรับตารางเกมด้วย จำเป็นต้องหาแฮชที่ดีสำหรับคำอธิบายสถานะแบบอิงภาษา เพื่อไม่ให้การสำรวจกราฟระเบิดในเชิงคำนวณ งานอ่านที่ดีเกี่ยวกับ tree search ได้แก่ 'Thinking Fast and Slow' และ 'Teaching Large Language Models to Reason with Reinforcement Learning' ซึ่งเปรียบเทียบแนวทาง MCTS กับกลยุทธ์ RL ร่วมสมัยอื่น ๆ

  • แค่ดูจาก URL บน HN ก็จำได้ทันทีว่าเป็นนักพัฒนาอัจฉริยะของ KataGo โพสต์ของเขาใน Reddit ภายใต้ cbaduk ยอดเยี่ยมอย่างสม่ำเสมอ

  • สำหรับชื่อ "Monte-Carlo Tree Search" ผู้อ่านควรสังเกตว่าอัลกอริทึมที่กล่าวถึงนั้นไม่มีส่วนที่เป็น "Monte-Carlo" เลย และเป็นแบบกำหนดแน่นอนทั้งหมด เป็นเรื่องแปลกที่โดยทั่วไป MCTS มักถูกนำไปใช้งานแบบกำหนดแน่นอน ผมเคยคิดว่าการสุ่มน่าจะอยู่ในขั้นตอนการ sampling

  • งานวิจัยที่กล่าวถึงนี้หลุดจากเรดาร์ของผมไปโดยสิ้นเชิงตอนที่ศึกษาด้าน MCTS ไว้ ถ้ามีโอกาสครั้งหน้า การลองปรับแก้แบบนี้น่าจะสนุกมาก

ความรู้พื้นฐาน:

  • LLMS: ในบริบทนี้ LLMS อาจไม่ได้หมายถึงเทคโนโลยีเฉพาะเจาะจง แต่ใช้สื่อถึงระบบแมชชีนเลิร์นนิงโดยทั่วไป
  • Zobrist hashing: เทคนิคสำหรับแฮชสถานะเกมอย่างมีประสิทธิภาพ โดยเฉพาะในเกมกระดาน
  • MCTS (Monte-Carlo Tree Search): อัลกอริทึมที่ใช้การสุ่มตัวอย่างเพื่อช่วยตัดสินใจอย่างเหมาะสม โดยมักใช้ในกระบวนการตัดสินใจอย่างเช่นเกม
  • Reinforcement Learning (RL): สาขาหนึ่งของแมชชีนเลิร์นนิงที่เรียนรู้ผ่านการลองผิดลองถูก และเรียนรู้กลยุทธ์การกระทำที่เหมาะสมผ่านระบบรางวัล