Python , 8 Puzzle และ A*

A* -> Astar -> Astral ก็ต้อง Astral Air สิ

เกริ่นว่า เจ้าของบทความได้เข้าค่าย Super Ai Engineer ซึ่งทุกๆคาบเรียนก็ย่อมมีการบ้านนั่นหล่ะ เผอิญมีการบ้านข้อนึงที่คิดว่ายาก (คือเขียนครั้งแรกน่าจะหลายชั่วโมง) จึงคิดว่าบทความนี้น่าจะมีประโยชน์กับหลายๆคน

1. เขียน 8 puzzle 2. เขียน depth-first search พร้อม อะนิเมชั่น

โจทย์มาสั้นๆ 2 ข้อรวมกันได้บรรทัดนึง แต่ Code นี่น่าจะเป็นร้อยบรรทัดได้
เจ้าของบทความคิดว่าทุกๆคนน่าจะเคยเล่น 15 puzzle แน่ๆ จึงขอละไว้ฐานที่เข้าใจก่อน โจทย์ข้อนี้เป็น 8 puzzle แทน ซึ่งมีเพียงตัวเลข 8 ตัวในตาราง 3x3

แน่นอนว่า เราไม่สามารถบอกว่า “นาย ก. ที่เอา 15 puzzle ของคุณไปนั่งเล่น 2 ชั่วโมง พึ่งหาคำตอบให้คุณได้” ดีเทียบเท่ากับ “นาย ข.ที่เคาะๆสามนาทีได้คำตอบ” ได้ฉันใด จึงต้องมีการกำหนดว่า วิธีไหนที่เป็นการแก้ปัญหาที่ดีกว่า อาจจะเป็น “เวลาที่เอาไปใช” ้แต่วิธีการขยับ 15 Puzzle เดียวกัน ก็สามารถทำให้เวลาแตกต่างกันได้ ขึ้นอยู่กับคนที่อยู่หน้า Puzzle นั้น

จึงต้องมีการกำหนด Cost Function ขึ้นมา

เพื่อบอกว่า การแก้ปัญหาไหนแบบไหนดีกว่า ใน 8 Puzzle “Cost Function” ย่อมเป็น “จำนวนครั้งที่ขยับช่องว่าง จนได้คำตอบ”

สิ่งที่ต้องรู้ก่อนอ่านบทความนี้

1. Queue, Stack , Priority Queue คืออะไร แตกต่างกันอย่างไร

ถ้าให้เจ้าของบทความอธิบายแบบสั้นที่สุด คงจะได้ว่า
ทั้ง Queue, Stack , Priority Queue ต่างก็เป็น Data Structure อย่างหนึ่ง ทั้ง 3 มี 2 ฟังค์ชั่นร่วมกันคือ

1. push : นำข้อมูลใส่ Data Structure
2. pop : นำ”ข้อมูลตัวแรกสุด” ออกจาก Data Structure

คำถามสำคัญคือ ”ข้อมูลตัวแรกสุด” หมายถึงอะไร โดย

Queue : ข้อมูลตัวแรกที่ถูกใส่ , Stack :ข้อมูลตัวสุดท้ายที่ถูกใส่ และ Priority Queue : ข้อมูลที่มีค่ามากที่สุด

ถ้ายกตัวอย่าง Queue เราคงจะนึกถึงเวลาที่เราต่อแถวซื้อข้าวเที่ยงในมหาลัย คนที่มาก่อนย่อมได้ก่อน (first in first out)

Stack คงจะคิดถึง การเข้าลิฟท์ สังเกตว่า คนสุดท้ายที่ขึ้น จะออกมาได้ก่อน (first in last out)

Priority Queue สามารถคิดถึงเวลาไปขึ้น BTS จะมีที่นั่งพิเศษสำหรับผู้หญิง และคนชราอยู่ แน่นอนว่า

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

TL;NR

1. 8 Puzzle แก้ไขด้วย search algorithm
2. BFS ใช้ queue , DFS ใช้ stack และ A* ใช้ priority queue
3. BFS คำตอบที่ได้จะเป็นคำตอบที่ดีที่สุดเสมอ(หมายถึง Costต่ำที่สุด) , DFS อาจจะได้คำตอบที่ดีที่สุดหรือไม่ก็ได้ และ A* จะได้คำตอบที่ดีที่สุดไหม ขึ้นกับ heuristic function ที่เราเลือกใช้

0.Utility Method & Class

GOAL เป็นการกำหนด State สุดท้ายที่เราต้องการจะไปถึง
หลายคนอาจแย้งว่าทำไมต้องเป็น String จะมีคำตอบในบทความ
‘0' หมายถึงขอบกระดานที่ไม่สามารถ Access ได ้เขียนเพื่อไม่ให้เกิดเข้าถึง out of bounds โดยไม่ได้ตั้งใจ

INITIAL เป็นการกำหนด State เริ่มต้น
จริงๆสามารถสร้างด้วยการสุ่มได้ แต่มีความเป็นไปได้ที่จะสุ่มมาเจอปัญหาที่ไม่สามารถแก้ได้ (ไม่ใช่ 8 Puzzle ทุกปัญหาสามารถแก้ได้) การจะเช็คว่าเป็นปัญหาที่แก้ได้หรือไม่ได้ อาจจะเกินขอบเขตของบทความนี้ แต่ถ้ามีโอกาสจะนำมาเล่าให้ฟังต่อไป

list_to_string() , string_to_list() เป็น ฟังค์ชั่นที่ใช้แปลงจาก State ในรูปแบบ List เป็น String และกลับกัน โดย string_to_list(list_to_string(c)) = c

ที่ต้องมี เพราะเวลาเลื่อนช่องว่าง การทำงานบน List ย่อมสะดวกกว่า ในทางกลับกัน การเปรียบเทียบระหว่าง 2 State ว่าเหมือนกันหรือไม่ การทำเป็น string สามารถทำได้สะดวกกว่า เพราะสามารถใช้ == ได้เลย

a == b โดย ที่ a และ b เป็น List มีความหมายว่า ถ้า a เป็นตัวเดียวกับ b จะ return True ซึ่งคำว่า “เป็นตัวเดียวกัน” ในที่นี้ หมายถึง ชี้ไปยังตำแหน่งของข้อมูล(Address) เดียวกัน

Ps. 3 Method บนนี้ เจ้าของโพสต์ไม่ได้เขียนเองนะเออ

แน่นอนว่า State ใหม่ของ 8 Puzzle เกิดขึ้นจากการสลับตำแหน่ง ‘e’ (ซึ่งหมายถึงตำแหน่งว่าง) กับอีกตำแหน่งหนึ่ง เพื่อความสะดวก จึงมี Function swapElement รับ State 1 State และพิกัดที่ต้องการสลับตำแหน่ง แล้ว return เป็น State ที่สลับตำแหน่งแล้ว

น่าสนใจที่ _rows = [x[:] for x in rows] มันหมายความว่าอย่างไร ถ้า log มาดู [x[:] for x in rows] กับ rows ก็คือตัวเดียวกัน ทำไมต้องทำให้ลำบากด้วยหล่ะ

เพราะว่าการส่ง List และ Object ใดๆของ Python เข้าสู่ Method จะเกิดสิ่งที่เรียกว่า “Pass by Reference” หมายถึง การแก้ไขค่าใน List ใดๆ จะส่งผลต่อ List ที่อยู่ข้างนอกMethodด้วย ซึ่งเป็นสิ่งที่ไม่ต้องการ การใช้ _x = x[:] ถือเป็นตัวอย่างที่ดีของการ Pass by Reference

Class State

Class State เป็น Class ที่เราจะค้นหาใน DFS,BFS หรือจะเป็น A* ก็ตาม สังเกตว่าสามารถใช้ Class ร่วมกันได้เลย

โดย rows หมายถึง หน้าตาของ ตาราง 3x3 ของเราในปัจจุบัน ว่าตอนนี้มีหน้าตาเป็นยังไง oldState หมายถึง ที่ผ่านมาก่อนจะมาถึงตารางนี้ จากตารางแรกสุดต้องทำยังไงมั้ง จะเลื่อน ‘e’ ไปข้างบนสามครั้ง ซ้ายสองครั้งก็ว่าไป

น่าจะมีคำถามว่า __lt__ หมายถึงอะไร ซึ่งจริงๆก็ไม่ได้ใช้ประโยชน์จริงๆหรอก แต่มันเป็นบัคใน library heapq ที่จะกล่าวถึงใน A* โดยถ้าไม่มีมันจะงอแง รันไม่ได้เลย

ก็จบลงแล้วสำหรับพวก Utility Method มาถึงส่วนสำคัญละครับ

1. Breadth First Search (BFS)

1  procedure BFS(G, root) is
2      let Q be a queue
3      label root as discovered
4      Q.enqueue(root)
5      while Q is not empty do
6          v := Q.dequeue()
7          if v is the goal then
8              return v
9          for all edges from v to w in G.adjacentEdges(v) do
10             if w is not labeled as discovered then
11                 label w as discovered
12                 w.parent := v
13                 Q.enqueue(w)

เมื่ออิมพลีเมนท์ ตาม Pseudocode จาก wikipedia

rows = string_to_list(INITIAL)
bfsArray = [State(rows)] # 2,3,4
beforeState = []

#2,3,4 บอกว่า ให้สร้าง queue Q ซึ่งใน Python List สามารถใช้ในฐานะของ queue ได้เลย และนำ root อันหมายถึง State แรกสุดไปใส่ใน Q ที่สร้างขึ้น

โดย beforeState เป็นส่วนที่ใช้สำหรับ Check ว่าเราเคยทำ State นั้นไปยัง ถ้าเคยทำแล้ว เราไม่ควรจะสนใจ (เพราะทำ Stateแบบเดิม ผลลัพท์ย่อมได้แบบเดิม)

(หน้าตาของ beforeState เป็น State.rows นะ)

หลายคนเจออันนี้ช๊อคแน่นอน แต่ลองจริงๆมันเข้าใจได้ค่อนข้างง่ายเลย

#6,7,8 บอกว่า หยิบ v (ตัวแรกสุด) ออกจาก Q เมื่อ v เป็น state ที่เราต้องการแล้ว ให้ return เลย ซึ่งตรงกับ Code ส่วนที่ 1

#9,10,11,12 บอกว่า ทุก Edge ที่สามารถสร้างได้ ซึ่งในที่นี้ของ 8 Puzzle คือ การสลับช่อง ‘e’ กับช่อง ซ้าย ขวา บน ล่าง โดยที่ Edge นั้นยังไม่เคยทำ(ส่วนนี้เจ้าของโพสต์เขียนในส่วนที่ 1 แทน) ให้สร้าง State ใหม่ ไปใส่ท้ายของคิว

#5 บอกให้รันไปจน Q ว่าง หรือ เจอคำตอบแล้ว สามารถเขียนโค๊ตได้ตามภาพเลย โดยผลลัพท์ของการรัน ควรจะได้

โดย [‘d’,’l’,…] เป็นวิธีการขยับ ‘e’ อย่าง ขยับ ‘e’ ไปข้างล่าง 1 ครั้ง ซ้าย1 ครั้ง ขึ้น1 ครั้ง ,…

โดยใช้เวลาไป 0.1093 seconds

1.5 BFS Animation

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

Queue มี 0 อยู่ ต้องการหาเส้นทางจาก 0 ไป 5

1. นำ State 0 ออกจาก Queue
2. ตรวจสอบว่า เป็น State 5 หรือไม่
3. ดูว่า จาก State 0 ไปทางไหนได้บ้าง ในที่นี้คือ State 1, State 2
4. นำ State 1, State 2 เข้า Queue

จากนั้นนำ State 2 ออกจาก Queue แล้วทำซ้ำ 1–4 จนกว่าจะเจอ Stage 5 ถือว่าจบการทำงาน

2. Depth-first search (DFS)

procedure DFS_iterative(G, v) is
    let S be a stack
    S.push(v)
    while S is not empty do
        v = S.pop()
        if v is not labeled as discovered then
            label v as discovered
            for all edges from v to w in G.adjacentEdges(v) do 
                S.push(w)

สังเกตว่า Pseudocode แทบจะเหมือนกับ Breadth First Search ทุกประการเลย แตกต่างกันแค่ 2 จุดเท่านั้น
1.DFS ใช้ Stack ซึ่ง BFS จะใช้ queue

2.BFS จะหยุดทันทีที่ไปถึง State ซึ่งเป็นคำตอบ แต่ DFS จะทำจนกว่าจะใน Stack เท่านั้นเพื่อหาคำตอบที่ดีที่สุด

เพราะว่าเส้นทางที่ Breadth First Search เจอ จะเป็นเส้นทางที่ Cost น้อยที่สุดเสมอ

เพื่อให้เข้าใจว่า ทั้ง DFS และ BFS โค๊ตใกล้เคียงกันมาก ผู้เขียนบทความจึงขอยก Code ของ BFS มาแก้เป็น DFS เลย

ในเมื่อ List ใน Python นับเป็นทั้ง queue และ stack โค๊ตนี้จึงเหมือนกับข้างบนเลย

ถ้าลองเทียบ Function นี้กับข้างบน จะเห็นว่า ต่างกันแค่ตอนที่ pop State ออกมา DFS จะ pop ตัวสุดท้ายของ List ซึ่งต่างกับ BFS ซึ่ง pop ตัวแรกสุด

ในที่นี้ ผมจะไม่ให้ DFS หาคำตอบที่ดีที่สุด แต่เป็นเจอคำตอบอะไรก็เอามาให้เลย

สังเกตว่า ถ้าเราใช้แค่คำตอบแรกที่ได้เหมือนกับ BFS คำตอบจะเป็นคำตอบที่แย่มาก เพราะมีโอกาสสูงที่จะเดินเข้าเขาวงกตไปแล้วเดินวนอยู่ในนั้น การทำงานจึงช้ากว่าด้วย เพราะเดินวนอยู่ในวงกตนั่นหล่ะ โดยเราอาจจะใช้ Humen Sense ช่วย อาจจะเป็น ถ้า Cost เกิน 10 ให้เลิกพิจารณา Node นั้นไปเลย หรือ ถ้า Cost มากกว่าจำนวนช่องที่ถูก 2เท่า ให้พิจารณา Nodeนั้น

3. A* search algorithm

มาถึง algorithm ที่เราจะใช้แก้ปัญหาในข้อนี้กัน “ทำไมถึงเราต้องเดินไปข้างหน้าโดยไม่คิดอย่าง DFS “, “ทำไมถึงเราต้องคำนวณผลลัพท์ในทุกๆแบบ ทั้งๆที่ในผลลัพท์ทุกๆแบบนั้น มีผลลัพท์ส่วนใหญ่ก็ไม่ใช่ทางที่เราต้องการทั้งนั้น อย่าง BFS”
จะดีกว่าไหม ถ้าเราจะเลือกทำใน State ที่มีโอกาสไปถึงคำตอบที่สุดเท่านั้น

それが A* search algorithm 「สิ่งนั้นหล่ะ คือ A* search algorithm」

ซึ่งตรงนี้ ผมไม่เจอ Pseudocode ที่ดูอ่านง่ายๆเลย ฉะนั้นขออนุญาติเขียนเองให้อ่านง่าย

1  procedure A*(G, root) is
2      let Q be a priorityQueue that Sorted by f-score
3      label root as discovered
4      Q.enqueue(root)
5      while Q is not empty do
6          v := Q.dequeue()
7          if v is the goal then
8              return v
9          for all edges from v to w in G.adjacentEdges(v) do
10             if w is not labeled as discovered then
11                 label w as discovered
12                 w.parent := v
13                 Q.enqueue(w)

เห็นแล้วคุ้นๆกับ BFS ไหมครับ จริงๆมันแทบจะเป็นตัวเดียวกันเลย แค่เปลี่ยน Data Structure จาก Queue เป็น Priority Queue นั่นเองครับ

ปัญหาก็คือ f-score คืออะไร

f(x) = g(x) + h(x)

g(x) หมายถึง Cost Function ซึ่งอธิบายอย่างชัดเจนแล้วข้างบน ที่น่าสนใจคือ h(x) heuristic function ถ้าอธิบายให้เข้าใจง่ายๆ จะเป็น State นั้นเข้าใกล้คำตอบแค่ไหน อย่างใน 8-Puzzle อาจจะเป็น “Goal , State ต่างกันกี่ช่อง” หรือ “ถ้ายอมให้เลื่อนทับช่องได้ จะมี Cost เท่าไหร่ ”

สำคัญคือ ถ้า heuristic function ถ้าเลือกมาไม่ดี เราจะไม่ได้คำตอบที่ดีที่สุด ซึ่งการพิสูจน์เรื่องนี้ หรือการเลือก heuristic function ต้องขอยกไว้ในโอกาสหน้า ซึ่งในบทความนี้ จะใช้ heuristic function เป็น “Goal , State ต่างกันกี่ช่อง”

ถ้า Implement Priority Queue เอง น่าจะเป็นเรื่องใหญ่ไปนิดนึง จึงเลือกใช้ heapq ที่เป็น Priority Queue ตัวนึง

1. heapq.heappush(list , (value ,object) )
2. heapq.heappop(list)

ขั้นตอน #1 ทำเหมือนกับ DFS และ BFS โดย heapq ใช้ list ธรรมดาได้เลย

ถ้าเปรียบเทียบกับทั้ง DFS และ BFS สังเกตว่า Code หน้าตาใกล้เคียงกันมาก คือการเริ่มจาก pop จาก Data Structure -> Check ว่าเป็น Goal ไหม -> นำกลับเข้า Data Structure แค่ A* ใช้ Data Structure เป็น Priority Queue

เขาถึงบอกว่าให้วางแผนก่อนลงมือทำอะไร

จากผลการ Run เห็นได้ชัดว่า เวลาที่ใช้ลดลงอย่างมาก สร้างแค่ไม่กี่ State ก็สามารถไปถึงได้แล้ว

สรุปแบบเข้าใจง่าย เอ้ะ หรือจะยากกว่าเดิมฟระเนี่ย

Display

คำตอบเป็น [‘d’,’l’,…] คงไม่ดีเท่าไหร่ในการแสดงผล ซึ่งการ log data ตาม Command สามารถโค๊ดดิ้งแบบตรงไปตรงมาได้ดังภาพ เพื่อความสวยงาม สามารถใช้ Recursive เพื่อแก้ปัญหานี้ได้

ดูดีกว่า [‘d’,’l’,…] แน่ๆ

ถ้าอ่าน Medium แล้วยังงงๆ อยากจะ log ค่าดู สามารถเปิด Colab ของเจ้าของบทความดูประกอบได้ที่ https://colab.research.google.com/drive/15AUBVqwhgnL7TfH0EzFD4egjbyH_HNmM

PS.ถ้าใครคิดว่า ทำไมชื่อ Medium มันยังกับเป็น light novel เรื่องนึงชื่อว่า แมลง,ลูกตา และ ตุ๊กตาหมี จะบอกว่า ตั้งมาล้อกับเรื่องนั้นนี่ละ

References

https://en.wikipedia.org/wiki/Breadth-first_search

https://en.wikipedia.org/wiki/Depth-first_search

https://en.wikipedia.org/wiki/A*_search_algorithm

simpleai-team/simpleai