Tic-tac-toe

ใน
ซื้อหนังสือขายดี "Artificial Intelligence with Machine Learning, AI สร้างได้ด้วยแมชชีนเลิร์นนิ่ง" โดย รศ.ดร.ปริญญา สงวนสัตย์ มาลองอ่านเล่นยังไม่ค่อยรู้เรื่องหรอกเพราะความรู้พื้นฐานน้อย แต่ชอบที่มีโจทย์ตัวอย่างประกอบการอธิบายเป็น Python ภาษาที่กำลังมาแรงช่วงนี้ซึ่งทำความเข้าใจกับโค้ดได้ง่ายกว่า ในบทที่ 2 มีตัวอย่างเกม Tic-tac-toe หรือที่เรารู้จักกันในชื่อ OX เกมเด็กๆ ง่ายๆ ที่อธิบายหลักการในการเลือกตำแหน่งในแต่ละตา กฎในการเล่นทุกคนคงรู้กันดีอยู่แล้วคือมีกระดานขนาด 3x3 ช่อง
|1|2|3|
|4|5|6|
|7|8|9|
 โดยที่ผู้เล่นสองคนแบ่งเป็นฝ่าย O กับฝ่าย X ผลัดกันใส่สัญลักษณ์ฝ่ายตัวเองลงในช่องที่ว่างอยู่ตาละช่อง การที่จะชนะได้จะต้องมีสัญลักษณ์ฝ่ายตัวเองเรียงครบสามตัวจะเป็นแนวนอน แนวตั้ง หรือแนวทแยงก็ได้ถ้าลงจนเต็มทุกช่องก็จะเสมอ เพื่อศึกษาทำความเข้าใจของตัวโปรแกรมอย่างแรกก็ต้องทำตามตัวอย่าง แต่ทำตามอย่างเดียวคงไม่สนุกเลยลองแปลงเป็นภาษาโปรดที่ผมคุ้นเคยดีนั่นก็คือ Lua นั่นเอง

เริ่มจากศึกษาโปรแกรมตัวอย่างก่อนเป็นโปรแกรมง่ายๆ ไม่ซับซ้อนเป็นการเขียนโปรแกรมเชิงคำสั่งธรรมดา (Imperative programming) เหมาะกับการทำความเข้าใจ ในโปรแกรมมีอยู่ 4 องค์ประกอบหลักคือ

  1. เตรียมเครื่องมือ คือการเรียกโมดูลที่จะใช้ในโปรแกรม สำหรับโปรแกรมนี้ใช้ numpy สำหรับช่วยจัดการพวก array และ random ที่เป็น standard library อยู่แล้วสำหรับการสุ่มเลือก
    (ใน random.py มีฟังก์ชั่นในการสุ่มพร้อมให้ใช้งานอยู่หลายตัวนอกจาก random.random() เช่น random.choice(), random.shuffle() เป็นต้นเป็นข้อดีของ Python ที่มี library พร้อมใช้มากมายแทบไม่ต้องลงเพิ่ม ส่วนการลงโมดูลภายนอกเพิ่มเช่น numpy ใช้ pip install numpy ได้เลยหาโมดูลที่ต้องการได้ใน PyPI )
  2. เตรียมข้อมูลได้แก่ O เป็น list ที่เก็บตำแหน่งของ O ในแต่ละตา, X เป็น list ที่เก็บตำแหน่งของ X ในแต่ละตา สุดท้าย win เป็น list ที่เก็บ list ของตำแหน่งที่ทำให้ชนะเกมเช่น [1,2,3],[1,4,7],...
  3. โปรแกรมย่อยหรือฟังก์ชั่นที่แบ่งการทำงานออกเป็นส่วนๆ เช่น displayOX() สำหรับการแสดงผลกระดาน OX หรือ checkWin() สำหรับตรวจสอบผลแพ้ชนะเป็นต้น
  4. โปรแกรมหลักเป็นส่วนเริ่มเกมทำงานเป็นวงรอบไปเรื่อยๆ จนกว่าจะจบเกม เริ่มตั้งแต่รับข้อมูลผู้เล่น=>แสดงผล=>ตรวจผลลัพธ์=>คำนวณตำแหน่งในตาของตัวเอง=>แสดงผล=>ตรวจผลลัพธ์ วนไปแบบนี้โดยเรียกใช้ฟังก์ชั่นในส่วนที่ 3 เพื่อทำงานในแต่ละขั้น
ในเกมนี้ผู้เล่นจะเป็นฝ่ายเริ่มก่อนเป็น O ตามด้วย AI ของเกมเป็น X หลักการคิดของ AI ในเกมนี้ตามตัวอย่างคือ หลังจากผู้เล่นเลือกตำแหน่งแล้วโปรแกรมจะเสือกตำแหน่งว่างขึ้นมาที่ละตำแหน่งแล้วคำนวณความเป็นไปได้ที่จะทำให้ชนะของตำแหน่งนั้นๆ เพื่อหาตำแหน่งที่ดีที่สุดโดยใช้สูตร

V(b) = 1 + X(b) - O(b)

โดยที่ V(b) คือฟังก์ชั่นเป้าหมายที่ตำแหน่ง b ซึ่งเราจะเลือกตำแหน่งที่มีค่านี้มากที่สุด
     ให้ X(b) เป็นผลรวมของ X ในแต่ละแนวที่ไม่มี O อยู่
     และ O(b) เป็นผลรวมของ O ในแต่ละแนวที่ไม่มี X อยู่
โดยขณะทีคำนวณ O(b) นั้นก็ดูว่ามีแนวไหนที่มี O สองตำแหน่งแต่ไม่มี X ด้วย
ถ้ามีแสดงว่า O มีโอกาสชนะในตาหน้าให้ลง X ในตำแหน่งที่ยังว่างของแนวนั้น
แต่ถ้าไม่มีให้กลับไปดูค่า V() ของทุกตำแหน่งแล้วเลือกตำแหน่งที่มีค่ามากที่สุดถ้ามีมากกว่าหนึ่งตำแหน่งก็สุ่มเลือกเอา

ในตัวอย่างนี้ผู้แต่งจงใจทำให้ไม่สมบูรณ์เพื่อให้ผู้อ่านได้ลองปรับปรุงโปรแกรมในคำถามท้ายบทซึ่งผมได้แก้ไขในโปรแกรมภาษา Lua ที่เขียนแล้วโดยมี 3 version ได้แก่
  1. pure Lua ใช้แค่คำสั่งพื้นฐานโดยไม่ได้เรียกใช้โมดูลเสริม ดูโค้ด ox_game
  2. pure Lua รุ่นดัดแปลงเปลี่ยนวิธีเก็บตำแหน่งของ O กับ X และตำแหน่งว่างเพื่อให้โค้ดสั้นลงและลดการใช้ลูป ดูโค้ด ox_game2
  3. Lua+pl มีการเรียกใช้โมดูล Penlight ในการช่วยจัดการเรื่อง list และ list comprehension ซึ่งถ้าจะเอาโค้ดไปลองเล่นต้องติดตั้งโมดูลนี้ด้วยโดยใช้คำสั่ง luarocks install penlight ดูโค้ด ox_game3
    (สำหรับ Lua เข้าไปหาโมดูลที่ต้องการได้ใน LuaRocks )
ส่วนการอธิบายโปรแกรมเทียบกับต้นฉบับ Python ผมทำแยกเป็นส่วนๆ ไว้ใน colab แล้วเข้าไปดูได้ครับ

update: 2019-12-20 14:44

ลองแปลงเป็นภาษา Julia บ้างเลยได้แก้ในส่วนของ ai() อีกรอบให้ตรวจแถวที่มี X สองตำแหน่งและมีตำแหน่งว่างก่อนถ้าพบก็ให้ใส่ X ในตำแหน่งว่างในแถวนั้นแล้วชนะเลยถ้าไม่ค่อยกลับเข้ากระบวนการปกติตามข้างบนคือหาโอกาศชนะของ O เพื่อกันถ้าไม่มีค่อยเอาผลคำนวณมาหาตำแหน่งที่ดีที่สุดในตานั้น แต่ยังพบจุดอ่อนใน AI ของเกมอีกอย่างจากสูตรตำแหน่งที่ดีที่สุดคือตำแหน่งที่ทำให้เกิดผลรวมของตำแหน่งของ X ในทุกแถวที่ยังสามารถชนะได้ของ X ลบด้วยผลรวมของตำแหน่งของ O ในทุกแถวที่ยังสามารถชนะได้ของ O มีค่ามากที่สุดตามที่อธิบายสูตรไว้ในตอนต้น ในกรณีตัวอย่างที่ O เริ่มที่มุมตำแหน่งดีสุดคือ 1 + X(5) - O(5) = 1 + 3 - 2 = 2 ขณะที่ตำแหน่งอื่นมีค่าเป็น 1
|O| | |
| |X| |
| | | |
ถ้าตาถัดมา O ลงตำแหน่งมุมตรงข้ามตำแหน่งว่างที่เหลือจะมีค่าเท่ากับข้างล่างซึ่งทุกตำแหน่งจะได้ X(b) = 4 แต่ตำแหน่งมุมจะทำให้ O(b) เหลือแค่ 2 ในขณะที่ตำแหน่งอื่น O(b) = 3
|O|2|3|
|2|X|2|
|3|2|O|
ดังนั้นตำแหน่งที่ดีที่สุดจะได้เป็นหนึ่งในสองมุมที่เหลือแต่ถ้าตาถัดมา O ลงในตำแหน่งมุมที่เหลืออีกจะทำให้ O มีโอกาสชนะได้ถึงสองแถวซึ่ง X ไม่สามารถกันได้
|O| |O|
| |X| |
|X| |O|
แสดงว่าสูตรนี้ยังไม่สมบูรณ์ไว้ถ้ามีเวลาค่อยหาทางแก้ไขสูตรอีกที
ตอนนี้ก็เอาสูตรเก่าไปทำเพิ่มอีกสองแบบ

  1. ใช้โมดูล AbsTk ทำ UI แบบง่ายๆ ดูโค้ด abstk-ox
  2. ใช้โมดูล lcurses ทำ Text-based UI ดูโค้ด curses-ox * ในโค้ดนี้มีการเปลี่ยนการเรียงลำดับขแวฟังก์ชั่นต่างๆ เพราะลองทำให้เป็น local ทั้งหมดเลยต้องเปลี่ยนลำดับให้ตัวที่ถูกเรียกอยู่ก่อนเพื่อป้องกันปัญหาเรื่อง scope
  3. แถมด้วยโค้ด ox_game ฉบับ Julia ที่ลองหัดดู
สรุปการลองแปลงโค้ดเป็นภาษาต่างๆ นอกจากช่วยให้ทำความเข้าใจการทำงานของโปรแกรมมากขึ้นแล้วยังช่วยให้เรียนรู้และทำความเข้าใจในภาษานั้นอีกด้วยขอให้สนุกกับโค้ดดิ้งครับ 😊

ความคิดเห็น

แสดงความคิดเห็น