DEV Community

ณัฐภณ สีสายคำ
ณัฐภณ สีสายคำ

Posted on

Connect Four AI: A Minimax Approach

#ai #tutorial #python

การที่เราจะเขียน AI ให้สามารถมาเป็นคู่แข่งกับเราในเกมได้ที่เขาเรียกกันว่าบอท(ฺBot)ในจะต้องผ่านการ tainning ต่าง ๆ นานา เพื่อให้สามารถมีความรู้ ความสามารถมากพอที่จะให้บอทมาเป็นคู่ต่อสู้กับเราได้หรือต้องสร้างเงื่อนไขอะไรบางอย่างเพื่อที่จะให้หาทุกวิถึทางเพื่อทำให้สามารถชนะคนได้เกมที่ผมนำมาใช้ในการศึกษาครั้งนี้คือ Connect 4

เกม Connect 4 คือเกมที่ต้องมีผู้เล่น 2 คน ในการเล่น โดยผู้เล่นจะต้องทำยังไงก็ได้ให้หยอดเหรียญที่เป็นสี ๆ เรียงกันได้แก่ แนวตั้ง แนวนอน และแนวเฉียง ในช่องที่มีขนาด 6 * 7 ดังภาพ

Image description

โหลด Library ที่ต้องใช้

ในส่วนของ pygame ใช้สำหรับแสดงภาพเกม เช่น กระดาน, หมาก, แอนิเมชัน และการรับอินพุตจากผู้เล่น

pip install pygame==1.9.3
Enter fullscreen mode Exit fullscreen mode

และ

pip install -r requirements.txt
Enter fullscreen mode Exit fullscreen mode

Algorithm ที่ใช้คือ Minimax และ Alpha-Beta Pruning

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

Alpha-Beta Pruning คือเทคนิคที่ช่วยลดจำนวนการจำลองลง โดยไม่ต้องดูทุกทางเดินหากรู้ว่ามีทางที่ดีสุดอยู่แล้ว

ด้วยความที่สถานการณ์ที่เป็นไปได้มีทั้งหมด 4,531,985,219,092 วิธี ซึ่งทำให้ยากต่อการคำนวณกับโครงสร้างเกม ดังนั้นเจึงใช้ Algorithm ของ Minimax ร่วมกับ Alpha-Beta Pruning

ขั้นตอนที่ 1 การนำเข้า Module และSetting 

from fourInARowGUI import fourInARowGUI as GUI
infinity = float('inf')
Enter fullscreen mode Exit fullscreen mode

เป็นการนำเข้าโมดูลfourInARowGUI.pyซึ่งอยู่ในโฟลเดอร์เดียวกัน ใน Module นี้จะมีฟังก์ชันทั้งหมดที่ใช้จัดการ กราฟิก, อินพุตของผู้เล่น และการแสดงผลเกม

ขั้นตอนที่ 2 สร้างคลาสในการควบคุมเกม 

class Game:
    AI = -1
    PLAYER = 0

def __init__(self, game_board):
    self.current_state = State(0, 0)
    self.turn = self.AI
    self.first = self.turn
    self.board = game_board
Enter fullscreen mode Exit fullscreen mode

โค้ดในส่วนนี้จะเป็นจะเป็นฟังก์ชั่นในการเริ่มเกม การตั้งให้บอทเล่นก่อน และเป็นการเก็บบอร์ดเกมไว้ใช้งานต่ออีกด้วย

def next_turn(self):
    if self.turn == self.AI:
        self.query_AI()
    else:
        self.query_player()
    self.turn = ~self.turn
Enter fullscreen mode Exit fullscreen mode

โค้ดในส่วนนี้เป็นฟังก์ชั่นใช้ในการสลับเทิร์นของผู้เล่นและบอท

column = GUI.getHumanInteraction(self.board)
Enter fullscreen mode Exit fullscreen mode

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

self.current_state = alphabeta_search(self.current_state, self.first, d=7)
Enter fullscreen mode Exit fullscreen mode

โค้ดส่วนนี้ใช้ในการให้บอทนั้นใช้ Minimax และ Alpha-Beta Pruning ในการตัดสินใจในการในการเดินในทางที่ดีที่สุด

ขั้นตอนที่ 3 ตรวจสอบสถานะของเกม 

def __init__(self, ai_position, game_position, depth=0):
        self.ai_position = ai_position
        self.game_position = game_position
        self.depth = depth
Enter fullscreen mode Exit fullscreen mode

โค้ดในส่วนนี้ตรวจสอบว่าในบอร์ดต่างๆ ของบอทในบอร์ดเช่นการลง bitboard ของผู้เล่น, จำนวณ bitboard และความลึกของ tree

ขั้นตอนที่ 4 ระบบการตัดสินใจของบอท 

self.current_state = alphabeta_search(self.current_state, self.first, d=7)
Enter fullscreen mode Exit fullscreen mode

โค้ดในส่วนนี้เป็นการตัดสินใจในการเล่นของบอทที่จะค้นหาที่ดีที่สุด โดยใช้ควบคู่ไปกับ Alpha-Beta Pruning ที่มีระดับความลึก 7 ขั้น

ขั้นตอนที่ 5 ระบบหน้าต่าง GUI ของเกม 

if __name__ == "__main__":
    print("Welcome to Connect Four!")

    GUI.run()
    while True:
        # Set up a blank board data structure.
        game_board = GUI.getNewBoard()
        GUI.drawBoard(game_board)
        GUI.updateDisplay()
        # Start game data structure
        game = Game(game_board)
        while not game.is_game_over():
            game.next_turn()
            print_board(game.current_state)
            GUI.drawBoard(game.board)
            GUI.updateDisplay()

        # Necessary for GUI
        WINNER = '' if game.draw() else GUI.COMPUTER if ~game.turn == -1 else GUI.HUMAN
        GUI.processGameOver(WINNER, game.board)
Enter fullscreen mode Exit fullscreen mode

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

ตัวอย่างเพิ่มเติม

ในส่วนนี้เราจะทำการทดลองระบบเกม Connect 4 ในเครื่องของเราใน visual studio โดยใช้ python เวอร์ชั่น 3.10.9 เพื่อให้ library ทำงานได้ปกติ

ขั้นตอนที่ 1 การนำเข้า Module และSetting

from fourInARowGUI import fourInARowGUI as GUI
infinity = float('inf')
Enter fullscreen mode Exit fullscreen mode

เป็นการนำเข้าโมดูลfourInARowGUI.pyซึ่งอยู่ในโฟลเดอร์เดียวกัน ใน Module นี้จะมีฟังก์ชันทั้งหมดที่ใช้จัดการ กราฟิก, อินพุตของผู้เล่น และการแสดงผลเกม

ขั้นตอนที่ 2 สร้างคลาสในการควบคุมเกม 

class Game:
    AI = -1
    PLAYER = 0

def __init__(self, game_board):
    self.current_state = State(0, 0)
    self.turn = self.AI
    self.first = self.turn
    self.board = game_board
Enter fullscreen mode Exit fullscreen mode

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

def next_turn(self):
    if self.turn == self.AI:
        self.query_AI()
    else:
        self.query_player()
    self.turn = ~self.turn
Enter fullscreen mode Exit fullscreen mode

โค้ดในส่วนนี้เป็นฟังก์ชั่นใช้ในการสลับเทิร์นของผู้เล่นและบอท

column = GUI.getHumanInteraction(self.board)
Enter fullscreen mode Exit fullscreen mode

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

Image description

self.current_state = alphabeta_search(self.current_state, self.first, d=7)
Enter fullscreen mode Exit fullscreen mode

โค้ดส่วนนี้ใช้ในการให้บอทนั้นใช้ Minimax และ Alpha-Beta Pruning ในการตัดสินใจในการในการเดินในทางที่ดีที่สุด

ขั้นตอนที่ 3 ตรวจสอบสถานะของเกม 

def __init__(self, ai_position, game_position, depth=0):
        self.ai_position = ai_position
        self.game_position = game_position
        self.depth = depth
Enter fullscreen mode Exit fullscreen mode

โค้ดในส่วนนี้ตรวจสอบว่าในบอร์ดต่างๆ ของบอทในบอร์ดเช่นการลง bitboard ของผู้เล่น, จำนวณ bitboard และความลึกของ tree

Image description

ขั้นตอนที่ 4 ระบบการตัดสินใจของบอท 

self.current_state = alphabeta_search(self.current_state, self.first, d=7)
Enter fullscreen mode Exit fullscreen mode

โค้ดในส่วนนี้เป็นการตัดสินใจในการเล่นของบอทที่จะค้นหาที่ดีที่สุด โดยใช้ควบคู่ไปกับ Alpha-Beta Pruning ที่มีระดับความลึก 7 ขั้น

Image description

ขั้นตอนที่ 5 ระบบหน้าต่าง GUI ของเกม 

if __name__ == "__main__":
    print("Welcome to Connect Four!")

    GUI.run()
    while True:
        # Set up a blank board data structure.
        game_board = GUI.getNewBoard()
        GUI.drawBoard(game_board)
        GUI.updateDisplay()
        # Start game data structure
    game = Game(game_board)
        while not game.is_game_over():
            game.next_turn()
            print_board(game.current_state)
            GUI.drawBoard(game.board) 


        # Necessary for GUI
        WINNER = '' if game.draw() else GUI.COMPUTER if ~game.turn == -1 else GUI.HUMAN
        GUI.processGameOver(WINNER, game.board)
Enter fullscreen mode Exit fullscreen mode

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

Image description

ผลลัพธ์ที่ได้

Image description

Image description

จาก 2 ภาพนี้เราใช่วิธีเล่นเหมือนเดิมแต่ว่าบอทในภาพที่ 2 จะมีการเล่นที่ต่างจากภาพที่ 1 เล็กน้อย

ตัวอย่างอื่นๆที่เราทำการเล่นให้ชนะ

Image description

Image description

Image description

สรุปผล

จาการที่เราได้ทำการทดลองเล่นเกม Connect 4 แล้วทำให้เห็นว่าบอทนั้นมีความฉลาดเป็นอย่างมากเมื่อไหร่เราลงพลาด บอทก็จะสามารถชนะให้เราได้ทันทีเพราะว่าเส้นทางที่บอทที่ใช้ในการชนะเรามากกว่า 1 เส้นทางโดยใช้ Minimax และ Alpha-Beta Purring ในการหาเส้นทางที่สุดแต่อย่างไรก็ตามเราก็ยังสามารถชนะบอทได้เช่นกันถ้าเราสามารถคิดได้ว่าถ้าเราเลือกเส้นทางที่ดีที่สุดเหมือนกันก็จะเป็นตัดโอกาสให้บอทไม่สามารถชนะหรืออาจจะสามารถก็เป็นได้

Reference

Connect 4 Python game
Rule of Connect 4

Top comments (0)