เจาะลึก AlphaGo ทำงานอย่างไร ? (ฉบับเขียนโปรแกรมไม่เป็นก็อ่านได้)

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

มนุษย์ vs เครื่องจักร

ช่วงประมาณ 1 สัปดาห์ที่ผ่านมาหลายๆ คนคงเห็นความเคลื่อนไหวมากมายบนโลก Social Network (อ้างอิงจากเวลาที่ผู้เขียนกำลังเขียนอยู่) ที่ว่า Google ได้สร้างสมองกลสุดอัจฉริยะเพื่อมาเล่นเกมกระดานหมากล้อมญี่ปุ่นที่เรียกกันว่า Go เพื่อมาแข่งกับ Lee Sedol นักเล่นโกะระดับ 9 ดั้ง (เป็นระดับสูงสุดของเกม Go) แน่นอนว่าระดับความสามารถของเขาอยู่ระดับต้นๆ ของโลก แล้วอย่างนี้คอมพิวเตอร์จะเอาชนะได้อย่างนั้นหรือ

การแข่งขันครั้งประวัติศาสตร์ ระหว่าง 2 อัจฉริยะระหว่างมนุษย์หัวกะทิชั้นนำของโลก กับสมองกลอันชาญฉลาด ใครจะเป็นผู้ชนะในศึกครั้งนี้

อะไรคือ Go

รูปภาพจาก http://personalidadeinteligenciauned.blogspot.com/2013/05/psicologia-del-go-comparado-con-el.html

Go (โกะในภาษาไทย) เป็นกระดานเกมอย่างหนึ่งจากประเทศญี่ปุ่น ซึ่งกระดานโกะจะประกอบไปด้วยจุดตัดบนกระดานทั้ง 19 x 19 จุด (361 จุด) โดยในกระดานนั้นจะต้อใช้ผู้เล่น 2 คน

แต่ละคนจะใช้หมากสีที่แตกต่างกัน คนหนึ่งสีขาวและคนหนึ่งสีดำ

กติกาอย่างคร่าวๆ คือ ผู้เล่นทั้ง 2 คนจะผลัดกันลงหมากโกะบนจุดตัด 19 x 19 จุดนั้น โดยจะสลับกันวางคนละหมาก

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

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

พอให้เข้าใจคอนเซ็ปพื้นฐานของกระดานนี้พอครับ

อะไรคือ AlphaGo

https://deepmind.com/research/alphago/

AlphaGo เป็นบอทเพื่อมาเล่นกระดาน Go ที่พัฒนาโดย Google จากทีมงาน DeepMind ครับ

ก่อนอื่นหลายท่านอาจจะสงสัยว่าคนที่เป็นคนที่พัฒนาบอทตัวนี้ขึ้นมานั้น เก่งกาจระดับไหนเชียว อันแท้จริงๆ อาจจะไม่ได้เก่งเหนือกว่า Lee Sedol ที่มีระดับ 9 ดั้งสักเท่าไหร่ครับ แต่คนที่เขียน เขาพอเชี่ยวชาญและรู้เทคนิคด้านการเล่น Go อยู่บ้าง เพื่อนำมาประกอบกับพัฒนากลายเป็นบอทตัวนี้

ซึ่งกระบวนการที่เขาใช้พัฒนาบอทนั้น ส่วนหนึ่งได้ใช้ความรู้ด้าน Machine Learning เพื่อนำมาพัฒนาบอทตัวนี้

ซึ่งไอเดียของการพัฒนาบอทของเกม Go ที่ผมจะเขียนต่อไปนั้น ไม่จำเป็นที่จะต้องเอาเทคนิคไปใช้แค่กับกระดาน Go อย่างเดียว แต่ยังสามารถแตกออกไปใช้บนกระดานในรูปแบบอื่นๆ เช่นหมอกฮอส หมากรุกก็ได้

อาจจะมีคนสงสัยว่า…

ถ้าคนที่พัฒนานั้นไม่ได้เก่งเท่า Lee Sedol และเขาสามารถสร้างบอทที่เก่งเทียบเท่า Lee Sedol (อาจจะเหนือกว่า) และเหนือกว่าตนเองได้อย่างไร

ความพิเศษด้านการคำนวณของคอมพิวเตอร์ครับที่ทำให้เกิดสิ่งนี้ขึ้น คนที่เขียนบอทนั้นเขาป้อนเงื่อนไข กฏและกติกาการเล่นเข้าไปในโปรแกรม และโปรแกรมนั้นก็ “เรียนรู้” ที่จะพัฒนาตัวเองจากเงื่อนไขต่างๆ ที่คนเขียนตั้งให้ จนกระทั่งกลายเป็นปรมาจารย์ Go ในที่สุด


Part I : How machine learns?

หลักการสำคัญเลยที่คอมพิวเตอร์สามารถเรียรู้ได้ล้วนมีพื้นฐานมาจากคณิตศาสตร์ทั้งหมดเลยครับ อันดับแรกเราต้องเข้าใจว่าความว่า “เรียน” ในทางคอมพิวเตอร์นั้น ไม่เหมือนสิ่งที่มนุษย์เรียนโดยสิ้นเชิง

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

รูปจาก https://flic.kr/p/pS16bL

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

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

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

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

ปัญหาหลักๆ คือทำอย่างไรให้คอมพิวเตอร์คำนวณได้แม่นยำมากขึ้น

สอนด้วยข้อมูล

ยัดข้อมูลลงไปเยอะๆ เพื่อให้คอมพิวเตอร์สามารถจดจำได้ว่า ถ้าป้อนข้อมูลรูปแบบนี้มานะ ควรจะต้องตอบแบบนี้ ซึ่งผมจะไม่ลงรายละเอียดมาก แต่คร่าวๆ คือคอมพิวเตอร์จะเรียนรู้จากความผิดพลาด หรือเรียนรู้จาก Error

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

ต่อไปผมจะขอเรียกโปรแกรมที่สามารถปรับตัวได้เองนี้ว่า Model

คำว่า “ปรับตัว” ใน Machine Learning คือการปรับตัวเลขบางอย่างภายใน Model ตัว Model เองจะมีตัวเลขจำนวนมหาศาลอยู่ข้างใน เพื่อใช้ในการแปลงข้อมูลที่ส่งเข้ามาใน Model จนกระทั่งสรุปผลออกมาเป็นข้อมูลบางอย่าง

เช่น คุณต้องการสอนให้คอมพิวเตอร์เล่นเกมไพ่เก่งๆ อาจจะเป็นไพ่ Poker ก็ได้ ตัว Model จะประกอบไปด้วย

  1. ข้อมูลนำเข้าเป็นข้อมูล เลข และ ดอก ต่างๆ บนไพ่
  2. ข้อมูลส่งออกก็จะเป็น Probability ของไพ่ ว่าไพ่ใบไหนที่ลงแล้วมีโอกาสชนะมากที่สุด
  3. ตัว Model เอง จะนำข้อมูล เลข และ ดอก ของไพ่ ไปทำกระบวนการทางคณิตศาสตร์ข้างใน เช่น บวก ลบ คูณ หาร ยกกำลัง ถอดรูท หรือคำนวณดิฟ อินทิเกรท โดยใช้ Calculus บางอย่าง ซึ่งกระบวนการข้างในนี้จำเป็นจะต้องมีตัวเลขบางอย่างมาช่วยในการคำนวณ จะใช้แค่ข้อมูลจาก เลข และ ดอก อย่างเดียวไม่
    ซึ่งเลขพวกนี้เป็นเลขที่สามารถปรับค่าได้ โดยรูปแบบการปรับขึ้นอยู่กับว่า Error ที่เกิดขึ้นนั้นมากน้อยเพียงใด

จะเห็นได้ว่าทุกอย่างเป็นคณิตศาสตร์หมด ความซับซ้อนที่เกิดขึ้นในคอมพิวเตอร์ ค่อนข้างจะแตกต่างสิ่งที่มนุษย์คิดเป็นอย่างมาก

กลับมาที่ AlphaGo

Machine Learning เกี่ยวข้องอย่างไรกับ AlphaGo

การเล่นเกมก็มองเป็น Error อย่างหนึ่งได้ครับ เช่นคุณเล่นกับคนระดับธรรมดาแล้วแพ้ แสดงว่ามี Error มาก ถ้าเล่นกับคนระดับเก่งก็อาจจะมี Error น้อยลงมาหน่อย ถ้าเล่นแล้วไม่มี Error เลยแสดงว่าคุณเก่งมากๆ

ซึ่ง AlphaGo ก็เรียนรู้จากความผิดพลาดเหล่านี้ เพื่อมาพัฒนาตัวเองให้ดียิ่งขึ้น

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


Part II : AlphaGo

มาถึงเวลาที่เป็นฮีโร่ของเราละครับ 55555

ใน Part นี้จะใช้ศัพท์เทคนิคเยอะมากนะครับ แต่จะพยายามเขียนให้เข้าใจง่ายที่สุดเท่าที่จะทำได้นะครับ หากมีอะไรสงสัยสามารถคอมเม้นท์ไว้ด้านล่างได้เลยครับ

วิธีการหลักที่ใช้ในการแก้ปัญหา

เทคนิคที่เขาใช้หลักคือ Machine Learning บน Neural Network ครับ (จะมองว่าเป็น Deep Learning ก็ไม่ผิดครับ)

รูปภาพจาก http://www.opennn.net/

อันดับแรกเรามาทำความเข้าใจ Neural Network อย่างสั้นๆ ก่อนว่า ตัว Neural Network เองนั้นจะมีส่วนประกอบสำคัญหลักอยู่ 3 ส่วน ได้แก่

  1. ส่วนแรกเป็นส่วนที่เป็น ข้อมูลเข้า หรือ Input
  2. ส่วนที่สองเป็น ข้อมูลออก คือ Output
  3. ส่วนที่ 3 เป็นส่วนที่อยู่ตรงกลางระหว่าง Input เป็น Output คือส่วนที่สำคัญที่สุดในการเปลี่ยนรูป แกะหาข้อมูล หรือดึงข้อมูลบางอย่างจาก Input และกลายร่างออกมาเป็น Output

เหมือนที่ผมได้เกริ่นไปแล้วใน Part I ข้างต้น

ยกตัวอย่างเช่นคุณมี Input เป็นภาพบางอย่าง และ Output ต้องการให้ Neural Network ตอบว่า ภาพที่คุณป้อนให้นั้นเป็นแมวหรือเป็นสุนัข เป็นต้น

ซึ่งตัว AlphaGo นั้นเกิดจาก Neural Network หลายๆ ชุดประกอบกันอย่างสลับซับซ้อน จนได้เป็น AlphaGo ตัวใหญ่ๆ และอาจจะพ่วงไปยังกระบวนการบางอย่างพิเศษที่ผมจะอธิบายต่อไป

ทุกความเป็นไปได้ ?

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

รูปภาพจาก https://thenewstack.io/google-ai-beats-human-champion-complex-game-ever-invented/

จริงๆ แล้วทำได้นะครับ แต่ว่าอย่าลืมนะครับว่ากระดาน Go นั้นมีจำนวนความเป็นไปได้ของตารางมากกว่าเกมหมากฮอสและเกมหมากรุกในรูปแบบอื่นๆ เรามาลองคำนวณกันคร่าวๆ ดูว่า กระดานโกะนั้นมีเริ่มขึ้นมาตาแรกแล้วจำนวนหมากที่สามารถเดินได้คือ 19 x 19 = 361 ช่อง ต่อไปตาที่ 2 ก็จะเดินได้ 360 ช่อง และตาที่ 3 ก็จะเดินได้ 359 ช่อง

ซึ่งเพียงแค่ 3 ตาแรกของเกม ก็มีจำนวนกระดานทั้งหมด 361 x 360 x 359 = 46,655,640 เท่ากับ 40 ล้านกว่ารูปแบบ (คุณอาจสามารถดูรูปประกอบด้านบนได้ว่า จำนวนมันมหาศาลแค่ไหน)

และถ้าหากคุณเล่นจนจบเกมเลยละ ไม่ใช่แค่ 3 ตาแรกนั้น
จำนวนวิธีที่คุณจะเล่นกระดานโกะทั้งหมดที่เป็นไปได้ คือ…

208168199381979984699478633344862770286522453884530548425639456820927419612738015378525648451698519643907259916015628128546089888314427129715319317557736620397247064840935
ซึ่งมากกว่าจำนวนอะตอมในจักรวาลเสียอีก

ตัวเลขอ้างอิงจาก Number of legal Go positions

ถึงแม้ว่าคอมพิวเตอร์สมัยปัจจุบันนี้จะเร็วมากๆ ก็ตาม สมมุติว่าให้คอมพิวเตอร์สามารถประมวลผลได้ ล้านล้านล้านล้าน กระดานต่อวินาที (ซึ่งเร็วกว่าคอมพิวเตอร์ปัจจุบันในระดับหลัก ล้านล้าน เท่า หรืออาจจะเป็น ล้านล้านล้าน) ด้วยซ้ำ

หรือต่อให้คุณใช้คอมพิวเตอร์ทั้งโลกรวมกัน ปัจจุบันมีคนอยู่ 7.5 พันล้านคน ผมสมมุติให้ทุกคนมีคอมพิวเตอร์คนละ 1000 เครื่อง โดยที่แต่ละเครื่องนั้นสามารถประมวลผล ล้านล้านล้านล้าน กระดานต่อวินาที

จะได้ว่าคุณมีพลังในการประมวลผลเท่ากับ 7.5 x 10³⁶ กระดานต่อ 1 วินาที

เมื่อคำนวณแล้วจะได้ว่า 2.77558×10¹³³ หรือ 9.02 × 10¹²⁵ ปี ถ้าแปลงเป็นภาษาพูดจะได้ว่าคุณต้องใช้เวลาทั้งสิ้น

9 ล้านล้านล้านล้านล้านล้านล้านล้านล้านล้านล้านล้านล้านล้านล้านล้านล้านล้านล้านล้านล้านปี
รูปจาก https://media.giphy.com/media/one2t6IVCI8RG/giphy.gif

ซึ่งกว่าเล่นจบได้เนี่ย โลกคงระเบิดไปแล้วครับ

เพราะฉะนั้น AlphaGo จึงเป็นที่ท้าทายมากต่อทีมพัฒนา ที่เขาสามารถบีบระยะเวลาในการประมวลผลเป็นล้านล้านล้าน…ปี ให้ลดลงเหลือหลักนาทีได้ ซึ่งเป็นอะไรที่เหลือเชื่อมากๆ

ในภาษาคอมเราจะเรียกวิธีที่หาทุกกรณีแบบนี้ว่า Brute Force ครับ

วิธีแก้

คุณอาจจะลดจำนวนความเป็นไปได้ของกระดาน จากที่มีความเป็นไปได้ทั้งหมด 361 จุด ให้เหลือเพียงแค่สัก 2–3 จุด โดยเป็นจุดที่เราค่อนข้างแน่ใจว่าผู้ต่อสู้จะเลือกลงหมากบนจุดเหล่านี้ แล้วเราก็ดักทางหรืออุดช่องโหว่นั้นจาก การทำนาย

การจะลดจุดจาก 361 จุดเหลือ 2–3 จุดไม่ใช่เรื่องง่ายเลย เปรียบเทียบกับมนุษย์คือใช้เซ้นส์ของมนุษย์ในการเดา บวกกับที่เรามีประสบการณ์ในการเล่น และยังมีความจำที่สามารถจำรูปแบบของกระดานได้ แต่คอมพิวเตอร์ไม่มีเซ้นส์ครับ เราต้องสามารถเซ้นส์ให้มัน โดยมีพื้นฐานจากหลักสถิติและหลักการทางคณิตศาสตร์

ดังนั้นทุกอย่างที่ AlphaGo ทำ ทุกอย่างที่ AlphaGo คิดนั้น มีพื้นฐานมาจากตัวเลขทั้งหมดเลยครับ โดยตัวเลขที่มาประกอบกันกลายเป็นตัวเลขที่ซับซ้อนมหาศาล ซึ่งนี่ก็เป็นพื้นฐานของเครื่องคอมพิวเตอร์ทุกเครื่อง ที่หลายๆ ท่านใช้อยู่กันครับ

การจะสร้างเซ้นส์ให้เครื่องคอมพิวเตอร์ได้นั้น ก็ใช้หลักการของ Machine Learning ที่มาลดปัญหาการคำนวณทุกจุดที่เป็นไปได้ ให้เหลือการคำนวณของจุดที่จำเป็น ก็จะลดเวลาไปได้มาก แต่สิ่งที่ต้องทำต่อคือคอมพิวเตอร์จะรู้ได้อย่างไรว่าจุดไหนจำเป็นหรือไม่จำเป็น?

Step 0 : How machine see?

ทุกอย่างที่ AlphaGo มองนั้นเป็นตัวเลขหมดเลยครับ เวลาที่คอมพิวเตอร์มอง AlphaGo ไม่เหมือนที่มนุษย์มองนะครับ มนุษย์อาจจะมองเห็นเป็นหมากสีขาวหรือสีดำแต่สำหรับ AlphaGo นั้นแตกต่าง

AlphaGo อาจจะแทนหมากของเราด้วยเลข 1 และหมากของศัตรูเป็น -1 และให้เลข 0 สำหรับจุดตัดที่ว่างเปล่า แล้วแสดงในรูปแบบของ Matrix ขนาด 19x19 เท่ากับจำนวนจุดตัด และ AlphaGo ก็จะนำ Matrix นี้ไปประมวลผลอีกที

และตัวเลขเหล่านี้จะถูกนำไปคำนวณและนำไปแปลงร่าง เพื่อใช้ในการประมวลผลขั้นตอนอื่นๆ ต่อไปอีกทีครับ

Step 1 : Begin from human

อันดับแรก AlphaGo จะสร้างโปรแกรมมาตัวหนึ่ง (โดยใช้ Machine Learning) โดยผมจะตั้งชื่อโปรแกรมตัวนี้ว่า Next-Move (SL policy network ใน Paper)

ก่อนอื่นขออธิบายจุดประสงค์ของโปรแกรมตัวนี้ (ต่อไปผมจะขอเรียกว่า Model) เป็น Model ที่ใช้สำหรับทำนายการเดินหมากในอนาคตจากรูปแบบของกระดานที่กำหนดให้

ผมขอมองเป็น

  • Input ของ Model นี้คือรูปแบบของกระดานในรอบหนึ่งๆ ซึ่งรูปแบบจะเป็นอิสระ หน้าตาของกระดานจะเป็นอย่างไรก็ได้
  • Output จะบอกความน่าเป็นของแต่ละหมากบนกระดาน โดยค่ามากหมายถึงควรวางอย่างมาก ค่าน้อยคือไม่ควรวาง ซึ่งสามารถเอาค่าควรวางของแต่ละหมาก ไปหาค่าสูงสุดเพื่อเลือกหมากที่จะเดินต่อในตาต่อไปได้
รูปภาพจาก http://www.slideshare.net/ShaneSeungwhanMoon/how-alphago-works
เน้นย้ำว่า Output เป็นค่าควรวาง ไม่ใช่ค่าโอกาสที่น่าจะชนะ หมายความว่า Model เรียนรู้จากกระดานของผู้เล่นมืออาชีพ รู้แค่ว่าตำแหน่งไหนควรวาง ตำแหน่งไหนไม่ควร แต่ไม่ได้หมายถึงโอกาสที่จะชนะ

ยกตัวอย่างจากในภาพด้านบน 0.4 คือเลขที่ค่าควรวาง ส่วนเลข 1 ด้านขวาบอกว่าตำแหน่งนี้คือตำแหน่งที่มีค่าควรวางสูงสุดนะ

วิธีการที่เราจะใช้ Model ตัวนี้เรียนรู้คือเราจะป้อนข้อมูลการเล่นโกะจำนวน 30 ล้านตาเดินจากนักเล่นมืออาชีพในพื้นที่สำหรับการเล่นโกะแบบออนไลน์ชื่อ KGS ลงไปใน Model เพื่อให้ Model เรียนรู้ (ใน Machine Learning จะเรียกว่า Train Model)

โดยตัว Model นี้จะแกะรูปแบบการเดิน จากหน้าตาของกระดานที่ได้มา เช่น หน้าตาของกระดานเป็นแบบนี้ เราควรจะเดินลักษณะนี้นะ เจอแบบนี้เราก็ควรจะเดินลักษณะนี้นะ

ซึ่งหลังจากที่เรียนรู้เสร็จ ความแม่นยำที่ Model จะเดินได้อย่างถูกต้องมีเพียง 57% เท่านั้น (ครึ่งต่อครึ่ง) ซึ่งโอกาสที่จะเดินผิดก็ยังสูงมาก ยังไม่เพียงพอที่จะไปฝ่าฝันกับมือวางอันดับต้นๆ ของโลกได้ แต่ก็เป็น Model ที่ฉลาดมากพอที่จะฝ่าฝันคนทั่วไปปกติได้ (เพราะว่าข้อมูลที่เอามาป้อนนั้น เป็นข้อมูลการเล่นกระดานจากผู้มีประสบการณ์)

ดังนั้นก็ต้องถึงเวลาอัพเกรดความฉลาดให้มันครับ

Note: ใน Paper เองจะเรียก Model ตัวนี้ว่า SL policy network ซึ่ง SL ก็ย่อมาจาก Supervised Learning ที่เรียนรู้จากกระดานการเดินของมนุษย์

Step 2: Self-playing

เนื่องจากความแม่นยำของ Next-Move ยังไม่มากพอที่จะต่อกรกับมนุษย์ระดับท็อบๆ ของโลกได้ เราจึงจำเป็นที่ต้องขยับขึ้นอีกก้าวหนึ่ง

โดยการนำ Next-Move ทั้ง 2 ตัวมาแข่งกันเองครับ แล้วแต่ละตัวก็จะเรียนรู้จากความผิดพลาด หรือเรียนรู้ลักษณะการเดินที่ดี หรือการเดินที่จะไปสู่ผลของการชนะ และก็พัฒนาตนเองอีกครั้ง

รูปจาก http://www.slideshare.net/ShaneSeungwhanMoon/how-alphago-works

หลังจากเรียนรู้การเล่นเกมครั้งแรกจบ พอครั้งต่อไปก็เอาตัวที่พัฒนาอยู่แล้ว มาเล่นซ้ำอีกรอบจนพัฒนาไปเรื่อยๆ จนกระโดดไปสู่ระดับผู้เล่นมืออาชีพ ซึ่งผู้พัฒนาได้จับ Next-Move มาแข่งกันเองเป็นล้านครั้ง

หลังแข่งเสร็จ ก็พบว่าเมื่อว่า Next-Move หลังจากเล่นเสร็จรอบที่ล้าน มาแข่งกับ Next-Move เวอร์ชั่นแรกสุด ตัวที่พัฒนาแล้วมีโอกาสชนะมากถึง 80% ทีเดียวเลย

ซึ่งต่อไปผมขอเรียกว่า Next-Move Smarter

Note: รูปแบบในการ Train ข้อมูลในครั้งนี้จะเป็นลักษณะของ Reinforcement Learning โดยนำ Weight จากโมเดล SL policy network มา Train โดยรูปแบบแข่งกันเองจนกลายเป็น RL policy network

เขาเคลมว่าเมื่อนำตัว Next-Move Smarter ไปแข่งกับบอทเกมโกะอีกตัวที่ชื่อว่า Pachi ที่เป็นบอทเกมโกะแบบ Open Source (เปิดเผยโค้ด) ที่เก่งที่สุดในตอนนั้น มีโอกาสชนะมากถึง 85%

ซึ่งหยุดแค่ Step ที่ 2 คุณก็ได้บอทที่เก่งมากๆ แล้ว แต่ทีมพัฒนา AlphaGo เขายังไม่หยุดแค่นั้น เป้าหมายของเขาคืออันดับหนึ่งของโลก

Step 3: Search Reduction

ขอทวนสักนิดว่า ในขั้นตอนที่ 1 กับ 2 นั้น เป็นการคิดแบบ turn-by-turn หมายความว่าคอมพิวเตอร์เห็นกระดานในลักษณะอย่างไร แล้วเอาหน้าตาของกระดานโยนเข้าไปใน Next-Move Smarter และ Next-Move Smarter ก็จะบอกว่าควรจะหย่อนหมากลงจุดไหนเพื่อทำให้โอกาสในการชนะมากที่สุด

จะเห็นว่าไม่มีการทำ Search เลยแม้แต่น้อย แค่ดูคำนวณว่าลงจุดไหนแล้วมีโอกาสชนะมากที่สุดเท่านั้น คือดูแต่ละตาว่าควรลงหมากไหนดีที่สุด แล้วลงไปเลย

รูปภาพจาก https://flic.kr/p/sd7vew

ซึ่งการที่เราเลือกที่จะเดินบนเส้นทางที่ดีที่สุดในแต่ละครั้ง ไม่ได้หมายความว่าสุดท้ายแล้วมันจะกลายเป็นเกมที่ดีที่สุด

เพราะว่าการที่เราเดินหมากแย่ในบางตานั้น มันจะช่วยพลิกสถานการณ์ตอนท้ายเกมให้กลับมาดีได้ในที่สุด เปรียบเป็นภาพง่ายๆ คือถ้าคุณเคยเล่นหมากฮอส คุณอาจจะยอมให้ศัตรูมากินหมากของคุณก่อน 1 หมาก แล้วคุณค่อยกินกลับเป็น 2 ทอดต่อ

การที่เราเลือกตาเดินที่ดีที่สุดในแต่ละครั้ง ไม่ได้หมายความว่าภาพรวมของเกมทั้งหมดจะดีที่สุดเสมอ

วิธีแก้คือใช้วิธี Search ครับ

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

ซึ่งขอย้ำอีกรอบว่าหมากที่นำไปสู่โอกาสที่จะชนะของเกม (Long-term) ไม่ได้จำเป็นจะต้องเป็นหมากที่ดีที่สุดในแต่ละตาเสมอ (Short-term)

สำหรับรายละเอียดต่อไปจะออกไปทาง Technical สักนิดนะครับ ถ้าอ่านรอบแรกไม่เข้าใจก็ไม่เป็นไรนะครับ ผมยังไม่แน่ใจเลยจะเขียนรู้เรื่องรึเปล่า ฮ่าๆๆ

Step 3.1 : Next-Move Faster

เราจะมี Model อีกตัวครับ จะเห็นว่าชื่อคุ้นๆ ใช่ไหมครับ ตัวนี้เหมือนกับตัว Next-Move ที่กล่าวไว้ในข้อ 1 เลยครับ

แต่ตัวนี้จะเป็นตัวที่เร็วกว่ามากๆ แต่แลกมาด้วยความแม่นยำที่น้อยลง คือ Model ตัวนี้เป็น Model ที่เรียนรู้จากหมากกระดานของคน แล้วจับรูปแบบการลงหมากต่างๆ จนสามารถลงได้อย่างแม่นยำ

แต่การจะทำให้แม่นยำได้นั้น ต้องใช้ตัวเลข (Weight) เข้ามามีบทบาทมากมายในการทำให้ Model ตัวนี้แม่นยำมากขึ้น

ตัว Next-Move Faster คือ Model ที่ลดจำนวนตัวเลขลง เพื่อให้ไม่เปลืองเวลาในการประมวลผลครับ ซึ่งตัว Next-Move Faster ใช้เวลาเพียงแค่ 2 µs เท่านั้น ในขณะที่ Next-Move (ทั้งแบบแรกและแบบ Smarter) ใช้เวลาไป 3 ms ซึ่งเร็วกว่าถึง 1500 เท่า!

Note:ใน Paper จะเขียนไว้ว่า Model ตัวนี้เป็น Rollout Policy ครับ

Step 3.2: Value Evaluation

รูปภาพจาก https://gogameguru.com/i/2016/03/deepmind-mastering-go.pdf

อันนี้เป็น Model ที่แปลกใหม่ไม่เหมือน 3 อันก่อนที่เคยกล่าวมาในข้างต้นเลยครับ

สำหรับจุดประสงค์ของ Model ตัวนี้ ถ้าให้เดาจากชื่อก็อาจจะพอๆ เดาได้นะครับ มันเป็น Model ที่ใช้สำหรับคำนวณว่าหน้าตากระดานปัจจุบันนี้ (state) มีโอกาสที่จะชนะมากน้อยขนาดไหน ซึ่งออกมาในรูปแบบของตัวเลขตัวเลขหนึ่ง (value function)

  • Input ของ Model นี้เป็นเพียงรูปแบบของกระดานในรอบหนึ่งๆ เป็นหน้าตากระดาน ซึ่งคำว่าหน้าตาในที่นี่หมายถึงตำแหน่งของหมากสีขาวและสีดำทั้งกระดานประกอบเป็นกระดานๆ อันหนึ่ง
  • Output เป็นตัวเลขตัวเดียวที่บอกว่ากระดานหน้าตาแบบนี้เนี่ย มีโอกาสมากน้อยเท่ากับเท่าไหร่ ย้ำนะครับว่า Output คือตัวเลขแค่ตัวเดียวเท่านั้น

พูดง่ายๆ คือ Model ตัวนี้จะบอกโอกาสชนะมากหรือน้อย ขึ้นอยู่กับหน้าตาของกระดานครับ

โดยลักษณะการเรียนรู้ของ Model นี้ จะจับเอา Next-Move Smarter มาจำลองการเดินหมากในแต่ละตา หลังจากเล่นเสร็จในเกมหนึ่งๆ ก็จะอัพเดทการแพ้หรือการชนะกลับไปยังรูปแบบการเดินทั้งหมดก่อนหน้า เพื่อจดจำว่าหน้าตาของกระดานแบบนี้จะนำไปสู่แพ้หรือการชนะ

ผมจะขอเรียก Model ตัวนี้ว่า Value-Evaluation

Note: ใน Paper ก็คือ Value Network ครับ ซึ่งจะเขียนในรูปแบบของ V(s) โดย s แทน state ของกระดาน และ V(*) คือ function คำนวณ Value จาก state ที่ใส่เข้าไป

Step 3.3: Monte-Carlo tree search

รูปภาพจาก https://stlong0521.github.io/20160409%20-%20MCTS.html

มาถึงพระเอกของ AlphaGo กันแล้วละครับ MCTS (Monte-Carlo tree search) คือการที่เราจะค้นหาวิธีการเล่นแบบต่างๆ โดยจะมองการค้นหาเป็นการคิดทบล่วงหน้าก็ได้

ก่อนอื่นอยากให้มองการค้นหาเป็นลักษณะของต้นไม้ (Tree) ที่จากตาปัจจุบัน ก็จะมีจำนวนหมากที่เป็นไปได้หลายๆ แบบ ซึ่งเราก็พยายามจะจำลองรูปแบบการเดินต่างๆ แล้วลองคิดล่วงไปอีก 1 ขั้น และแต่ละขั้นที่เราคิดลึกลงไปก็จะมีรูปแบบการเดินแบบต่างๆ ที่ต่างกันไปอีก

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

คุณก็จินตนาการว่าวันที่เริ่มต้นมีทางเลือกซ้ายกับขวา วันแรกคุณไปซ้ายก็จะเจอซ้ายกับขวาอีกวันต่อไป ถึงแม้วันแรกคุณจะเลือกขวา คุณก็จะไปเจอซ้ายกับขวาในวันต่อไปอีก เหมือนกับการที่เราเล่นเกมและเลือกลงหมากไปอนาคตอาจจะรูปแบบหมากอื่นๆ ให้เลือกอีก

กลับมาพูดเรื่องของ Tree ใน Tree ก็จะประกอบด้วยกิ่ง (Edge) และใบ (Node) ผมอยากให้มองว่าใบแต่ละใบของต้นไม้ คือหน้าตาของกระดานในแบบต่างๆ ที่เราจินตนาการขึ้น ส่วนกิ่งคือทางเลือกที่เราเลือกในแต่ละตา ถ้าเทียบกับตัวอย่างข้างต้นคือการเลือกซ้ายหรือเลือกขวา เป็นกิ่ง 2 อัน กิ่งที่เลือกซ้ายและกิ่งที่เลือกขวา ส่วนใบนั้นเป็นแค่หน้าตาของกระดานหรือตำแหน่งที่คุณอยู่ในเขาวงกตเท่านั้น


กลับมาพูดเรื่อง Monte-Carlo tree search อีกครั้ง

MCTS ใช้หลักการของ Tree มาใช้ในกระบวนการของ AlphaGo ซึ่งมันประกอบไปด้วยกิ่ง (Edge) และใบ (Node) ทั้งคู่ ซึ่งหลักๆ แล้วใบจะเก็บหน้าตาของกระดานโกะ ส่วนกิ่งจะเป็นการวางหมากในแต่ละตา

และ MCTS จะมีตัวเลขตัวหนึ่งที่คำนวณว่าการเลือกเส้นทาง (Action) นั้นๆดีแค่ไหน ซึ่งตัวเลขตัวนั้นจะมีการเปลี่ยนแปลงค่าไปตามกระบวนการค้นหาของ MCTS ซึ่งผมจะไม่ลงรายละเอียดลึกมาก ซึ่งตัวเลขตัวนี้เรียกว่า action value หรือ Q (หรือ Q-value)

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

ดังนั้นจำเป็นต้องมีข้อมูล 2 อย่างคือ หน้าตาของกระดาน และ ลักษณะการเดิน เพื่อคำนวณ Q

Note: ถ้าอธิบายเป็นสมการน่าจะเข้าใจง่ายกว่าครับ Paper เขียนเป็น Q(s,a) โดย s คือ state ของกระดาน และ a คือ action แต่ละครั้ง จึงจำเป็นต้องใช้ทั้งคู่เพื่อคำนวณ Q

กลับมาถึงเวลาทำความเข้าใจกระบวนการของ MCTS กันละครับ ซึ่ง MCTS ที่นำมาใช้ใน AlphaGo นั้นค่อนข้างจะพิสดารเล็กน้อย ผมจะค่อยย่อยเนื้อหาแบ่งเป็น 2 ส่วนหลักๆ ได้แก่

การแตกกิ่ง

รูปภาพจาก https://gogameguru.com/i/2016/03/deepmind-mastering-go.pdf
  1. จากกระดานปัจจุบัน ก็จะจำลองการเดินแบบต่างๆ (แตกกิ่งให้แก่ใบ) โดยแต่ละการเดินก็จะโอกาสการแพ้ชนะไม่เหมือนกัน โดยโอกาสที่จะชนะในแต่ละการเดินนั้นคำนวณมาจาก Next-Move ใน Step 1 
    กำหนดให้โอกาสที่จะชนะเป็นค่า P ซึ่งจะนำค่า P นี้ไปคำนวณร่วมกับค่า Q ด้วย (ดังนั้นในแต่ละกิ่งจะมีค่า P และ Q อยู่ทั้ง 2 ค่า)
  2. เลือกกิ่งที่มีค่า Q สูงสุด โดยคำนวณรวมกับค่า P แล้วเลือกค่า Q,P ที่คำนวณเสร็จแล้วที่มีค่าสูงสุด โดยจะเลือกใบของกิ่งที่มีค่า Q,P สูงที่สุดเพื่อไปแตกกิ่งใหม่ต่อ
  3. เสร็จแล้วก็จะทำคล้ายๆ ข้อ 1 อีกครั้ง คือแตกกิ่งจากใบที่เลือกจากข้อ 2 โดยกิ่งจะคำนวณค่า P ไว้ด้วย
  4. เลือกกิ่งที่มีค่า Q,P สูงสุด ซึ่งกิ่งที่เลือกนั้นไม่จำเป็นต้องเป็นกิ่งที่เพิ่งแตกออก หรือเป็นกิ่งที่อยู่ชั้นล่างที่สุด แต่จะเป็นกิ่งจากตรงไหนก็ได้ ตำแหน่งไหนก็ได้ของต้นไม้ แล้วเอาใบของกิ่งที่เลือกมาไปแตกต่อ
  5. แตกกิ่งจากใบที่เลือกในข้อ 4
  6. เลือกกิ่งที่ Q,P สูงสุด แล้วเอาใบของกิ่งที่เลือกไปแตกต่อ
  7. ไปเรื่อยๆ

จะเห็นว่าเราสามารถยุบขั้นตอนพวกนี้ให้เข้าใจง่ายๆ ได้เป็น

  1. แตกกิ่ง
  2. เลือกใบจากกิ่งที่มี Q,P สูงสุด เพื่อนำใบไปทำข้อ 1

แล้ววนอย่างนี้ไปเรื่อยๆ แต่ถ้าเราวนไปอย่างนี้ด้วยจำนวนกิ่งและใบที่มากมายมหาศาล ถ้าแตกอย่างนี้ก็ไม่ต่างอะไรจากการที่เราไล่ทุกกรณีที่เป็นไปได้ ดังนั้นจึงต้องมีระยะที่เราควรจะหยุดแตกกิ่งได้แล้ว

ระยะหยุดแตกกิ่ง

ระยะหยุดแตกกิ่ง ไม่ใช่ระยะที่เราแตกกิ่งจนพบคำตอบแล้ว เช่น คุณกำลังจินตนาการภาพล่วงหน้าไป 3 สเต็ป แต่ที่คุณจินตนาการนั้นไม่ใช่ภาพปลายทางที่จบเกมแล้ว แค่จินตนาการไว้แค่ 3 ขั้นเท่านั้น

การหยุดแตกกิ่งก็เช่นกัน การแตกกิ่งของต้นไม้หมายถึงคุณมีภาพกระดานที่อยากคิดล่วงหน้า แตกกิ่งเพื่อจินตนาการถึงการเดินแบบต่างๆ และการแตกลึกลงไปคือการคิดกระโดดไปหลายๆขั้น แต่ไม่ได้หมายความว่าคุณจะคิดจนถึงจบเกมแล้ว

คำถามคือทำไมเราไม่แตกกิ่งไปเรื่อยๆ จนกระทั่งพบคำตอบละ

ถ้าเรายังจำได้ Part II ผมกล่าวไว้ว่าจำนวนความเป็นไปได้ของกระดานโกะมีมากกว่าอะตอมในจักรวาล นั่นคือเหตุผลว่าทำไมเราไม่ควรแตกกิ่งไปเรื่อยๆจนพบคำตอบ

เราหยุดแตกกิ่งเมื่อเราคิดนานเกินไปครับ (ซึ่งใน Paper ได้เขียนถึง threshold ต่างๆ ที่เป็นเงื่อนไขในการแตกกิ่งครับแต่ผมจะไม่ขออธิบายส่วนนี้) เมื่อคิดนานไปเราก็หยุดคิดและเอาเฉพาะภาพที่ดีที่สุดที่เราจินตนาการได้เพื่อมาเดินหมากต่อ

ซึ่งตัว MCTS นั้น การที่เราแตกกิ่งมาได้กลางทาง แต่ยังไม่ถึงปลายทาง เราจะรู้ได้อย่างไรว่าปลายทางนั้นมันดีหรือไม่ดี AlphaGo จึงเสนอไอเดียนี้ครับ


รูปภาพจาก https://gogameguru.com/i/2016/03/deepmind-mastering-go.pdf

ยังจำ 3.1 กับ 3.2 ที่ผมเขียนไปข้างต้นได้ไหมครับ จะเห็นว่ามันยังไม่ได้ถูกใช้งานใดๆเลย เราจะนำ 3.1 กับ 3.2 นี่ละครับ เข้ามารวมใน MCTS

3.3.1 MCTS + Value-Evaluation

  1. เมื่อกิ่งหยุดแตกกิ่ง สิ่งที่ต้องทำคือคำนวณว่ากิ่งที่หยุดแตกนี้มีโอกาสชนะมากน้อยขนาดไหน และต้องเร็ว ไม่เปลืองเวลามาก
  2. เมื่อหยุดแตกกิ่ง คุณก็นำใบ ซึ่งใบนั้นคือหน้าตาของกระดาน เราสามารถเอาหน้าตาของกระดานไปใส่ใน Value-Evaluation จะทำให้สามารถวิเคราะห์โอกาสชนะมากน้อยจากกิ่งได้เลย

หรือ

3.3.2 MCTS + Next-Move Faster

  1. เมื่อหยุดแตกกิ่ง สิ่งที่ต้องทำคือคำนวณว่ากิ่งที่หยุดแตกนี้มีโอกาสชนะมากน้อยขนาดไหน
  2. เมื่อหยุดแตกกิ่ง คุณก็นำใบ ซึ่งใบนั้นคือกระดาน คุณก็นำกระดานนี้ไปเล่นต่อโดยใช้ Next-Move Faster ที่เร็วพุ่งติดจรวด ที่เล่นจากกิ่งที่ค้างอยู่ เล่นไปเรื่อยๆจนไปสู่จุดจบของเกม เมื่อจบเกมแล้วก็ดูผลลัพธ์ว่าคุณจะแพ้หรือจะชนะและโอกาสเท่าไหร่

ซึ่งการคำนวณค่าโอกาสชนะมากน้อยของแตกละใบของกิ่งที่หยุดแตกนั้น มี 2 วิธีครับ วิธีแรกคือใช้ Value-Evaluation ส่วนวิธีที่สองคือวิธี Next-Move Faster ซึ่งบางทีเขาก็เอา 2 วิธีมาผสมกันและคำนวณอย่างละครึ่งครึ่งด้วยครับ

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

กลับไปสู่จุดเริ่มต้น

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

จำได้ไหมครับว่าก่อนที่จะแตกกิ่งครั้งแรกสุดนั้น 
เรากำลังทำอะไรอยู่ แล้วเราแตกกิ่งเพื่ออะไร

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

คำถามคือเราจะเล่นต่ออย่างไรหลังจากคำนวณค่า Q และแตกกิ่งจนเสร็จสิ้นแล้ว เราจะได้กิ่งหน้าตาประหลาดๆ ถ้าให้กระดานปัจจุบันเป็นใบที่อยู่ด้านบนสุด ส่วนกิ่งที่แตกอยู่ด้านล่าง

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

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

ใครมีลูกเยอะสุดเลือกคนนั้นเลยครับ

ซึ่งลูกก็คือใบถัดไป หรือกระดานถัดไปที่เราเลือกเดินครับ

จริงๆ ใน Paper เขียนไปว่าเป็นจำนวน Visit Count ซึ่งจะมองว่ามันคือเป็น S’ (Next State) ที่มี leaves เยอะที่สุดครับ S’ ที่มี leaves เยอะสุดก็เลือกอันนั้น ซึ่งตัวเลขอาจจะไม่ตรงกับการนับแบบลูก หลาน เหลนแบบเป๊ะๆ แต่อยากให้เข้าใจ Concept ครับ
ซึ่งมันสมเหตุสมผลไหม ก็ค่อนข้างสมเหตุสมผลครับ เพราะเวลาแตกกิ่งเราเลือก Q ที่เยอะที่สุด ซึ่งกิ่งที่แตกออกมาก็เป็นกิ่งที่มี Q-value สูงมาก ดังนั้นการเลือก Next State จากจำนวนกิ่ง (ซึ่งแต่ละกิ่งมี Q สูง) ก็ค่อนข้างสมเหตุสมผลครับ

Step 4: Summarize

ในที่สุดก็มาถึงบทสรุปสักทีหลังจากที่เราผ่านมาอย่างยืดยาว จากทั้งหมดนี้เราสามารถอธิบายอย่างคร่าวๆ ด้วยภาพๆ นี้ครับ

ภาพจาก Paper https://gogameguru.com/i/2016/03/deepmind-mastering-go.pdf

ขั้นตอนแรก (Step 1) คือ Next-Move เราเอากระดานจากผู้เล่นมาหารูปแบบความสัมพันธ์จนได้เป็น Model ที่ชื่อว่า SL policy network

หลังจากนั้น (Step 2) เราเอา Next-Move มาแข่งกันเองเพื่อปรับปรุงตัวเองให้เก่งขึ้นจนได้เป็น RL policy network

แล้วก็ได้สร้าง Next-Move Faster หรือ Rollout policy (Step 3.1) โดยปรับให้ตัวเลขที่ใช้คำนวณน้อยลง และเอา Next-Move Smarter จาก Step 2 มาจำลองการเดินเพื่อคำนวณหา Value-Evaluation ได้ออกมาเป็น Value Network (Step 3.2)

ภาพด้านขวาอธิบายว่า Policy network จะดูรูปแบบตารางทั้งตารางแล้วหาว่าความน่าจะเป็นของหมากในกระดานว่าควรวางมีมากน้อยเพียงใด ส่วน Value Network ก็จะดูภาพของตารางทั้งตารางแล้วบอกว่าตารางนี้มีค่าน่าจะเป็นที่จะชนะมากน้อยเพียงใด

ภาพจาก Paper https://gogameguru.com/i/2016/03/deepmind-mastering-go.pdf

อันที่เป็นผลลัพธ์สนุกที่ทาง DeepMind ได้ลองยกตัวอย่างมาให้เราดูครับ ว่าผลลัพธ์จากกระบวนการทั้งหมดที่ AlphaGo คิดนั้นเป็นอย่างไรบ้าง

A อันนี้เป็นข้อมูลจาก Value Network (Value-Evaluate) ครับ ซึ่งข้อมูลนี้ไม่ได้มาจาก Value Network โดยตรงนะครับ เนื่องจาก Value Network ต้อง Input กระดานทั้งใบแล้วออกมาเป็นค่าเพียงค่าเดียวครับ 
เขาจึงต้องลองวางหมากไปก่อน และคำนวณ Value Network หลังจากวางหมากไปแล้ว แล้วเอาหมากที่ลองวางออก แล้วลองวางที่ตำแหน่งอื่น คำนวณ Value ใหม่ และไล่ทำทีละหมากจนครับทุกๆ ช่องแล้วเอามาแสดงให้ดูครับ

B อันนี้เป็นตัวเลข Q ต่างๆ จากการทำกระบวนการใน MCTS คู่กับ Value Network (Value-Evaluate) ที่ได้อธิบายไปใน 3.3.1

C อันนี้เป็นตัวเลข Q ต่างๆ จากการทำกระบวนการใน MCTS แต่เป็นคู่กับ Rollout Policy (Next-Move Fast) ที่ได้อธิบายไปใน 3.3.2

D เป็นความน่าจะเป็นที่ควรลงมากจาก SL policy network (Next-Move) ครับ

E เป็นจำนวนลูก (Visit Count) ของแต่ละหมากในต้นไม้ MCTS ที่เกิดจากการแตกกิ่งก้านจนเสร็จเรียบร้อยแล้ว คาดว่าตอนที่กำลังแตกกิ่งนั้นใช้ MCTS คู่กับ Value Network และ Rollout policy ทั้งคู่เลยครับ

F เป็นการที่ AlphaGo ลองทำการเล่นของหมากขาวและหมากดำสลับกันไปเรื่อยๆ

Part III : Summarize

วิธีทั้งหมดจำเป็นต้องใช้กับ AlphaGo อย่างเดียวหรือไม่

ก่อนหน้าที่เขาจะสร้าง AlphaGo ขึ้นมา ก็ได้มีเกมอย่างหมากฮอส หมากรุก โอเทโล่ที่ปัจจุบันมีบอทที่สามารถโค่นมนุษย์ได้แล้ว

ยกเว้นเกมกระดานเกมเดียวคือกระดาน Go ที่เป็นกระดานที่ใหญ่ที่สุดและซับซ้อนมากกว่าหมากฮอส หมากรุกเป็นหลายๆ เท่า ความยากไม่ก็ใช่เพียงแค่ความซับซ้อนเท่านั้น แต่ยังเป็นจำนวนความเป็นไปได้มหาศาลในการเล่นเกมของ AlphaGo

เขาจึงสร้างสิ่งที่ขึ้นมาเพื่อแก้ปัญหาความเป็นไปได้มหาศาลของ AlphaGo ซึ่งถ้าหาก AlphaGo แก้ได้ เกมหมากกระดานที่เหลือก็แทบจะกระดิกนิ้วแล้วคำนวณได้เลยครับ ถือได้ว่าเป็นของเปลี่ยนโลกจริงๆ

AlphaGo น่ากลัวหรือไม่

น่ากลัวครับ แต่ความน่ากลัวในที่นี้หมายถึงพลังในการประมวลผลของคอมพิวเตอร์ และคนที่สร้างมันขึ้นมาครับ ซึ่งสิ่งแรกที่ผมอ่าน Paper อันนี้ ขณะที่ผมอ่านไปก็ได้แต่พึมพาว่า

เขาคิดได้ยังไง !???

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

ความน่ากลัวของ AlphaGo คือพลังประมวลล้วนๆ เลยครับ ส่วนความน่ากลัวของคนสร้างคือ เขาสามารถลดระยะเวลาจากระยะเวลาที่ต้องใช้ประมวลผลกระดานโกะที่มีจำนวนความเป็นไปได้มากกว่าอะตอมในจักรวาล ให้สามารถทำงานได้ภายในชั่วโมง หรืออาจจะเป็นหลักนาที หรือเป็นหลักวินาที

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

Machine Learning บน AlphaGo

ผมคิดว่านอกจากความฉลาดล้ำและเก่งกาจของ AlphaGo แล้ว ถ้าพูดถึงในแง่ของ Machine Learning แล้ว AlphaGo คือเทคโนโลยีรวมศาสตร์ทุกๆ ด้านเข้ามารวมกันครับ

  • ใช้ Classification บน SL policy network
  • ใช้ Reinforcement Learning บน RL policy network
  • ใช้ Regression บน Value Network
  • และยังเอาทั้ง 3 อันนี้มารวมกันและทำ Searching โดยใช้ Monte-Carlo tree search

ซึ่งมันเป็นงานที่สุดของที่สุดที่รวมศาสตร์ทั้ง 3 สายเข้ามาบรรจุในงานชิ้นเดียว ถือเป็นงานอันหนึ่งที่ล้ำค่ามากของทีมงาน DeepMind และ Google ขอบคุณสำหรับ Paper คุณค่าขนาดนี้มากๆ ครับ

Credit

ข้อมูลและข้อความทั้งหมดที่ผมเขียนขึ้นนั้น บ้างก็เขียนเอง บ้างก็นำมาจากเว็บไซต์ต่างๆ บ้างก็นำมาจาก Paper ตามสังขารที่มีครับ หากมีข้อผิดพลาดประการใด discuss ที่ช่องคอมเม้นท์ด้านล่างได้เลยครับ ถ้าหากผิดพลาดประการใดก็ขออภัยมา ณ ที่นี้ด้วยครับ :D

One clap, two clap, three clap, forty?

By clapping more or less, you can signal to us which stories really stand out.