แก้ปัญหา 8-puzzle ด้วย A* algorithm (Python)

สวัสดีครับผม Blue เป็นนักศึกษาวิศวกรรมศาสตร์คอมพิวเตอร์ที่ KMUTT ครับ ในวันแรกของการเรียนผมก็ได้การบ้านมาทำทันที (TT) ซึ่งโจทย์ที่น่าสนใจ และ มีหลายๆคนเกิดปัญหาในการทำก็เป็นโจทย์ข้อที่ 1 : แก้ 8-puzzle

credit: http://www.8puzzle.com/8_puzzle_algorithm.html

ในวันนี้ผมเลยจะมาอธิบายโจทย์ และ วิธีในการแก้โจทย์ปัญหานี้ครับ

อะไรคือ 8-puzzle?

8 puzzle คือเกม ๆ หนึ่งที่จะมีแป้นตัวเลขอยู่ 8 ตัว และ ช่องว่างหนึ่งช่อง ซึ่งในสมัยเด็ก ๆ หลายคนอาจจะเคยมีของเล่นฝึกสมองในลักษณะนี้ คือเกมเรียงตัวเลข นั้นเอง แต่อาจจะเป็นลักษณะ 15 ตัวเลข

credit: https://cf.shopee.co.th/file/6ae49a3540144340a56e8a4ae02cf639

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

แก้ปัญหา

Algorithm ที่ผมเลือกใช้ในการแก้ปัญหานี้คือ A* algorithm ครับ

Solving 8-Puzzle using A* Algorithm.

โดยขั้นตอนของ algorithm จะอยู่ในลักษณะนี้

1. ทำการ generate ความเป็นไปได้ในการเลื่อนตำแหน่งว่างทั้งหมด
2. คำนวน f-score ของทุกๆความเป็นไปได้
3. เลือกเลื่อนตำแหน่งว่างไปในความเป็นไปได้ที่ให้ f-score น้อยที่สุด
4. ทำซ้ำ 3 steps ด้านบนจนกว่าจะได้ผลลัพท์ตรงกับเป้าหมาย

f-score

f-score คือการนำ g-score + h-score

h-score คือ การนำ ระยะห่างในการ traverse ของแต่ละตำแหน่งมารวมกัน เช่น ถ้า initial state ของเราอยู่ในลักษณะนี้

credit: http://www.8puzzle.com/8_puzzle_algorithm.html

และ เป้าหมายอยู่ในลักษณะนี้

credit: http://www.8puzzle.com/8_puzzle_algorithm.html

จากภาพถ้าเราต้องการเลื่อนเลข 1 ไปช่องมุมซ้ายบนสุด แปลว่า เราจะทำการเพิ่ม h-score ของเลข 1 = 1 (ขยับขึ้น 1 ครั้ง)

เลข 8 ห่างจากตำแหน่งเป้าหมาย ตำแหน่งที่ 8 อยู่ 2 (เลื่อนลง 1 ครั้ง เลื่อนซ้าย 1 ครั้ง) ดังนั้น เราทำการบวก h-score ของตำแหน่งที่ 8 = 2

g-score คือจำนวน step การเลื่อนของชองว่าง หรือ ก็คือผลรวมของช่องที่อยู่ผิดจาก initial state

credit: http://www.8puzzle.com/8_puzzle_algorithm.html

ถ้าปัจจุบันอยู่ในลักษณะนี้

จะมีช่องที่อยู่ผิดที่จากจุดเริ่มต้นคือ 1,2,3,4,5,6,7,8 ได้ g-score = 8

Coding

แล้วก็มาถึงช่วง coding กันครับ โดยสามารถ Download Notebook ได้ทาง link นี้

Colab: https://colab.research.google.com/drive/1UxSLnSbIIk1KXuGLgpQKigbwChqxj5sc?usp=sharing

function win

ใช้ในการตรวจสอบว่า puzzle ในปัจจุบัน ตรงกับ เป้าหมายแล้วหรือยัง

function find

ใช้ในการค้นหาตำแหน่งของเลขนั้นๆว่าอยู่ใน row, col ที่เท่าไร

function f-score

ใช้ในการคำนวน f-score = h-score + g-score

function genOp

เป็น function ในการ generate opportunity ทั้งหมดที่เป็นไปได้ ที่เลข 0 หรือช่องว่างสามารถเลื่อนไป

function swap0

ใช้ในการเลื่อนเลข 0 หรือ ช่องว่าง ไปที่ตำแหน่งต่างๆ

function shuffle

ใช้ในการ ขยับเลข 0 ใน puzzle แบบสุ่มเพื่อใช้เป็นตัว initialize

function solve

เป็น function A* algorithm ที่ใช้ในการแก้ปัญหา 8-puzzle

เมื่อทำการ run ก็จะได้ผลลัพท์สุดท้ายในลักษณะนี้