เทคนิคการอ่านตาเดินล่วงหน้าที่ใช้ใน AlphaGo

ช่วงนี้หลายๆคนคงได้ยินข่าว 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 เราก็จะสามารถเลือกได้ว่าช่องไหนจะดีสุด

 

ลดขนาดของต้นไม้ลง

ในความเป็นจริง เราไม่มีความจำเป็นที่จะต้องไล่ดูไปจนเดินครบทุกช่อง เพราะเรารู้ผลแล้ว เช่น

1. เกมอาจจะจบได้เร็วกว่า เพราะเราได้วาง O สามช่องติดกันแล้ว
2. ไม่มีทางเป็นไปได้ที่จะทำ O X ติดกันสามช่องได้แล้ว
3. เกมถึงจุดที่มีผู้ชนะแน่นอนแล้ว

ดังนั้น พอถึงจุดนี้ เราสามารถคำนวนผล ได้เลย โดยไม่ต้องสร้างต้นไม้ต่อ ทำให้ลดปริมาณการสร้างโนดได้เยอะมาก

ในเกมที่ซับซ้อนมากขึ้นอย่างโกะ  ที่มีช่องทั้งหมด 361 ช่อง ความเป็นไปได้นั้นเยอะมาก (361! นี่เยอะขนาดไหน ลองไป Google ดูครับ)  เราจะสามารถใช้วิธีนี้ในการตัดเล็มต้นไม้ให้เล็กลงได้  เช่น

1. ตอนเริ่มเกมไม่มีใครลงที่เส้น 2 กับ เส้น 1
2. หากเรามีลมหายใจพอแล้ว เราไม่ลงเหมากเพื่อถมพื้นที่ตัวเอง
3. เราไม่ลงหมากในพื้นที่ของศัตรู เพราะถูกจับกินแน่นอน (แต่จะรู้ได้ยังไงว่าโดนจับกินแน่นอนถ้าไม่ค้นหาดู?

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

เช่น ทำให้แต่ละตามีช่องที่เลือกลงเหลือเฉลี่ย 200 แบบ  และเกมส่วนใหญ่รู้ผลใน 200 ตา ต้นไม้ก็ยังใหญ่เกินไปอยู่ดี

 

เดาตาล่วงหน้าด้วย Monte Carlo Search Tree (MCST)

เนื่องจากเราไม่มีทรัพยากรคอมพิวเตอร์ที่จะคำนวนรูปแบบทั้งหมด เราจึงต้องใช้เทคนิคทาง AI เข้ามาเพื่อใช้ในการอ่านเกมล่วงหน้า (Reading)

Monte Carlo Search Tree (หรือต่อไปนี้จะเรียกย่อๆว่า MCST) เป็นเทคนิคที่ถูกใช้กันมากในการสร้าง AI เพื่อเล่นเกม  โปรแกรมเล่นโกะต่างๆในปัจจุบันก็ใช้วิธีนี้ ตัว AlphaGo เองก็ใช้วิธีนี้เช่นกัน

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

โดยโปรแกรมจะทำซ้ำสี่ขั้นตอนนี้เพื่อขยายต้นไม้ไปเรื่อยๆ  เมื่อทดสอบมากพอ ต้นไม้จะสามารถคาดเดาได้ว่าเส้นทางไหนดีที่สุด

ถ้านำมาใช้ในกรณีของโกะ จะเป็นดังนี้

1. Selection – เลือกหมากที่เดินต่อแล้วน่าจะดีที่สุด
2. Expansion – ขยายต้นไม้ต่อในตำแหน่งนั้น
3. Simulation – ทดลองเดินหมากต่อไปจนจบเกม ว่าได้ผลแพ้หรือชนะ
4. Back propagation – นำผลลัพธ์แพ้ชนะ มาปรับค่าที่เก็บไว้ในแต่ละโนด

วิธีนี้จะคล้ายกับการคิดของมนุษย์ที่ใช้ในการเลือกเดินหมาก  และลดปริมาณรูปแบบที่ต้องใช้ในการคำนวนไปได้อย่างมหาศาล

 

แต่ MCST ยังไม่พอที่จะชนะนักเล่นโกะอาชีพได้

เทคนิค MCST นั้นถูกใช้มานานแล้วในโปรแกรมโกะอื่นๆ แต่เทคนิคนี้มีข้อจำกัดอยู่

ตัวอย่างเช่น ในขั้นตอนที่ 3 เราจะทดลองเดินต่อไปจนจบได้อย่างไร

เราอาจจะใช้วิธีการเลือกเดินสุ่มๆเอา แต่ด้วยความที่เกมโกะมีตาเดินให้เลือกเยอะมากกว่าจะจบเกม การเดินสุ่มๆแล้วใช้ผลแพ้ชนะจากการสุ่มแต่ละครั้งนั้นไม่ทำให้ต้นไม้ของเราฉลาดขึ้นเลย

AlphaGo แก้ปัญหาเหล่านี้ด้วยสิ่งที่เรียกว่า Policy Network กับ Value Network  ซึ่งเป็นจุดที่ทำให้ AlphaGo พิเศษกว่าโปรแกรมโกะอื่นๆ

โดย Network ทั้งสองแบบนี้เป็น Neural network ที่ถูกสร้างขึ้นด้วยวิธีหลายๆแบบ (SL – Supervised Learning, RL – Reinforce Learning)  ซึ่งจำเป็นต้องใช้พลังในการคำนวนสูงมาก นี่เป็นสาเหตุที่ AlphaGo ต้องใช้คอมพิวเตอร์จำนวนมากในการทำงาน

เนื้อหาตรงส่วนนี้ คุณ kozartaeneung เขียนอธิบายเป็นภาษาไทยไว้แล้วที่ http://blog.kosatestudio.com/2016/03/12/how-alphago-work/  ผมจึงขออนุญาติไม่เขียนซ้ำนะครับ

ใครที่อยากอ่านต่อ ผมขอแนะนำลิ้งก์ข้างบนเลยครับ (อยู่ในหัวข้อ  “Step 1 : Begin from human” )

 

Chadchapol V.

References

[1] http://www.willamette.edu/~levenick/cs448/goNature.pdf  – Paper ของทีม Deepmind

[2] http://mcts.ai/about/index.html – อธิบาย Monte Carlo Tree Search ฉบับย่อ

[3] http://playtictactoe.org/