신경망 알고리즘을 이용하여 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) - 머신러닝을 이용한 게임 구현
'개발 > AI,ML,ALGORITHM' 카테고리의 다른 글
Tic-Tac-Toe 게임 제작 (3/4) - 머신러닝 훈련 데이터 생성 (0) | 2023.09.12 |
---|---|
Tic-Tac-Toe 게임 제작 (2/4) - alpha–beta pruning (0) | 2023.09.12 |
Simple Neural Network XOR (0) | 2023.08.29 |
SARSA (0) | 2023.08.28 |
Q-learning (0) | 2023.08.28 |