Tic-Tac-Toe 게임 제작 (1/4) - minimax

신경망 알고리즘을 이용하여 tic-tac-toe게임을 구현해 보고자 한다. 

전체 4회에 걸쳐 업로드 할 예정이며 순서는 다음과 같다.

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) - 머신러닝을 이용한 게임 구현

 

아래 코드는 AI의 수를 계산하기 위해 minimax알고리즘을 사용하였다.

Minimax는 게임 이론 및 인공 지능 분야에서 사용되는 의사결정 알고리즘 중 하나이다. 주로 두 플레이어 간의 게임에서 최적의 움직임을 찾는 데 사용된다. Minimax 알고리즘은 상대방과 자신의 이익 또는 손해를 고려하여 다음 움직임을 결정하는 방법을 제공한다.

<Minimax 알고리즘의 작동 방식>

1. 게임 트리 생성: 현재 게임 상태에서 가능한 모든 움직임을 고려하여 게임 트리를 생성한다. 트리의 각 레벨은 게임의 한 턴을 나타내고, 각 노드는 해당 턴에서 가능한 상태를 나타낸다.

2. 평가 함수: 게임 트리의 말단 노드(게임 종료 상태)에 도달하면 각 상태를 평가한다. 이 평가는 게임에서 어떤 플레이어가 이길 확률 또는 게임 상태의 가치를 나타내는 값이다.

3. Minimax 알고리즘: 게임 트리를 위에서 아래로 (루트에서 리프로) 탐색하면서, 각 레벨에서 최대화(Maximize) 노드와 최소화(Minimize) 노드를 번갈아 가며 선택한다. 최대화 노드에서는 가능한 움직임 중에서 가장 큰 가치를 선택하고, 최소화 노드에서는 가능한 움직임 중에서 가장 작은 가치를 선택한다.

4. 최선의 움직임 결정: 루트 노드까지 도달하면 최종적으로 최선의 움직임을 결정한다. 최대화 노드에서 최대 가치를 가진 움직임이 최적의 움직임이 된다.

# Tic Tac Toe (1/4)
# Created by netcanis on 2023/09/09.
#
# Minimax


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())
        
        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)
            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):
        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)
                self.board[row][col] = 0
                best_score = max(best_score, score)
            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)
                self.board[row][col] = 0
                best_score = min(best_score, score)
            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) - 머신러닝을 이용한 게임 구현