ช่วงนี้หลายๆคนคงได้ยินข่าว AlphaGo เอาชนะแชมป์โลกอย่างLee Sedol หลายๆคนคงสงสัยเหมือนผม ว่าเจ้า AlphaGo ที่ว่านี่ทำงานยังไง
ทีมงานของ Deep Mind ได้มีการเผยแพร่ไว้อย่างละเอียด[1] หลายคนอาจจะเคยเห็นบทความนี้แล้ว แต่ติดปัญหาที่ไม่ได้มีพื้นฐานทางด้าน AI ทำให้ทำความเข้าใจได้ยาก เพราะศัพท์ต่างๆที่ใช้นั้นเป็นศัพท์เฉพาะเยอะมาก (Monte Carlo Search Tree, Supervised Learning, Reinforced Learning, etc.)
บทความนี้จะทำการอธิบายเทคนิคการอ่านตาเดินล่วงหน้าที่ AlphaGo ใช้ (Monte Carlo Search Tree – MCST) โดยจะไม่ลงไปในระดับคณิตศาสตร์หรือตัวทฤษฏีมาก แค่อธิบายให้เห็นถึงหลักการคร่าวๆ เพื่อให้คนทั่วไปที่ไม่ได้มีพื้นฐานทางด้าน AI พอเข้าใจเทคนิคเหล่านี้ได้ในระดับหนึ่ง
MCST เป็นแค่เทคนิคนึงที่ AlphaGo ใช้เท่านั้น สำหรับใครที่ต้องการทำความเข้าใจให้ลึกลงกว่านี้ ลองเช็คลิ้งก์บทความจริง[1] ด้านล่างสุดดูครับ
การอ่านตาถัดๆไปด้วยการจำลองรูปแบบการเล่น
จะตอบคำถามนี้ได้ เราต้องเข้าใจกันก่อนว่าคอมพิวเตอร์เล่นบอร์ดเกมต่างๆยังไง
เราจะเริ่มจากเกมง่ายๆอย่าง “โอเอ็กซ์” (Tic-Tac-Toe) กันก่อนครับ (ใครไม่รู้จักลองไปเล่นดูที่นี่ครับ http://playtictactoe.org/ )
กระดานโอเอ็กซ์ มีทั้งหมดเก้าช่อง ผู้เล่นผลัดกันเล่นและลงซ้ำในช่องเดียวกันไม่ได้
ดังนั้น ผู้เล่นคนแรกจะมีโอกาสเลือกจาก 9 ช่องในตาแรก ตาถัดไปก็จะเหลือให้เลือกเล่นแค่ 8 ช่อง, 7 ช่อง … ไปจนกระทั่ง 1 ช่อง
ไล่ไปเรื่อยๆ เราจะพบว่า หากเล่นจนครบทุกช่อง จะมีรูปแบบที่เป็นไปได้ทั้งหมด 9 x 8 x 7 x 6 x …. x 1 = 9!
ซึ่งก็คือ 362,880 แบบ !!
เยอะกว่าที่คิดใช่ไหมครับ?
ถ้านำมาเขียนเป็นแผนผังในการเลือก เราจะได้รูปประมาณนี้
ในวิทยาศาสตร์คอมพิวเตอร์ เราเรียกแผนผังแบบนี้ว่าต้นไม้ (Tree) โดยแต่ละโนด (Node) ในต้นไม้ จะแสดงสถานะของตารางในปัจจุบัน ไล่ลงไปเรื่อยๆ จนถึงโนดล่างสุดของต้นไม้ (ที่เล่นกันเต็มครบ 9 ช่องแล้ว) จะถูกเรียกว่าใบ (Leave – ใบ) ซึ่งเป็นจุดที่เราได้ผลลัพธ์ในการเล่น เจ้าใบที่ว่านี่แหละ คือหนึ่งใน 352,880 แบบที่เราคำนวนกันเมื่อครู่
(ถึงจุดนี้ ผู้อ่านอาจจะบอกว่าไม่ต้องเล่นจนครบเก้าช่องก็รู้ผลแล้ว ตอนนี้เราจะถือว่าต้องเล่นให้ครบเก้าช่องก่อน เดี๋ยวเราจะมาคุยเรื่องนี้กันในหัวข้อถัดไปครับ)
สมมติว่าเราต้องการสร้างคอมพิวเตอร์เพื่อเล่นเกมโอเอ็กซ์ วิธีการแบบกำปั้นทุบดินคือ คำนวนทุกความเป็นไปได้ทั้งหมด แล้วให้คอมพิวเตอร์ทำการอ่านเกมล่วงหน้า (Reading) เพื่อเลือกตาที่ดีที่สุด
คราวนี้ เราจะรู้ได้ยังไงล่ะว่าตาไหนดี เพราะเราไม่รู้ว่าตาถัดไปจะเดินยังไง และการแพ้ชนะยังไม่รู้จนกระทั่งจบเกม ตัวอย่างเช่น ตาแรก จะเดินช่องไหนดีระหว่าง 1-9 เพราะทุกช่องยังไม่จบเกม
ดังนั้น เราต้องมีวิธีการคำนวนว่าโนดลูก (โนดที่อยู่ถัดลงไปหนึ่งชั้น) อันไหนที่ควรเลือก วิธีง่ายๆก็คือคำนวนว่า ถ้าคำนวนลงไปทั้งหมด
อย่างขั้นตอนแรก ถ้าเราเลือกเดินช่อง 1 ก็จะมีลีฟ 8! (40,320) แบบ ที่เป็นไปได้
เราก็มานั่งนับดูได้ สมมติว่า ใน 40,320 แบบนี้ ชนะ 9,250 แบบ แพ้ 10,750 แบบ เสมออีก 20,320 แบบ
ทำแบบนี้ไปกับช่อง 2 ไปจนถึง ช่อง 9 เราก็จะสามารถเลือกได้ว่าช่องไหนจะดีสุด
ลดขนาดของต้นไม้ลง
ในความเป็นจริง เราไม่มีความจำเป็นที่จะต้องไล่ดูไปจนเดินครบทุกช่อง เพราะเรารู้ผลแล้ว เช่น
- เกมอาจจะจบได้เร็วกว่า เพราะเราได้วาง O สามช่องติดกันแล้ว
- ไม่มีทางเป็นไปได้ที่จะทำ O X ติดกันสามช่องได้แล้ว
- เกมถึงจุดที่มีผู้ชนะแน่นอนแล้ว
ดังนั้น พอถึงจุดนี้ เราสามารถคำนวนผล ได้เลย โดยไม่ต้องสร้างต้นไม้ต่อ ทำให้ลดปริมาณการสร้างโนดได้เยอะมาก
ในเกมที่ซับซ้อนมากขึ้นอย่างโกะ ที่มีช่องทั้งหมด 361 ช่อง ความเป็นไปได้นั้นเยอะมาก (361! นี่เยอะขนาดไหน ลองไป Google ดูครับ) เราจะสามารถใช้วิธีนี้ในการตัดเล็มต้นไม้ให้เล็กลงได้ เช่น
- ตอนเริ่มเกมไม่มีใครลงที่เส้น 2 กับ เส้น 1
- หากเรามีลมหายใจพอแล้ว เราไม่ลงเหมากเพื่อถมพื้นที่ตัวเอง
- เราไม่ลงหมากในพื้นที่ของศัตรู เพราะถูกจับกินแน่นอน (แต่จะรู้ได้ยังไงว่าโดนจับกินแน่นอนถ้าไม่ค้นหาดู?
เราสามารถสร้างกฏพวกนี้ขึ้นมาได้ เพราะเรารู้จักเกมโกะดี ซึ่งทำให้คอมพิวเตอร์สามารถตัดสินใจได้ง่ายขึ้นเพราะไม่ต้องค้นหาทุกแบบ อย่างไรก็ตามกฏเหล่านี้ก็ไม่พอที่จะทำให้วิธีการอ่านเกมแบบกำปั้นทุบดินของเราเก่งในระดับโปรได้
เช่น ทำให้แต่ละตามีช่องที่เลือกลงเหลือเฉลี่ย 200 แบบ และเกมส่วนใหญ่รู้ผลใน 200 ตา ต้นไม้ก็ยังใหญ่เกินไปอยู่ดี
เดาตาล่วงหน้าด้วย Monte Carlo Search Tree (MCST)
เนื่องจากเราไม่มีทรัพยากรคอมพิวเตอร์ที่จะคำนวนรูปแบบทั้งหมด เราจึงต้องใช้เทคนิคทาง AI เข้ามาเพื่อใช้ในการอ่านเกมล่วงหน้า (Reading)
Monte Carlo Search Tree (หรือต่อไปนี้จะเรียกย่อๆว่า MCST) เป็นเทคนิคที่ถูกใช้กันมากในการสร้าง AI เพื่อเล่นเกม โปรแกรมเล่นโกะต่างๆในปัจจุบันก็ใช้วิธีนี้ ตัว AlphaGo เองก็ใช้วิธีนี้เช่นกัน
แนวคิดของเทคนิคนี้คือการค่อยๆสร้างต้นไม้ให้ใหญ่ขึ้นเรื่อยๆ โดยเลือกใบที่ดูมีโอกาสเป็นไปได้มากที่สุด (Selection) แล้วทำการจำลองตาถัดไปโดยการเพิ่มโนด (Expansion) หลังเพิ่มโนดเสร็จแล้ว ก็จะทำการทดสอบดูว่าการขยายแบบนี้ได้ผลแพ้หรือชนะ (Simulation) แล้วผลลัพธ์นำมาปรับค่าที่เก็บไว้ในแต่ละโนดของต้นไม้ ไล่ไปจนถึงตาแรก (Back propagation) ตามรูปด้านล่าง
โดยโปรแกรมจะทำซ้ำสี่ขั้นตอนนี้เพื่อขยายต้นไม้ไปเรื่อยๆ เมื่อทดสอบมากพอ ต้นไม้จะสามารถคาดเดาได้ว่าเส้นทางไหนดีที่สุด
ถ้านำมาใช้ในกรณีของโกะ จะเป็นดังนี้
- Selection – เลือกหมากที่เดินต่อแล้วน่าจะดีที่สุด
- Expansion – ขยายต้นไม้ต่อในตำแหน่งนั้น
- Simulation – ทดลองเดินหมากต่อไปจนจบเกม ว่าได้ผลแพ้หรือชนะ
- Back propagation – นำผลลัพธ์แพ้ชนะ มาปรับค่าที่เก็บไว้ในแต่ละโนด
วิธีนี้จะคล้ายกับการคิดของมนุษย์ที่ใช้ในการเลือกเดินหมาก และลดปริมาณรูปแบบที่ต้องใช้ในการคำนวนไปได้อย่างมหาศาล
แต่ MCST ยังไม่พอที่จะชนะนักเล่นโกะอาชีพได้
เทคนิค MCST นั้นถูกใช้มานานแล้วในโปรแกรมโกะอื่นๆ แต่เทคนิคนี้มีข้อจำกัดอยู่
ตัวอย่างเช่น ในขั้นตอนที่ 3 เราจะทดลองเดินต่อไปจนจบได้อย่างไร
เราอาจจะใช้วิธีการเลือกเดินสุ่มๆเอา แต่ด้วยความที่เกมโกะมีตาเดินให้เลือกเยอะมากกว่าจะจบเกม การเดินสุ่มๆแล้วใช้ผลแพ้ชนะจากการสุ่มแต่ละครั้งนั้นไม่ทำให้ต้นไม้ของเราฉลาดขึ้นเลย
AlphaGo แก้ปัญหาเหล่านี้ด้วยสิ่งที่เรียกว่า Policy Network กับ Value Network ซึ่งเป็นจุดที่ทำให้ AlphaGo พิเศษกว่าโปรแกรมโกะอื่นๆ
โดย Network ทั้งสองแบบนี้เป็น Neural network ที่ถูกสร้างขึ้นด้วยวิธีหลายๆแบบ (SL – Supervised Learning, RL – Reinforce Learning) ซึ่งจำเป็นต้องใช้พลังในการคำนวนสูงมาก นี่เป็นสาเหตุที่ AlphaGo ต้องใช้คอมพิวเตอร์จำนวนมากในการทำงาน
เนื้อหาตรงส่วนนี้ คุณ http://blog.kosatestudio.com/2016/03/12/how-alphago-work/ ผมจึงขออนุญาติไม่เขียนซ้ำนะครับ
เขียนอธิบายเป็นภาษาไทยไว้แล้วที่ใครที่อยากอ่านต่อ ผมขอแนะนำลิ้งก์ข้างบนเลยครับ (อยู่ในหัวข้อ “Step 1 : Begin from human” )
Chadchapol V.