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

 (github.com/lightvector)
3 คะแนน โดย GN⁺ 2024-03-11 | 1 ความคิดเห็น | แชร์ทาง WhatsApp
  • Monte-Carlo Graph Search (MCGS) คือแนวทางที่นำ MCTS ไปใช้กับกราฟมีทิศทางแทนต้นไม้ เพื่อแชร์การค้นหาที่ซ้ำกันในเกมที่หลายลำดับการเดินสามารถเปลี่ยนผ่านไปสู่สถานะเดียวกันได้
  • หากย้าย จำนวนครั้งที่เยี่ยมชม N และ ค่าเฉลี่ยมูลค่า Q ของ MCTS เดิมไปยัง DAG ตรง ๆ จำนวนครั้งที่เยี่ยมชมของโหนดลูกที่ถูกแชร์อาจไม่สอดคล้องกับการประมาณค่านโยบายและมูลค่าของโหนดพ่อ ทำให้อัลกอริทึมไม่ sound ได้
  • หากมอง MCTS เป็น การปรับเหมาะนโยบายแบบมี regularization การกระจายจำนวนครั้งที่เยี่ยมชมของแต่ละแอ็กชันที่ PUCT สร้างขึ้นคือ posterior policy และ Q ถูกตีความเป็นอรรถประโยชน์คาดหวังของนโยบายนั้น
  • MCGS ที่ถูกต้องต้องติดตาม จำนวนครั้งที่เยี่ยมชมเอดจ์ N(n,a) แยกจากจำนวนครั้งที่เยี่ยมชมโหนดลูก และคำนวณ Q ใหม่เป็นผลรวมถ่วงน้ำหนักของ U(n) กับ Q ของโหนดลูก เพื่อรักษาความหมายของนโยบายและมูลค่าไว้แม้ในกราฟ
  • ในการใช้งานจริงยังมีตัวเลือกต่าง ๆ เช่น stale Q, การอัปเดตแบบเพิ่มทีละส่วน, จะทำ playout ต่อจากโหนดลูกที่ถูก transposition หรือไม่, การจัดการ hash collision และ cycle ในเกม โดยปัจจุบัน KataGo ใช้ การอัปเดตแบบ idempotent

สถานะ transposition ที่การค้นหาแบบต้นไม้พลาดไป

  • ในการค้นหา game tree อาจเกิดกรณีที่ลำดับการเดินต่างกัน เปลี่ยนผ่าน (transposition) ไปสู่สถานะเดียวกัน
    • ในหมากรุก 1. d4 d5 2. Nf3 และ 1. Nf3 d5 2. d4 ไปถึงตำแหน่งเดียวกัน
  • สำหรับเกมที่เกิด transposition ได้ เมื่อความลึกของการค้นหาเพิ่มขึ้น สถานะซ้ำอาจเพิ่มขึ้นแบบเอกซ์โพเนนเชียล ดังนั้นจึงควรแชร์การคำนวณของสถานะเดียวกัน
  • การใช้งาน MCTS ทั่วไปปฏิบัติต่อเกมเป็น branching tree จึงค้นหาหลายอินสแตนซ์ของตำแหน่งเดียวกันซ้ำอีก
    • การปรับแต่งระดับต่ำ เช่น การแคชผลประเมินจาก neural network สำหรับตำแหน่งที่ซ้ำกัน ช่วยลดต้นทุนได้
    • แต่ยังมีปัญหาว่า แม้จะค้นพบแท็กติกสำคัญในอินสแตนซ์หนึ่งจนทำให้การประเมินถูกแก้ไข การแก้ไขนั้นก็ไม่ถูกเผยแพร่ไปยังอินสแตนซ์อื่น
  • หากโมเดล state space เป็น กราฟมีทิศทางไม่มีวัฏจักร (DAG) เมื่อหลายเส้นทางไปถึงสถานะเดียวกัน ก็สามารถแทนสถานะนั้นเป็นโหนดเดียวได้
  • จะละเว้นการจัดการเกมที่มี cycle จริงเป็นส่วนใหญ่ และโฟกัสว่า MCTS ควรทำงานอย่างไรบน DAG

MCTS มาตรฐาน: ต้นไม้ที่สะสมสถิติการรัน

  • MCTS มาตรฐานเก็บส่วนหนึ่งของเกมที่ค้นหาแล้วไว้ในหน่วยความจำเป็น ต้นไม้ของโหนด
  • โดยปกติแต่ละโหนดติดตามค่าต่อไปนี้
    • N: จำนวน playout ที่ผ่านโหนดนี้หรือจบที่โหนดนี้จนถึงปัจจุบัน
    • Q: ค่าเฉลี่ยแบบรันนิ่งของค่าอรรถประโยชน์ที่ playout เหล่านั้นสุ่มตัวอย่างได้
  • playout หนึ่งครั้งดำเนินไปตามลำดับต่อไปนี้
    • เริ่มจากรูท แล้วเลือกแอ็กชันถัดไปตามสูตรสำรวจขณะไล่ลงไป
    • เมื่อไปถึงสถานะที่ยังไม่เคยค้นหา ให้เพิ่มโหนดใหม่
    • รับค่าอรรถประโยชน์ U ของสถานะใหม่ ตัวอย่างคือการ query value head ของ neural network
    • ย้อนกลับขึ้นไปตามต้นไม้ เพิ่ม N ของแต่ละโหนดและอัปเดตค่าเฉลี่ย Q
  • ใน MCTS สไตล์ AlphaZero ใช้สูตร PUCT ในการเลือกแอ็กชัน
    • N(a): จำนวนครั้งที่ลองแอ็กชัน a ซึ่งในต้นไม้เท่ากับ N ของโหนดลูกที่แอ็กชันนั้นชี้ไป
    • Q(a): อรรถประโยชน์เฉลี่ยของแอ็กชัน a ซึ่งเท่ากับ Q ของโหนดลูก
    • PlayerToMove: สะท้อนว่าผู้เล่นปัจจุบันเป็นฝ่าย maximize หรือ minimize
    • P(a): prior probability เช่น การทำนายนโยบายของ neural network
    • c_PUCT: ค่าคงที่ที่ปรับได้
  • “PUCT” มาจากตระกูล Predictor UCT/UCB ที่ใช้ prior distribution จากการทำนาย โดยเวอร์ชันดัดแปลงของ AlphaZero มีรูปแบบฟังก์ชันต่างจากรูปแบบดั้งเดิม
  • MCTS สมัยใหม่อาจเป็นแบบ deterministic เมื่อใช้การประเมินจาก neural network แต่คำว่า “Monte-Carlo” ในชื่อมาจากวิธีเดิมที่ทำ random rollout ไปจนจบเพื่อประมาณค่าอรรถประโยชน์
  • หลังทำ playout ซ้ำจนหมดงบคำนวณของตานั้นแล้ว จะเลือกแอ็กชันสุดท้ายที่รูทโดยดู โหนดลูกที่มีจำนวนครั้งที่เยี่ยมชม N มากที่สุด ไม่ใช่ Q
    • โหนดลูกที่มี Q สูงแต่ N ต่ำอาจเป็นความผิดพลาดที่ได้ค่าสูงเพราะ noise จากการค้นหาตื้น ๆ
  • การกระจายจำนวนครั้งที่เยี่ยมชมที่รูท N(a) / ΣN(b) สามารถใช้เป็นเป้าหมายการเรียนรู้นโยบายในลูปการเรียนรู้ของ AlphaZero ได้

ปัญหาที่เกิดเมื่อประยุกต์กับ DAG แบบตรงไปตรงมา

  • อาจแทบคงโค้ด tree MCTS ไว้เดิม แล้วถ้าสถานะเกมใหม่มีอยู่ใน nodes_by_hash แล้วก็ให้ชี้ไปยังโหนดเดิม
  • วิธีนี้ไม่สามารถรักษาสมมติฐานของต้นไม้ที่ว่า จำนวนครั้งที่เยี่ยมชมโหนดลูก เท่ากับจำนวนครั้งที่เยี่ยมชมแอ็กชันที่เลือกจากโหนดพ่อ
  • สถานการณ์ตัวอย่าง
    • โหนด A ชอบแอ็กชันที่ไปยังโหนด C และ Q ของ A ถูกกำหนดโดย playout ประมาณ 30 ครั้งที่ส่วนใหญ่ค้นหา C
    • C ถูกเยี่ยมชมประมาณ 40 ครั้งจากเส้นทาง transposition อื่นด้วย
    • ต่อมา C ถูกเยี่ยมชมจากเส้นทาง transposition อื่นมากขึ้น และพบแท็กติกในส่วนลึก ทำให้การประมาณค่าอรรถประโยชน์ของ C เพิ่มจาก 0.39 → 0.51
  • เนื่องจาก playout ที่อัปเดต C ไม่ได้ผ่าน A ทำให้ Q ของ A ไม่สะท้อนการประเมินใหม่ของ C
  • หลังจากนั้นแม้ A จะได้รับ playout อีกครั้ง PUCT ก็อาจสำรวจแอ็กชันอื่นที่มีจำนวนเยี่ยมชมน้อย แทน C ที่มีจำนวนเยี่ยมชมมาก
    • เพราะ C ดูเหมือนว่า “ถูกค้นหามากพอแล้ว”
    • ผลคือ Q ของ A อาจกลับลดลง
  • การขยายเป็นกราฟแบบตรงไปตรงมาสามารถสร้างอคติเทียมในค่าเฉลี่ยของ playout โดยทำให้ยิ่งเส้นทาง transposition เยี่ยมชมตัวเลือกที่โหนดพ่อชอบมากเท่าไร โหนดพ่อก็ยิ่งไปค้นหาตัวเลือกอื่นมากขึ้น
  • จึงกลายเป็น อัลกอริทึมที่ไม่ sound ถึงขั้นไม่ชัดเจนว่าแม้ค้นหาอนันต์แล้วจะลู่เข้าสู่การเดินที่ดีที่สุดหรือไม่

แม้อัปเดตพ่อทั้งหมดก็ยังไม่แก้ปัญหา

  • เมื่อโหนดหนึ่งถูกอัปเดตด้วย playout บางครั้ง อาจคิดถึงวิธีสะท้อนผลนั้นไม่เพียงต่อโหนดพ่อที่ playout ผ่านมาจริง แต่ต่อ พ่อและบรรพบุรุษทั้งหมด ด้วย
  • วิธีนี้ในกรณี A-C ข้างต้นสามารถอัปเดตอรรถประโยชน์ของ A ไปพร้อมกันได้
  • แต่ในตัวอย่างอื่น โหนดพ่อ D จะถูกปนเปื้อนด้วยจำนวนเยี่ยมชมจำนวนมากของโหนดลูก transposition F ที่ตนเองไม่ได้ชอบ
    • โหนดลูกที่ดีที่สุดของ D คือ E มี Q = 0.56 และ Q = 0.55 ของ D ก็สอดคล้องกับสิ่งนี้
    • D ค้นหา F แค่ครั้งเดียว แต่ F ถูกเยี่ยมชมจากเส้นทางอื่นแล้ว 9 ครั้ง รวมเป็นสถานะที่ถูกเยี่ยมชม 10 ครั้ง
    • ต่อมาถ้า F ถูกเยี่ยมชมจากเส้นทางอื่นเพิ่มอีก 100 ครั้งและยังคงมีอรรถประโยชน์ต่ำ วิธีอัปเดตพ่อทั้งหมดอาจดึง Q ของ D ลงไปถึง 0.35
  • จากมุมมองของ D ไม่ได้ต้องการจัดสรร playout ให้ F มากขนาดนั้น ดังนั้นการอัปเดตพ่อทั้งหมดก็เป็น วิธีที่ทำลายความหมายของนโยบาย เช่นกัน

มอง MCTS เป็นการปรับเหมาะนโยบาย

  • Monte-Carlo Tree Search as Regularized Policy Optimization ตีความ MCTS จากมุมมอง machine learning
  • ในแต่ละโหนด การกระจายจำนวนครั้งที่เยี่ยมชมสะสมที่ PUCT เลือกซ้ำ ๆ จะประมาณและลู่เข้าไปยังคำตอบของปัญหา optimization ต่อไปนี้
ค่าที่ π maximize:
Σ π(a) Q(a) - λ_N D_KL(P || π)
  • ความหมายขององค์ประกอบ
    • Σ π(a) Q(a): อรรถประโยชน์คาดหวังที่ประมาณได้เมื่อทำตามนโยบาย π
    • D_KL(P || π): reverse KL divergence ที่วัดความแตกต่างระหว่าง prior policy P กับ posterior policy π
    • λ_N: สัมประสิทธิ์ที่กำหนดความแรงของพจน์ KL และจะลดลงเมื่อจำนวนการเยี่ยมชมเพิ่มขึ้น
  • การกระจายจำนวนครั้งที่เยี่ยมชมสามารถมองเป็น posterior policy ที่เริ่มจาก prior policy P ของ neural network แล้วดีขึ้นเมื่อมีหลักฐานอรรถประโยชน์ของแอ็กชันสะสมจากการเยี่ยมชมมากขึ้น
  • ดังนั้น MCTS จึงตีความได้ว่าเป็นอัลกอริทึมที่ทำ online policy learning ขนาดเล็กพร้อมกันในแต่ละโหนดของต้นไม้
  • มุมมองนี้อธิบายได้ว่าทำไมการกระจายจำนวนครั้งที่เยี่ยมชมจึงดูเหมือนนโยบายของเอเจนต์ที่แข็งแกร่ง และทำไมจึงถูกใช้เป็นเป้าหมายการเรียนรู้นโยบายใน AlphaZero
  • แม้จะสามารถคำนวณคำตอบที่ถูกต้องของปัญหา optimization แล้วใช้เป็นนโยบายได้ แต่ในทางปฏิบัติอาจให้น้ำหนักมากกับการเดินที่ถูกเยี่ยมชมน้อยแต่บังเอิญดูเหมือนมี Q สูง
    • หากใช้การกระจายจำนวนครั้งที่เยี่ยมชมเป็น posterior policy การเดินใดจะได้น้ำหนักสูงได้ต้องถูกค้นหามากจริง ๆ จึงมีความทนทานกว่า

การตีความ Q ใหม่: จากค่าเฉลี่ย playout เป็นค่าคาดหวังของนโยบาย

  • ในคำนิยามมาตรฐาน Q(n) ของโหนด n คือค่าเฉลี่ยอรรถประโยชน์ของ playout ที่เยี่ยมชม n
Q(n) = (1 / N(n)) Σ U(p)
  • เมื่อเขียนใหม่ตามโหนดลูก จะได้ดังนี้
Q(n) = (1 / N(n)) ( U(n) + Σ N(c) Q(c) )
  • โดย U(n) คือการประมาณอรรถประโยชน์ดิบจาก neural network ของโหนด n เอง และ N(c) Q(c) คือค่าของโหนดลูกที่ถ่วงน้ำหนักด้วยจำนวนครั้งที่เยี่ยมชมของแต่ละโหนดลูก
  • ดังนั้น Q จึงตีความได้ว่าเป็น ค่าเฉลี่ยถ่วงน้ำหนักตามการกระจายจำนวนครั้งที่เยี่ยมชม ของ Q ของโหนดลูก
  • หากการกระจายจำนวนครั้งที่เยี่ยมชมคือ posterior policy ที่ MCTS ปรับเหมาะอยู่ Q(n) ก็คืออรรถประโยชน์คาดหวังแบบ regularized เมื่อทำตาม posterior policy นั้น
  • ในการตีความนี้ แต่ละโหนดจะปรับเหมาะนโยบายต่อไปเพื่อ maximize Q ที่โหนดลูกส่งรายงานมา และอัปเดต Q ของตนเป็นค่าประมาณล่าสุดของอรรถประโยชน์คาดหวังที่ทำได้ด้วยนโยบายนั้น
  • หาก Q ของโหนดลูกลู่เข้าสู่ค่าที่เหมาะที่สุดตามทฤษฎีเกม นโยบายและ Q ของโหนดพ่อก็จะลู่เข้าแบบ recursive ไปยังค่าที่เหมาะที่สุดเช่นกัน

MCGS ที่ถูกต้อง: แยกการเยี่ยมชมเอดจ์ออกจากการเยี่ยมชมโหนดลูก

  • ปัญหาที่เกิดในกราฟมาจากการสมมติว่าการเยี่ยมชมโหนดลูกของโหนดพ่อเกิดผ่านโหนดพ่อนั้นเท่านั้น
  • เมื่อมีเส้นทาง transposition จำนวนครั้งที่เยี่ยมชมโหนดลูกอาจต่างจากจำนวนครั้งที่ PUCT ตั้งใจจัดสรรจากโหนดพ่อนั้นได้อย่างไม่แน่นอน
  • ทางแก้คือการติดตาม จำนวนครั้งสะสมที่ PUCT เลือกแอ็กชันจากโหนดหนึ่ง ๆ แยกต่างหาก
  • แต่ละโหนด n ติดตามค่าต่อไปนี้
    • N(n): จำนวนครั้งทั้งหมดที่โหนดนี้ถูกเยี่ยมชม
    • N(n,a): จำนวนครั้งที่ PUCT เลือกแอ็กชัน a ที่โหนด n หรือก็คือจำนวนครั้งที่เยี่ยมชมเอดจ์
    • Q(n) = (1 / N(n)) ( U(n) + Σ N(n,a) Q(n,a) )
  • โดย Q(n,a) เท่ากับ Q(c) ของโหนดลูก c ที่ไปถึงเมื่อเล่นแอ็กชัน a
  • ในการคำนวณ PUCT ก็ใช้ จำนวนครั้งที่เยี่ยมชมเอดจ์ ไม่ใช่จำนวนครั้งที่เยี่ยมชมโหนดลูก
argmax_a PlayerToMove(n) * Q(n,a)
       + c_PUCT P(n,a) sqrt(Σ N(n,b)) / (1 + N(n,a))
  • อัลกอริทึมพื้นฐานเลือกแอ็กชันบนเส้นทาง playout หากสถานะที่ transposition ไปถึงมีอยู่แล้วก็เชื่อมไปยังโหนดเดิม แล้วตอนย้อนกลับจึงเพิ่มจำนวนครั้งที่เยี่ยมชมเอดจ์ จากนั้นคำนวณ N และ Q ใหม่เป็นฟังก์ชันของค่าของโหนดลูก
  • วิธีนี้คล้ายกับ Monte-Carlo Graph Search for AlphaZero ของ Czech, Korus, Kersting ในระดับสูง แต่ได้มาจากมุมมองการปรับเหมาะนโยบาย ไม่ใช่สถิติการรัน

ตัวเลือกการ implement: stale Q และวิธีอัปเดต

  • pseudocode ที่นำเสนออัปเดตเฉพาะโหนดบนเส้นทางที่ playout ผ่านจริง
  • ด้วยเหตุนี้ Q ของโหนดบนเส้นทางที่ไม่ได้ผ่านจึงอาจกลายเป็น stale Q
  • ถึงอย่างนั้นในทางทฤษฎีก็ยัง sound
    • สูตรสำรวจมาตรฐานอย่าง PUCT จะลองทุกแอ็กชันอย่างไม่สิ้นสุดในลิมิต
    • เมื่อโหนดถูกเยี่ยมชมอีกครั้ง จะใช้ Q ของโหนดลูกและจำนวนครั้งที่เยี่ยมชมเอดจ์ ณ ตอนนั้นมาคำนวณ Q ที่ถูกต้องโดยตรง
    • บน DAG จึงสามารถลู่เข้าไปสู่ค่าที่เหมาะที่สุดตามทฤษฎีเกมได้ในลิมิต
  • stale Q อาจลดประสิทธิภาพการค้นหา
    • สามารถเก็บ parent pointer แบบทันทีเพื่ออัปเดต Q ของโหนดพ่อด้วย
    • สามารถอัปเดตบรรพบุรุษทั้งหมดตามลำดับ topological sort เพื่อกำจัดสถานะ stale
    • สามารถอัปเดตเฉพาะเส้นทาง playout แล้วให้เธรดขนานอีกตัวค้นหาและอัปเดตโหนด stale
  • pseudocode ใช้ การอัปเดตแบบ idempotent
    • ไม่ว่าก่อนหน้านี้จะมีการอัปเดตขั้นกลางใด ๆ เมื่อเยี่ยมชมโหนดหนึ่งครั้ง N และ Q จะถูกต้องตามค่าปัจจุบันของโหนดลูก
  • การอัปเดตแบบเพิ่มทีละส่วนก็เป็นไปได้ แต่ในกราฟการทำให้เทียบเท่าหรือเทียบเท่าในลิมิตทำได้ยากกว่า
  • Czech และคณะเข้าหาจากมุมมองสถิติการรัน จึงใช้สูตรที่ incremental มากกว่า
    • เก็บ Q ของเอดจ์ด้วย นอกเหนือจากจำนวนครั้งที่เยี่ยมชมเอดจ์
    • มีกลไกให้ stale Q ค่อย ๆ ไล่ทันค่าล่าสุดและมีไฮเปอร์พารามิเตอร์สำหรับ tolerance ของ error
  • pseudocode ที่นำเสนอแสดงให้เห็นว่า MCGS ทำงานได้โดยไม่ต้องมีพารามิเตอร์ tolerance ของ error ใหม่หรือเก็บ Q ของเอดจ์
  • ปัจจุบัน KataGo ใช้ สูตรแบบ idempotent

จะทำ playout ต่อจากโหนดลูกที่ถูก transposition หรือไม่

  • ใน tree MCTS การเพิ่มจำนวนเยี่ยมชมเอดจ์และการเพิ่มจำนวนเยี่ยมชมโหนดลูกเป็นเหตุการณ์เดียวกัน
  • ในกราฟ เนื่องจาก transposition โหนดลูกอาจถูกเยี่ยมชมมามากกว่าเอดจ์นั้นแล้ว
  • ในกรณีนี้สามารถมองว่าโหนดลูกถูกเยี่ยมชมมากพอแล้ว จึงหยุด playout เพิ่มเฉพาะจำนวนครั้งที่เยี่ยมชมเอดจ์ แล้วอัปเดตโหนดพ่อและบรรพบุรุษ
  • เหตุผลที่ชอบการหยุด
    • หากจำนวนเยี่ยมชมเอดจ์ต่ำและจำนวนเยี่ยมชมโหนดลูกสูง ปริมาณข้อมูลส่วนเพิ่มจากการเพิ่มการเยี่ยมชมให้โหนดลูกนั้นอาจน้อย
  • เหตุผลที่ชอบการทำต่อ
    • โหนดที่จำนวนเยี่ยมชมโหนดลูกมากกว่าจำนวนเยี่ยมชมเอดจ์มีแนวโน้มเป็นโหนดที่มีหลายโหนดพ่อ transposition เข้ามา จึงมีผลต่อโหนดพ่อจำนวนมาก และการประเมินที่แม่นยำยิ่งสำคัญ
  • ตัวเลือกนี้ยังเป็นพื้นที่สำหรับการทดลอง
    • อาจใช้วิธีตั้ง threshold ให้หยุดก็ต่อเมื่อจำนวนเยี่ยมชมโหนดลูกมากกว่าจำนวนเยี่ยมชมเอดจ์มากพอ
  • โดยพื้นฐาน KataGo จะหยุด playout แต่มีตัวเลือกการตั้งค่าให้ทำต่อหรือหยุดบางส่วนแบบสุ่มได้
  • pseudocode ไม่หยุด playout และหากต้องการสามารถเพิ่มการเช็กหนึ่งบรรทัดด้วยเงื่อนไข child.N <= edge_visits

แฮช โหนดสิ้นสุด และ cycle จริงในเกม

  • ใน pseudocode โหนดจบเกมจะถูกคำนวณใหม่เป็น N = 1, U = Q = อรรถประโยชน์ของผลลัพธ์เกม โดยไม่ขึ้นกับจำนวนครั้งที่เยี่ยมชม
    • จำนวนครั้งที่เยี่ยมชมเอดจ์ของโหนดพ่อยังเพิ่มตามปกติ ดังนั้นวิธีนี้ก็ใช้ได้
    • หากผลลัพธ์เกมเป็นแบบสุ่มและไม่สามารถคำนวณอรรถประโยชน์คาดหวังได้โดยตรง การเพิ่ม N ทุกครั้งที่เยี่ยมชมโหนดสิ้นสุดและเฉลี่ยผลลัพธ์ที่สุ่มได้อาจสำคัญ
  • อาจจัดการอรรถประโยชน์ของจุดจบเกมให้กว้างขึ้น เพื่อเผยแพร่ค่าที่พิสูจน์ได้ขึ้นไปบนกราฟได้เร็วขึ้น
    • MCTS/MCGS ทั่วไปไม่มีอุปกรณ์รับรู้ค่าอรรถประโยชน์ที่แน่นอน ดังนั้นเมื่อสถานะสิ้นสุดมีความสำคัญ จึงไม่ลู่เข้าสู่ค่าที่เหมาะที่สุดได้ถูกเท่าการค้นหาแบบคลาสสิกอย่าง alpha-beta
  • สมมติว่ามี hash ที่เป็นเอกลักษณ์ ของสถานะเกมเพื่อหา transposition
    • การสร้าง hash ที่ไม่มี collision จริง ๆ สำหรับสถานะเกมที่ซับซ้อนนั้นยุ่งยากและอาจมีต้นทุนสูง
    • Zobrist hash ขนาดใหญ่พอ เช่น 128 บิตหรือ 192 บิต โดยทั่วไปเพียงพอในทางปฏิบัติที่จะทำให้ collision แทบไม่เกิดขึ้น หากไม่ใช่สถานะที่ถูกสร้างขึ้นมาแบบ adversarial
    • เพื่อหลีกเลี่ยง infinite recursion เมื่อ hash collision ทำให้เกิด cycle สามารถเพิ่ม cycle detection ได้
  • ไม่ลงรายละเอียดการจัดการ cycle ที่เกิดจากกฎเกมจริง เช่น superko ในโกะ หรือ threefold repetition ในหมากรุก
  • ภาคผนวกวันที่ 2024-03-10 ให้ลิงก์ Google Docs ที่รวบรวมแนวคิดคร่าว ๆ เพิ่มเติมเกี่ยวกับการจัดการ repetition และ cycle และอาจต้องทดลอง heuristic ตามแต่ละเกม
  • ในการจัดการโกะของ KataGo ใช้ทฤษฎีบทเฉพาะของโกะที่ว่า หากจะกลับไปยังตำแหน่งเดิมหลังจากการเดินบางตา ต้องใช้เวลาอย่างน้อย S + E - 1 ตา เพื่อจำกัดการแชร์โหนดในสถานการณ์ที่เกี่ยวข้องกับ cycle ให้เสถียร

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

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

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

  • ผมคิดว่า การค้นหากราฟ แบบนี้จำเป็นต่อการพัฒนาการให้เหตุผลของ AI แค่ LLM เพียงอย่างเดียวมีโอกาสล้มเหลวสูง
    ในลิงก์มีแหล่งอ้างอิงดี ๆ มากมาย รวมถึง Zobrist hashing สำหรับตารางเกม https://en.wikipedia.org/wiki/Zobrist_hashing
    เพื่อไม่ให้ปริมาณการคำนวณของการค้นหากราฟระเบิด ต้องหา hashing ที่ดีซึ่งเหมาะกับคำอธิบายสถานะในรูปแบบภาษา
    เรื่องการค้นหาต้นไม้ ก็มี Thinking Fast and Slow: https://arxiv.org/abs/1705.08439 และ Teaching Large Language Models to Reason with Reinforcement Learning: https://arxiv.org/abs/2403.04642 ซึ่งเปรียบเทียบแนวทาง MCTS กับกลยุทธ์ reinforcement learning อื่น ๆ ในปัจจุบัน น่าอ่านเช่นกัน

    • อันนี้ดูระดับต่ำเกินไป
      ถ้าจะก้าวไปอีกขั้น อาจเป็นวิธีที่เรียนรู้ การแทนสถานะ ไปพร้อมกับอัลกอริทึมค้นหา ให้เป็นการค้นหาบนการแทนสถานะของโครงข่ายประสาทที่อัลกอริทึมค้นหาสามารถดึงต้นทุนออกมาได้
      https://sites.google.com/view/genie-2024/
      Genie ของ DeepMind เป็นตัวอย่างที่ดีของการโมเดลสถานะแบบไม่ต่อเนื่อง โครงข่ายประสาทเรียนรู้การแทนที่ซับซ้อนมาก ซึ่งรวมถึงการตรวจจับการชนและการกระทำ แทนที่จะถอดรหัสสถานะนั้นกลับเป็นพิกเซล บางทีอาจค้นหาบนสถานะนั้นโดยตรงได้
      แน่นอนว่าโครงสร้างนี้ในทางปฏิบัติอาจแตกต่างไปมาก
    • แม้จะทำให้ง่ายเกินไปมาก แต่ผมคิดว่าแนวทางที่น่าลองสำรวจคือแบบนี้
      วางชุดของข้อโต้แย้งเชิงตรรกะไว้ แล้วหาวิธีให้แฮชกับแต่ละข้อโต้แย้ง จากนั้นแทนแฮชของข้อโต้แย้งเหล่านั้นเป็น Merkle tree ที่ซ้อนทับกันตาม หลักการพื้นฐาน
      เมื่อข้อโต้แย้งหนึ่งถูกหักล้างได้สำเร็จ แฮชของข้อโต้แย้งนั้นก็เปลี่ยน และแฮชของข้อโต้แย้งย่อยก็จะไม่ถูกต้องไปด้วย
    • ผมสงสัยว่าเป็นไปไม่ได้หรือที่จะผสานทั้งสองอย่างเข้าด้วยกัน สมองคงไม่น่าจะใช้เทคนิคเดียวกับทุกเรื่อง และดูมีแนวโน้มสูงว่าจะมีเครื่องมือหลายอย่าง พร้อม ตัวเลือก ที่คอยเลือกว่าจะใช้เครื่องมือไหนเมื่อไรอยู่ด้านบน

  • เห็นผู้เขียนใน URL ของ HN แล้วก็รู้ทันทีว่าเป็นอัจฉริยะที่สร้าง KataGo: https://github.com/lightvector/KataGo
    โพสต์ต่าง ๆ ที่เขาลงใน https://www.reddit.com/r/cbaduk/ ก็ยอดเยี่ยมอย่างสม่ำเสมอ

    • URL ก็อยู่ใน repository ของ KataGo ตรง ๆ เลย

  • ผมไม่ได้มีประสบการณ์หมากรุกมากนัก แต่ค่อนข้างสงสัยกับข้ออ้างที่ว่า position เดียวกันจะซ้ำกันใน search tree บ่อยพอที่จะสำคัญ อยากเห็นค่าที่วัดจริงจาก Leela Zero
    ถ้ารวมการซ้ำสามครั้งและกฎ 50 ตาเข้าไปในสถานะด้วย โอกาสซ้ำก็น่าจะยิ่งต่ำลงมาก และแม้ยังไม่ได้พิจารณาส่วนนั้น ผมก็ยังคิดแบบนั้น

    • ในโกะ โคะ พบได้บ่อยมาก แม้จะไม่สามารถเล่นให้ตำแหน่งบนกระดานซ้ำเดิมได้ แต่ถ้า tree search ประเมินตำแหน่งโคะได้ไม่ดี ก็สร้างสถานการณ์ให้ AI เดินหมากแย่ ๆ ได้ง่าย

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

    • เดิมที MCTS มีความสุ่มอยู่จริง ๆ เหมือนบทความก็พูดถึงอยู่ คือเป็นรูปแบบที่ทำ playout เพื่อประเมินตำแหน่งในตอนท้าย
      ในโปรเจกต์คล้าย ๆ กันปัจจุบัน สิ่งนี้ถูกแทนที่ด้วยการประเมินจากโครงข่ายประสาทที่คุณภาพดีกว่า การสุ่มเดินหมากเพื่อดูว่าใครชนะไม่ใช่วิธีที่ดีนัก แต่เป็นกลยุทธ์ที่ดีที่สุดเท่าที่รู้ในเวลานั้น
      สุดท้ายแล้ว ส่วนมอนติคาร์โลจึงไม่ใช่องค์ประกอบสาระสำคัญของสิ่งที่ปัจจุบันยังเรียกว่า MCTS และค่อนข้างเป็นตัวเลือกที่ด้อยกว่าด้วยซ้ำ ชื่อนี้เลยออกจะโชคร้ายนิดหน่อย
    • พูดให้เคร่งครัด มันเป็นอัลกอริทึมอีกแบบหนึ่งที่อยู่ใต้ชื่อ “monte carlo” เดียวกัน
      จุดที่น่าสนใจคือ วิธีมอนติคาร์โลส่วนใหญ่พึ่งพา ตัวสร้างเลขสุ่มเทียม ไม่ใช่ตัวสร้างเลขสุ่มจริง ดังนั้นถ้าให้ seed และอินพุตเดียวกัน ก็จะเป็นวิธี deterministic ที่ให้ผลลัพธ์เดิมเสมอ
      อัลกอริทึมนี้แทนที่จะใช้ตัวสร้างเลขสุ่มเทียมทั่วไปกับ heuristic แยกต่างหาก ก็ไป query โครงข่ายประสาทแทน โครงข่ายประสาทเป็น heuristic บนพื้นที่ค้นหาขนาดมหึมา จึงทำงานเหมือนตัวสร้างเลขสุ่มเทียมที่แย่มากซึ่งถูก training จนเอนเอียงอย่างแรงไปยังผลลัพธ์บางอย่าง และสุดท้ายจึงดูเหมือนตัวสร้างเลขสุ่มเทียมที่มี heuristic ครอบอยู่
      ประเด็นสำคัญคือ นี่เป็นการทำให้ MCTS เฉพาะทาง ดังนั้นในเชิงเทคนิคจึงไม่ได้เหมาะกับทุกกรณีใช้งาน
    • ถ้ามีความสุ่มอยู่ ผมสงสัยว่าจะลู่เข้าหรือไม่ และต้องใช้ ทรัพยากร-เวลา แค่ไหน ซึ่งอาจต่างกันไปตาม CPU, RAM, GPU, TPU, QPU ด้วย

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

  • ถ้ามีบทนำสั้น ๆ ก็คงดี

    • เวลาสร้าง AI เล่นเกม ถ้าเปรียบกว้าง ๆ แล้ว AI ทั้งหมดก็เป็นแบบนั้น หนึ่งในเทคนิคที่มีแนวโน้มดีที่สุดคือ การค้นหาต้นไม้ เป็นวิธีจัดอันดับตาเดินปัจจุบันจากตาเดินถัด ๆ ไป
      ในเกมที่สามารถไปถึงสถานะเดียวกันได้หลายเส้นทาง อาจสิ้นเปลืองหน่วยความจำมากเพราะต้องบันทึกโหนดสถานะเดียวกันซ้ำในกิ่งต่าง ๆ
      บทความนี้พิจารณาแนวทางที่เรียกว่า การค้นหากราฟ อย่างดี โดยแก่นแล้วคือเพิ่มการคำนวณเพื่อ hashing สถานะเกม เพื่อตรวจสอบว่าเป็นโหนดที่เคยเยี่ยมชมแล้วหรือไม่ แลกกับการประหยัดหน่วยความจำ
      เพราะไม่ต้องบันทึกโหนดที่เคยเห็นแล้วซ้ำ ต้นไม้ที่ไม่มีวงจรจึงกลายเป็นกราฟมีทิศทางแบบไม่มีวัฏจักร
      ด้วยเหตุนี้ หากต้องการผลลัพธ์ที่ถูกต้อง ก็ต้องปรับ tree search เล็กน้อย โดยเฉพาะต้องจัดหน่วยของการปรับให้เหมาะสมไปที่ edge หรือก็คือ action/ตาเดิน มากกว่าที่ vertex หรือสถานะ
      เป็น technical essay ที่เขียนดีในสไตล์ literate programming โดยคนที่เข้าใจหัวข้อนี้เป็นอย่างดี