Ai Searching algorithm

ใน Post นี้เราจะมาแนะนำหนึ่งในการหาตัวข้อมูลหรือคำตอบของ Ai โดยผ่าน AI algorithm ที่ชื่อว่า Breadth First Search

• BFS หรืออีกคำนึงคือหลักการ FIFO First in Last out ในการหาโหนดข้อมูลที่จะหาใน Tree นั้นๆที่อยากจะหาแต่ในที่นี้เราจะ Algorithm นี้ในการหาคำตอบของเกม 8 Puzzle หลักการในการหาคำตอบจะใช้ตัวของ Level เป็นตัวหลักในการ Search หาคำตอบนั้นเอง

ในการหาคำตอบของ Puzzle อันนี้เราจะใช้ Ai ในการเลื่อนช่องของตัวเลขไปในช่องว่างเพื่อเรียงตัวเลขให้ได้เหมือนกับคำตอบที่เซ็ตไว้

เริ่มจากการ Import Library เพื่อสร้าง 8 puzzle มา

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

การที่จะทำให้ตัวเลขไม่เกินขอบออกไปเราจะใช้คำสั่งดังนี้

แล้วทำการเช็คว่าถึง Goal หรือยัง

ใช้ฟังชั่นนี้ในการสร้างเป็นตารางออกมา

เราสามารถสร้างตัว Path หรือ Move ของ Ai ได้จากคำสั่งด้านบ่างว่า Ai นั้นเดินอย่างไร

การที่ Ai จะรู้ได้ว่าช่องไหนเป็นช่องว่าให้ใช้คำสั่งด้านล่างนี้

ต่อไปเราจะสร้างตัว Puzzle ขึ้นมาจากการใช้ Code ด้านบนโดยทำให้ Ai ใช้ระบบ ฺBFS ในการหาคำตอบนั้นเอง

เราสามารถเซ็ต Starting และ Goal ผ่านโคดด้านล่างนี้

เราสามารถเริ่มให้ Ai เล่นเกมได้ผ่านโคดด้านล่าง

จะได้เป็นคำตอบด้านล่างนี้

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