Gomoku(Five in a Row, Omok) (2/5) - 속도 최적화 1차 (minimax 속도 개선)
개발/AI,ML,ALGORITHM 2023. 10. 27. 11:18반응형
minimax 속도를 개선하기 위해 다음과 같은 변경사항을 적용하였다.
1. 빈 자리를 검색할 때, 이미 돌이 놓여진 위치 주변에 있는 빈 자리만 반환.
2. AI가 돌을 놓았을 때, 승리 조건이 만족되는 위치라면 즉시 돌을 놓는다.
3. 플레이어가 돌을 놓았을 때, 승리 조건이 만족되는 위치라면 AI가 그 위치에 돌을 즉시 놓는다.
1번 빈 자리 검색 시 아래 그림과 같이 돌이 놓여진 주변 빈자리만 검색하여 반환되도록 한다.
반환된 빈 자리는 불필요한 트리 탐색을 줄여 속도가 개선된다.
#
# FIAR
# Created by netcanis on 2023/10/07.
#
# minimax
# alpha beta pruning
# 속도 개선
import pygame
import random
import numpy as np
import sys
BOARD_SIZE = 9 # (7,9,13,15,19)
CELL_SIZE = 40
MARGIN = 20
CLICK_RADIUS = CELL_SIZE // 2
BLACK = (0, 0, 0)
WHITE = (255, 255, 255)
RED = (255, 0, 0)
GRAY = (100, 100, 100)
NUM_ITEMS = (BOARD_SIZE * BOARD_SIZE)
PLAYER = 1
AI = -1
DIFFICULTY_LEVEL = 3
class FIAR:
def __init__(self):
self.init_game()
def init_game(self):
pygame.init()
pygame.display.set_caption("FIAR")
w = (BOARD_SIZE-1) * CELL_SIZE + 2 * MARGIN
h = (BOARD_SIZE-1) * CELL_SIZE + 2 * MARGIN
self.screen = pygame.display.set_mode((w, h))
self.font = pygame.font.Font(None, CELL_SIZE-4)
def reset_game(self):
self.board = np.zeros((BOARD_SIZE, BOARD_SIZE), dtype=int)
self.sequences = np.zeros((BOARD_SIZE, BOARD_SIZE), dtype=int)
self.sequence = 0
self.game_over = False
self.turn_player = PLAYER
self.draw_board(self.screen)
pygame.display.flip()
def find_empty_cells(self):
empty_cells = []
for row in range(BOARD_SIZE):
for col in range(BOARD_SIZE):
if self.board[row][col] == 0:
empty_cells.append((row, col))
random.shuffle(empty_cells)
return empty_cells
# 수가 놓여진 자리의 주변 빈 자리만 반환
def find_adjacent_empty_cells(self):
empty_cells = []
for row, col in self.find_empty_cells():
for dr in [-1, 0, 1]:
for dc in [-1, 0, 1]:
new_row, new_col = row + dr, col + dc
if 0 <= new_row < BOARD_SIZE and 0 <= new_col < BOARD_SIZE and self.board[new_row][new_col] != 0:
empty_cells.append((row, col))
break
return empty_cells
def check_winner(self, board, row, col):
def check_direction(dx, dy):
count = 1
r, c = row + dx, col + dy
while 0 <= r < len(board) and 0 <= c < len(board[0]) and board[r][c] == board[row][col]:
count += 1
r += dx
c += dy
return count
directions = [(0, 1), (1, 0), (1, 1), (-1, 1)]
for dx, dy in directions:
count1 = check_direction(dx, dy)
count2 = check_direction(-dx, -dy)
total_count = count1 + count2 - 1
if total_count == 5:
return True
return False
def is_board_full(self, board):
return all(cell != 0 for row in board for cell in row)
def random_move(self, player):
if self.game_over:
return -1, -1
row, col = random.choice(self.find_adjacent_empty_cells())
self.make_move(row, col, player)
return row, col
def minimax_move(self, player):
if self.game_over:
return -1, -1
row, col = self.find_best_move(player)
self.make_move(row, col, player)
return row, col
def make_move(self, row, col, player):
if self.board[row][col] == 0:
self.board[row][col] = player
self.sequence += 1
self.sequences[row][col] = self.sequence
print(f"[{self.sequence}] <{player}> {row},{col}")
if self.check_winner(self.board, row, col):
self.game_over = True
elif self.is_board_full(self.board):
self.game_over = True
self.turn_player = 0
else:
self.turn_player *= -1
def minimax(self, depth, is_maximizing, alpha, beta, row2, col2):
if self.is_board_full(self.board):
return 0
if is_maximizing:
if self.check_winner(self.board, row2, col2):
return -(NUM_ITEMS - depth + 1)
else:
if self.check_winner(self.board, row2, col2):
return (NUM_ITEMS - depth + 1)
if depth >= DIFFICULTY_LEVEL:
return 0
if is_maximizing:# AI
best_score = -float('inf')
for row, col in self.find_adjacent_empty_cells():
self.board[row][col] = AI
score = self.minimax(depth + 1, False, alpha, beta, row, col)
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_adjacent_empty_cells():
self.board[row][col] = PLAYER
score = self.minimax(depth + 1, True, alpha, beta, row, col)
self.board[row][col] = 0
best_score = min(best_score, score)
beta = min(beta, best_score)
if beta <= alpha:
break
return best_score
# 아래 우선순위에 따라 즉시 처리할 자리는 minimax 알고리즘 없이 즉시 수를 놓아 속도 개선
# 1.만약 AI가 놓으면 게임을 이기는 자리라면 즉시 수를 놓는다.
# 2.만약 Player가 놓으면 게임을 이기는 자리라면 AI는 그 곳에 수는 놓는다.
def make_optimal_move(self, player):
# 0. The first one is random.
if self.sequence == 0:
row = BOARD_SIZE // 2 + random.randint(-2, 2)
col = BOARD_SIZE // 2 + random.randint(-2, 2)
return (row, col)
empty_cells = self.find_adjacent_empty_cells()
# 1. ai turn: 5
for row, col in empty_cells:
self.board[row][col] = player
if self.check_winner(self.board, row, col):
self.board[row][col] = 0
return (row, col)
self.board[row][col] = 0
# 2. player turn: 5
for row, col in empty_cells:
self.board[row][col] = -player
if self.check_winner(self.board, row, col):
self.board[row][col] = 0
return (row, col)
self.board[row][col] = 0
return None
def find_best_move(self, player):
print(f"[{self.sequence+1}] <{player}> Calculating...")
optimal_move = self.make_optimal_move(player)
if optimal_move != None:
return optimal_move
alpha = -float('inf')
beta = float('inf')
best_move = None
best_score = -float('inf') if player == AI else float('inf')
empty_cells = self.find_adjacent_empty_cells()
for index, (row, col) in enumerate(empty_cells):
self.board[row][col] = player
is_maximizing = False if player == AI else True
score = self.minimax(0, is_maximizing, alpha, beta, row, col)
self.board[row][col] = 0
if (player == AI and score > best_score) or (player == PLAYER and score < best_score):
best_score = score
best_move = (row, col)
percentage = (index / len(empty_cells)) * 100
print(f" [{percentage:.1f}%] <{player}> {row},{col} -> {score}")
return best_move
def show_message(self, message, is_exit=False):
popup = True
while popup:
for event in pygame.event.get():
if event.type == pygame.QUIT:
pygame.quit()
sys.exit()
if event.type == pygame.KEYDOWN:
if is_exit:
if event.key == pygame.K_y:
self.reset_game()
popup = False
return
elif event.key == pygame.K_n:
pygame.quit()
sys.exit()
else:
popup = False
break
text_lines = message.split('\n')
for i, line in enumerate(text_lines):
text = self.font.render(line, True, (128, 0, 128))
text_rect = text.get_rect(topleft=(20, 20 + i * 20))
self.screen.blit(text, text_rect)
pygame.display.flip()
def draw_board(self, screen):
screen.fill(GRAY)
for row in range(BOARD_SIZE):# draw horizontal lines
pygame.draw.line(screen, BLACK,
(0 * CELL_SIZE + MARGIN, row * CELL_SIZE + MARGIN),
((BOARD_SIZE-1) * CELL_SIZE + MARGIN, row * CELL_SIZE + MARGIN),
1)
for col in range(BOARD_SIZE):# draw vertical lines
if row == 0:
pygame.draw.line(screen, BLACK,
(col * CELL_SIZE + MARGIN, 0 * CELL_SIZE + MARGIN),
(col * CELL_SIZE + MARGIN, (BOARD_SIZE-1) * CELL_SIZE + MARGIN),
1)
x = col * CELL_SIZE + MARGIN
y = row * CELL_SIZE + MARGIN
if self.board[row][col] == PLAYER:
pygame.draw.circle(screen, BLACK, (x, y), CLICK_RADIUS)
elif self.board[row][col] == AI:
pygame.draw.circle(screen, WHITE, (x, y), CLICK_RADIUS)
seq_no = self.sequences[row][col]
if seq_no != 0:
if seq_no == self.sequence:
pygame.draw.circle(screen, RED, (x, y), CLICK_RADIUS+1, 1)
color = WHITE if self.board[row][col] == PLAYER else BLACK
text = self.font.render(f"{seq_no}", True, color)
text_rect = text.get_rect(center=(x, y))
screen.blit(text, text_rect)
def handle_events(self):
for event in pygame.event.get():
if event.type == pygame.QUIT:
self.game_over = True
elif event.type == pygame.MOUSEBUTTONDOWN and not self.game_over and self.turn_player == PLAYER:
x, y = pygame.mouse.get_pos()
row = int(round((y - MARGIN) / CELL_SIZE))
col = int(round((x - MARGIN) / CELL_SIZE))
if 0 <= row < BOARD_SIZE and 0 <= col < BOARD_SIZE and self.board[row][col] == 0:
self.make_move(row, col, self.turn_player)
self.draw_board(self.screen)
pygame.display.flip()
if self.turn_player == AI:
best_move = self.find_best_move(self.turn_player)
if best_move is not None:
row, col = best_move
self.make_move(row, col, self.turn_player)
self.draw_board(self.screen)
pygame.display.flip()
if self.game_over == True:
if self.turn_player == 0:
self.show_message("Game draw!")
else:
self.show_message(f"Game Over!\n{'Player' if self.turn_player == PLAYER else 'AI'} wins!")
if __name__ == "__main__":
game = FIAR()
game.reset_game()
while True:
while not game.game_over:
game.handle_events()
game.show_message("Play Again? (y/n)", is_exit=True)
속도는 다소 빨라지긴 했다.
3x3을 만들면 이미 진 것을 예감한 것인지 AI는 그 때부터 엉뚱한 수를 놓는다.
마치 포기한 것처럼...
2023.10.27 - [AI,ML, Algorithm] - Gomoku(Five in a Row, Omok) (2/5) - 속도 최적화 1차 (minimax 속도 개선)
2023.10.28 - [AI,ML, Algorithm] - Gomoku(Five in a Row, Omok) (3/5) - 속도 최적화 2차 (RANDOM모드 추가)
2023.10.29 - [AI,ML, Algorithm] - Gomoku(Five in a Row, Omok) (4/5) - 훈련 데이터 생성 및 학습
2023.10.29 - [AI,ML, Algorithm] - Gomoku(Five in a Row, Omok) (5/5) - 머신러닝으로 게임 구현
2023.11.03 - [AI,ML, Algorithm] - Gomoku(Five in a Row, Omok) (5/5) - 3x3 체크 추가
반응형
'개발 > AI,ML,ALGORITHM' 카테고리의 다른 글
| Gomoku(Five in a Row, Omok) (4/5) - 훈련 데이터 생성 및 학습 (1) | 2023.10.29 |
|---|---|
| Gomoku(Five in a Row, Omok) (3/5) - 속도 최적화 2차 (RANDOM모드 추가) (1) | 2023.10.28 |
| Gomoku(Five in a Row, Omok) (1/5) - 기본 구현 (minimax, alpha-beta pruning) (0) | 2023.10.27 |
| Tic-Tac-Toe 게임 제작 (4/4) - 머신러닝을 이용한 게임 구현 (0) | 2023.09.12 |
| Tic-Tac-Toe 게임 제작 (3/4) - 머신러닝 훈련 데이터 생성 (0) | 2023.09.12 |
SKY STORY
