Tic-Tac-Toe 게임 제작 (2/4) - alpha–beta pruning

Tic-Tac-Toe와 같은 단순한 게임의 경우 minimax 알고리즘을 사용해도 속도에 그다지 민감하지 않지만

다른게임의 경우 속도가 너무 느려지므로 최적화 처리를 해야한다.

그 래서  alpha-beta pruning를 사용하여 최적화 하였다.

 

Alpha-beta pruning(알파-베타 가지치기)는 미니맥스 알고리즘(Minimax algorithm)과 함께 사용되는 게임 트리 탐색 알고리즘이다. 주로 체스, 오셀로, 틱택토 등의 턴 기반 보드 게임을 포함한 다양한 게임에서 최적의 수를 계산하기 위해 사용된다.

Alpha-beta pruning은 미니맥스 알고리즘의 성능을 향상시키기 위해 개발되었다. 미니맥스 알고리즘은 게임 트리를 완전히 탐색하여 모든 가능한 움직임을 고려하지만 이것은 많은 게임 상황에서 매우 비실용적일 수 있으며, 계산 복잡성이 지나치게 높을 수 있다.

Alpha-beta pruning은 게임 트리의 탐색을 중지하거나 일부 노드를 스킵함으로써 계산 시간을 크게 절약한다. 이것은 최소한의 계산만으로도 최선의 움직임을 찾을 수 있게 해준다. 알파와 베타라는 두 개의 값, 일반적으로 부모 노드에서 현재 노드로 이동할 때 알파(α)와 현재 노드에서 부모 노드로 이동할 때 베타(β)라는 값으로 표시된다.

<알파-베타 가지치기의 작동 방식>

1. 미니맥스 알고리즘과 마찬가지로 게임 트리를 깊이 우선 탐색.
2. 최대 플레이어 노드(현재 플레이어가 최대인 노드)에서 시작하고, 가능한 모든 자식 노드를 탐색. 이 때 알파 값을 최대로 업데이트.
3. 최소 플레이어 노드(상대 플레이어)로 이동하고, 가능한 모든 자식 노드를 탐색. 이 때 베타 값을 최소로 업데이트.
4. 알파 값과 베타 값 사이에 관계를 검사하여 가지치기를 수행. 만약 알파가 베타보다 크거나 같으면 현재 노드의 형제 노드를 스킵.
5. 이 과정을 루트 노드까지 반복하며 최선의 움직임을 결정.

# Tic Tac Toe (2/4)
# Created by netcanis on 2023/09/09.
#
# Minimax
# Alpha–beta pruning


import tkinter as tk
import random
from tkinter import messagebox

NUM_ITEMS = 9
PLAYER = 1
AI = -1

class TTT:
    def __init__(self):
        self.window = tk.Tk()
        self.window.title("TTT")
        
        self.board = [[0 for _ in range(3)] for _ in range(3)]
        self.buttons = [[None for _ in range(3)] for _ in range(3)]
        
        self.sequence = 0
        
        for row in range(3):
            for col in range(3):
                self.buttons[row][col] = tk.Button(
                    self.window,
                    text=' ',
                    font=("Helvetica", 24),
                    height=1,
                    width=1,
                    command=lambda r=row, c=col: self.make_human_move(r, c),
                )
                self.buttons[row][col].grid(row=row, column=col)
        
    def find_empty_cells(self):
        return [(row, col) for row in range(3) for col in range(3) if self.board[row][col] == 0]
    
    def check_winner(self, player):
        for row in self.board:
            if all(cell == player for cell in row):
                return True
        for col in range(3):
            if all(self.board[row][col] == player for row in range(3)):
                return True
        if all(self.board[i][i] == player for i in range(3)) or all(self.board[i][2 - i] == player for i in range(3)):
            return True
        return False
    
    def is_board_full(self):
        return all(cell != 0 for row in self.board for cell in row)
    
    def updateBoardUI(self, row, col, turn_player):
        self.buttons[row][col]["text"] = 'X' if turn_player == PLAYER else 'O'
        self.buttons[row][col]["state"] = "disabled"
        self.window.update()
        
    def make_human_move(self, row, col):
        if self.board[row][col] == 0:
            self.board[row][col] = PLAYER
            self.updateBoardUI(row, col, PLAYER)
            self.sequence += 1
            
            if self.check_winner(PLAYER):
                messagebox.showinfo("Game Over", "Player wins!")
                self.window.quit()
            
            if self.is_board_full():
                messagebox.showinfo("Game Over", "It's a draw!")
                self.window.quit()
            
            self.make_computer_move()
    
    def make_computer_move(self):
        best_move = self.find_best_move()
        if best_move is not None:
            row, col = best_move
            self.board[row][col] = AI
            self.updateBoardUI(row, col, AI)
            self.sequence += 1
            
            if self.check_winner(AI):
                messagebox.showinfo("Game Over", "AI wins!")
                self.window.quit()

            if self.is_board_full():
                messagebox.showinfo("Game Over", "It's a draw!")
                self.window.quit()
    
    def find_best_move(self):
        if self.sequence <= 1:
            return random.choice(self.find_empty_cells())
        
        alpha = -float('inf')
        beta = float('inf')
        best_move = None
        best_score = -float('inf')
        
        for row, col in self.find_empty_cells():
            self.board[row][col] = AI
            score = self.minimax(0, False, alpha, beta)
            self.board[row][col] = 0
            
            if score > best_score:
                best_score = score
                best_move = (row, col)
        
        return best_move
    
    def minimax(self, depth, is_maximizing, alpha, beta):
        if self.check_winner(AI):
            return (NUM_ITEMS + 1 - depth)
                    
        if self.check_winner(PLAYER):
            return -(NUM_ITEMS + 1 - depth)

        if self.is_board_full():
            return 0
        
        if is_maximizing:
            best_score = -float('inf')
            for row, col in self.find_empty_cells():
                self.board[row][col] = AI
                score = self.minimax(depth + 1, False, alpha, beta)
                self.board[row][col] = 0
                best_score = max(best_score, score)
                alpha = max(alpha, best_score)
                if beta <= alpha:
                    break
            return best_score
        else:
            best_score = float('inf')
            for row, col in self.find_empty_cells():
                self.board[row][col] = PLAYER
                score = self.minimax(depth + 1, True, alpha, beta)
                self.board[row][col] = 0
                best_score = min(best_score, score)
                beta = min(beta, best_score)
                if beta <= alpha:
                    break
            return best_score

    def run(self):
        self.window.mainloop()

if __name__ == "__main__":
    game = TTT()
    game.run()

 

2023.09.12 - [AI,ML, Algorithm] - Tic-Tac-Toe 게임 제작 (1/4) - minimax

2023.09.12 - [AI,ML, Algorithm] - Tic-Tac-Toe 게임 제작 (2/4) - alpha–beta pruning

2023.09.12 - [AI,ML, Algorithm] - Tic-Tac-Toe 게임 제작 (3/4) - 머신러닝 훈련 데이터 생성

2023.09.12 - [AI,ML, Algorithm] - Tic-Tac-Toe 게임 제작 (4/4) - 머신러닝을 이용한 게임 구현