'alpha-beta pruning'에 해당되는 글 6건

3x3 체크를 위해 아래와 같이 함수를 만들고 플레이어와 AI 둘다 막아보았다.
문제되는 부분이 있다면 댓글로 알려주길 바란다.

# 3x3 체크 
def check3x3(self, row, col):
    def check_direction_with_blank(dx, dy):
        scount = 1 # 같은 색상 갯수 
        bcount = 1 # 빈공간 포함 갯수
        r, c = row + dx, col + dy
        while 0 <= r < len(self.board) and 0 <= c < len(self.board[0]) and (self.board[r][c] == self.board[row][col] or self.board[r][c] == 0):
            bcount += 1
            if self.board[r][c] == self.board[row][col]:
                scount += 1
            r += dx
            c += dy
        return scount, bcount

    self.board[row][col] = self.turn_player
    
    count3x3 = 0
    directions = [(0, 1), (1, 0), (1, 1), (-1, 1)]
    for dx, dy in directions:
        sc1, bc1 = check_direction_with_blank( dx,  dy)
        sc2, bc2 = check_direction_with_blank(-dx, -dy)
        scount = sc1 + sc2 - 1
        bcount = bc1 + bc2 - 1
        if scound == 3 and bcound >= 5:
            count3x3 += 1
    self.board[row][col] = 0
    if check3x3 >= 2:
        return True
    return False
    
    
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:
                if self.check3x3(row, col) == False: # 3x3 체크
                    empty_cells.append((row, col))
    random.shuffle(empty_cells)
    return empty_cells
    
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:
                if self.check3x3(row, col) == True: # 3x3 체크
                    return

                self.make_move(row, col, self.turn_player)
                
    			(이하 생략)

 
 
 
 
 
 
 
2023.10.27 - [AI,ML, Algorithm] - Gomoku(Five in a Row, Omok) (1/5) - 기본 구현 (minimax, alpha-beta pruning)
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 체크 추가
 
 
 

이제 머신러닝으로 게임을 구현해 보자.

학습 데이터가 5만 이상 되어야 하는데 2만개 정도만 학습 시켰다.

최적화 이동 처리 함수와 믹스해서 구현해 보았다.

3x3일 경우 막지 않았다.

나중에 그 부분은 업데이트 하도록 하겠다.

#
# FIAR
# Created by netcanis on 2023/10/29.
#
# minimax
# alpha beta pruning
# 속도 개선 
# 훈련데이터 생성하여 머신러닝.

import pygame
import random
import numpy as np
import sys
import os
import tensorflow as tf
from keras.models import load_model


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_AI = 4

PLAYER_MODE = "MANUAL"
AI_MODE = "ML"

H5_FILE_NAME = "fiar_model.h5"


class FIAR:
    def __init__(self):
        self.init_game()
    
    def init_game(self):
        self.episode = 0
        
        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#random.choice([PLAYER, AI])

        self.draw_board(self.screen)
        pygame.display.flip()
        
        self.model = load_model(H5_FILE_NAME)
        
    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 = []
        empty_cells2 = []
        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:
                        # 수를 놓았을 경우 연결된 수가 3개 이상이고 5개를 놓을 수 있는 자리일 경우만 배열에 추가.
                        self.board[row][col] = self.turn_player
                        c1, c2, _ = self.evaluate_position(self.board, row, col)
                        self.board[row][col] = -self.turn_player
                        c3, c4, _ = self.evaluate_position(self.board, row, col)
                        self.board[row][col] = 0
                        if (c1 >= 3 and c2 >= 5) or (c3 >= 3 and c4 >= 5):
                            empty_cells2.append((row, col))

                        empty_cells.append((row, col))
                        break
                    
        if len(empty_cells2) > 0:
            return empty_cells2
        
        return empty_cells
    
    def evaluate_position(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
        
        def check_direction_with_blank(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] or board[r][c] == 0):
                count += 1
                r += dx
                c += dy
            return count
        
        total_count1 = 0
        total_count2 = 0
        total_score = 0
        directions = [(0, 1), (1, 0), (1, 1), (-1, 1)]
        for dx, dy in directions:
            count1 = check_direction( dx,  dy)
            count2 = check_direction(-dx, -dy)
            dir_count1 = count1 + count2 - 1
            count3 = check_direction_with_blank( dx,  dy)
            count4 = check_direction_with_blank(-dx, -dy)
            dir_count2 = count3 + count4 - 1
            total_count1 = max(total_count1, dir_count1)
            total_count2 = max(total_count2, dir_count2)
            # 각 방향별로 연결된 돌의 수가 3자리 이상이고 5개이상 놓을 수 있는 자리라면 점수를 추가한다.
            # 즉, 연결되는 돌이 교차하는 위치라면 점수가 높게 나온다.
            if dir_count1 == 4 and dir_count2 >= 5:
                total_score += dir_count1 * 4
            elif dir_count1 >= 3 and dir_count2 >= 5:
                total_score += dir_count1 * 2
            elif dir_count1 >= 2 and dir_count2 >= 5:
                total_score += dir_count1
                
        return total_count1, total_count2, total_score
    
    def check_winner(self, board, row, col):
        if board[row][col] == 0:
            return False
        
        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
        
        best_move = None
        best_score = 0
        
        best_move = self.make_optimal_move(player)
        if best_move == None:
            if player == AI:
                empty_cells = self.find_adjacent_empty_cells()
                for row, col in empty_cells: 
                    self.board[row][col] = player
                    s1 = self.evaluate_position(self.board, row, col)[2]
                    if s1 > best_score:
                        best_score = s1
                        best_move = (row, col)
                    self.board[row][col] = -player
                    s2 = self.evaluate_position(self.board, row, col)[2]
                    if s2 > best_score:
                        best_score = s2
                        best_move = (row, col)
                    self.board[row][col] = 0
                
                if best_score == 0:
                    best_move = random.choice(self.find_empty_cells())
            else:
                best_move = random.choice(self.find_empty_cells())
        
        self.make_move(best_move[0], best_move[1], player)
        
        return best_move

    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_AI:
            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
    
    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
        
        # 3. The position that becomes 4 when placed
        for row, col in empty_cells: 
            self.board[row][col] = player
            c1, c2, _ = self.evaluate_position(self.board, row, col)
            self.board[row][col] = -player
            c3, c4, _ = self.evaluate_position(self.board, row, col)
            self.board[row][col] = 0
            if (c1 == 4 and c2 >= 5) or (c3 == 4 and c4 >= 5):
                return (row, col)
            
        # 4. The position that becomes 3 when placed
        for row, col in empty_cells: 
            self.board[row][col] = player
            c1, c2, _ = self.evaluate_position(self.board, row, col)
            self.board[row][col] = -player
            c3, c4, _ = self.evaluate_position(self.board, row, col)
            self.board[row][col] = 0
            if (c1 == 3 and c2 >= 5) or (c3 == 3 and c4 >= 5):
                return (row, col)
            
        return None
        
    def find_best_move(self, player):
        if AI_MODE == "ML":
            optimal_move = self.make_optimal_move(player)
            if optimal_move != None:
                print(f"optimal move! ({optimal_move[0]}, {optimal_move[1]})")
                return optimal_move
            
            move_index = self.predicts(self.board)
            row = move_index // BOARD_SIZE
            col = move_index % BOARD_SIZE
            best_move = (row, col)
            print(f"ML move! ({row}, {col})")
        elif AI_MODE == "RANDOM":
            best_move = self.random_move(player)
        else: # MINIMAX
            print(f"[{self.sequence+1}] <{player}> ...")
            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}")
            
            print(f"    {best_move[0]},{best_move[1]} ({best_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
                        message = ""
                        self.draw_board(self.screen)
                        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!")

    def init_ML(self):
        hidden_layer_count = 3 * NUM_ITEMS
        self.model = tf.keras.Sequential([
            tf.keras.layers.Dense(hidden_layer_count, activation='relu', input_shape=(NUM_ITEMS,)),
            tf.keras.layers.Dense(NUM_ITEMS, activation='softmax')
        ])
        self.model.compile(loss='categorical_crossentropy', optimizer='adam', metrics=['accuracy'])

    def predicts(self, input_data):
        if isinstance(input_data, list):
            input_data = np.array(input_data)
        
        prediction = self.model.predict(input_data.reshape(1, -1))
        sorted_indices = np.argsort(prediction, axis=-1)[:, ::-1]
        index = 0
        for i in sorted_indices[0]:
            if input_data.shape == (NUM_ITEMS,):
                if input_data[i] == 0:
                    index = i
                    break
            elif input_data.shape == (BOARD_SIZE, BOARD_SIZE):
                row = i // BOARD_SIZE
                col = i % BOARD_SIZE
                if input_data[row][col] == 0:
                    index = i
                    break
        return index


    
if __name__ == "__main__":
    game = FIAR()
    game.init_ML()
    game.reset_game()
    
    while True:
        while not game.game_over:
            game.handle_events()
            
        game.show_message("Play Again? (y/n)", is_exit=True)

2023.10.27 - [AI,ML, Algorithm] - Gomoku(Five in a Row, Omok) (1/5) - 기본 구현 (minimax, alpha-beta pruning)

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는 모두 랜덤 모드로 수를 연산하도록 설정했다. 수를 놓을 때 3자리 이하인 부분에서는,

AI는 점수를 계산하여 높은 점수의 자리에 돌을 놓도록 했다. 플레이어는 3자리 이하인 부분에서 인접한 빈자리 중 랜덤한 위치에 돌을 놓도록 난이도에 약간의 차이를 두었다. 즉, 대부분 비기거나 AI가 좀더 잘 두도록 설정하였다.

#
# FIAR
# Created by netcanis on 2023/10/29.
#
# minimax
# alpha beta pruning
# 속도 개선 
# 훈련데이터 생성하여 머신러닝.

import pygame
import random
import numpy as np
import sys
import os
import tensorflow as tf
from keras.models import Sequential, load_model
import pandas as pd


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_AI = 4
DIFFICULTY_LEVEL_PLAYER = 2

AUTO_PLAY = True

if AUTO_PLAY == True:
    PLAYER_MODE = "RANDOM"#"MINIMAX"
    AI_MODE = "RANDOM"#"MINIMAX"
else:
    PLAYER_MODE = "MANUAL"
    AI_MODE = "RANDOM"#"ML"#"MINIMAX"
    
NUM_EPISODES = 20000
CSV_FILE_NAME = "fiar_training_data.csv"
H5_FILE_NAME = "fiar_model.h5"


class FIAR:
    def __init__(self):
        self.init_game()
    
    def init_game(self):
        self.episode = 0
        
        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 = random.choice([PLAYER, AI]) if AUTO_PLAY == True else 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 = []
        empty_cells2 = []
        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:
                        # 수를 놓았을 경우 연결된 수가 3개 이상이고 5개를 놓을 수 있는 자리일 경우만 배열에 추가.
                        self.board[row][col] = self.turn_player
                        c1, c2, _ = self.evaluate_position(self.board, row, col)
                        self.board[row][col] = -self.turn_player
                        c3, c4, _ = self.evaluate_position(self.board, row, col)
                        self.board[row][col] = 0
                        if (c1 >= 3 and c2 >= 5) or (c3 >= 3 and c4 >= 5):
                            empty_cells2.append((row, col))

                        empty_cells.append((row, col))
                        break
                    
        if len(empty_cells2) > 0:
            return empty_cells2
        
        return empty_cells
    
    def evaluate_position(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
        
        def check_direction_with_blank(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] or board[r][c] == 0):
                count += 1
                r += dx
                c += dy
            return count
        
        total_count1 = 0
        total_count2 = 0
        total_score = 0
        directions = [(0, 1), (1, 0), (1, 1), (-1, 1)]
        for dx, dy in directions:
            count1 = check_direction( dx,  dy)
            count2 = check_direction(-dx, -dy)
            dir_count1 = count1 + count2 - 1
            count3 = check_direction_with_blank( dx,  dy)
            count4 = check_direction_with_blank(-dx, -dy)
            dir_count2 = count3 + count4 - 1
            total_count1 = max(total_count1, dir_count1)
            total_count2 = max(total_count2, dir_count2)
            # 각 방향별로 연결된 돌의 수가 3자리 이상이고 5개이상 놓을 수 있는 자리라면 점수를 추가한다.
            # 즉, 연결되는 돌이 교차하는 위치라면 점수가 높게 나온다.
            if dir_count1 == 4 and dir_count2 >= 5:
                total_score += dir_count1 * 4
            elif dir_count1 >= 3 and dir_count2 >= 5:
                total_score += dir_count1 * 2
            elif dir_count1 >= 2 and dir_count2 >= 5:
                total_score += dir_count1
                
        return total_count1, total_count2, total_score
    
    def check_winner(self, board, row, col):
        if board[row][col] == 0:
            return False
        
        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
        
        best_move = None
        best_score = 0
        
        best_move = self.make_optimal_move(player)
        if best_move == None:
            if player == AI:
                empty_cells = self.find_adjacent_empty_cells()
                for row, col in empty_cells: 
                    self.board[row][col] = player
                    s1 = self.evaluate_position(self.board, row, col)[2]
                    if s1 > best_score:
                        best_score = s1
                        best_move = (row, col)
                    self.board[row][col] = -player
                    s2 = self.evaluate_position(self.board, row, col)[2]
                    if s2 > best_score:
                        best_score = s2
                        best_move = (row, col)
                    self.board[row][col] = 0
                
                if best_score == 0:
                    best_move = random.choice(self.find_empty_cells())
            else:
                best_move = random.choice(self.find_empty_cells())
        
        self.make_move(best_move[0], best_move[1], player)
        
        return best_move

    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 (self.turn_player == AI and depth >= DIFFICULTY_LEVEL_AI) or \
            (self.turn_player == PLAYER and depth >= DIFFICULTY_LEVEL_PLAYER):
            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
    
    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
        
        if (player == PLAYER and PLAYER_MODE == "RANDOM") or (player == AI and AI_MODE == "RANDOM"):
            # 3. The position that becomes 4 when placed
            for row, col in empty_cells: 
                self.board[row][col] = player
                c1, c2, _ = self.evaluate_position(self.board, row, col)
                self.board[row][col] = -player
                c3, c4, _ = self.evaluate_position(self.board, row, col)
                self.board[row][col] = 0
                if (c1 == 4 and c2 >= 5) or (c3 == 4 and c4 >= 5):
                    return (row, col)
                
            # 4. The position that becomes 3 when placed
            for row, col in empty_cells: 
                self.board[row][col] = player
                c1, c2, _ = self.evaluate_position(self.board, row, col)
                self.board[row][col] = -player
                c3, c4, _ = self.evaluate_position(self.board, row, col)
                self.board[row][col] = 0
                if (c1 == 3 and c2 >= 5) or (c3 == 3 and c4 >= 5):
                    return (row, col)
            
        return None
        
    def find_best_move(self, player):
        if AI_MODE == "RANDOM":
            best_move = self.random_move(player)
        else: # MINIMAX
            print(f"[{self.sequence+1}] <{player}> ...")
            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}")
            
            print(f"    {best_move[0]},{best_move[1]} ({best_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
                        message = ""
                        self.draw_board(self.screen)
                        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!")

    def init_ML(self):
        hidden_layer_count = 3 * NUM_ITEMS
        self.model = tf.keras.Sequential([
            tf.keras.layers.Dense(hidden_layer_count, activation='relu', input_shape=(NUM_ITEMS,)),
            tf.keras.layers.Dense(NUM_ITEMS, activation='softmax')
        ])
        self.model.compile(loss='categorical_crossentropy', optimizer='adam', metrics=['accuracy'])
        
    def learning(self):
        if os.path.exists(CSV_FILE_NAME) == False:
            x_data, y_data = self.generate_training_data(NUM_EPISODES)

            self.save_data_to_csv(x_data, y_data, CSV_FILE_NAME)
            print(f"{CSV_FILE_NAME} 저장 완료")
        else:
            x_data, y_data = self.load_data_from_csv(CSV_FILE_NAME)
        
        self.model.fit(x_data, y_data, epochs=100, verbose=1)
        self.model.save(H5_FILE_NAME)
        
        test_results = self.model.evaluate(x_data, y_data)
        print(f"손실(Loss): {test_results[0]}")
        print(f"정확도(Accuracy): {test_results[1]}")
 
    def generate_training_data(self, num_games):
        x_data = []
        y_data = []
        
        while self.episode < num_games:
            self.reset_game()
            
            x = []
            y = []
            while True:
                row, col = self.get_next_move(self.turn_player)
                x.append(np.array(self.board).flatten())
                y.append(np.eye(NUM_ITEMS)[row * BOARD_SIZE + col])
                
                self.draw_board(self.screen)
                pygame.display.flip()
                
                if self.check_winner(self.board, row, col):
                    #print(f"{self.board}")
                    break
                if self.is_board_full(self.board):
                    #print(f"{self.board}")
                    break
                
            if self.turn_player != PLAYER:
                del x[-1]
                del y[0]
                x_data.extend(x)
                y_data.extend(y)
                self.episode += 1
                print(f"{self.episode}: {self.turn_player} win.")

        return np.array(x_data), np.array(y_data)

    def get_next_move(self, player):
        if (player == AI and AI_MODE == "MINIMAX") or (player == PLAYER and PLAYER_MODE == "MINIMAX"):
            return self.minimax_move(player)
        else:
            return self.random_move(player)
        
    def save_data_to_csv(self, x_data, y_data, file_name):
        x_data_flat = [x.flatten() for x in x_data]
        y_data_flat = [y.flatten() for y in y_data]
        data = {'x_data': x_data_flat, 'y_data': y_data_flat}
        df = pd.DataFrame(data)
        df.to_csv(file_name, index=False)

    def load_data_from_csv(self, file_name):
        df = pd.read_csv(file_name)
        x_data_flat = df['x_data'].apply(lambda x: np.fromstring(x[1:-1], sep=' '))
        y_data_flat = df['y_data'].apply(lambda x: np.fromstring(x[1:-1], sep=' '))
        x_data = np.array(x_data_flat.to_list())
        y_data = np.array(y_data_flat.to_list())
        return x_data, y_data
    
    
if __name__ == "__main__":
    game = FIAR()
    game.init_ML()
    game.learning()

2023.10.27 - [AI,ML, Algorithm] - Gomoku(Five in a Row, Omok) (1/5) - 기본 구현 (minimax, alpha-beta pruning)

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 체크 추가

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) (1/5) - 기본 구현 (minimax, alpha-beta pruning)

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 체크 추가

tic tac toe 게임 머신러닝에 이어 오목 게임을 만들어 보자.

아래와 같은 순서로 총 5회로 구성하였다.

Gomoku(Five in a Row, Omok) (1/5) - 기본 구현 (minimax, alpha-beta pruning)

Gomoku(Five in a Row, Omok) (2/5) - 속도 최적화 1차 (minimax 속도 개선)

Gomoku(Five in a Row, Omok) (3/5) - 속도 최적화 2차 (RANDOM모드 추가)

Gomoku(Five in a Row, Omok) (4/5) - 훈련 데이터 생성 및 학습

Gomoku(Five in a Row, Omok) (5/5) - 머신러닝으로 게임 구현

9x9보드에서 minimax알고리즘을 사용하여 간단하게 구현해 보았다.

참고로 3x3을 막고있지 않다. 

DIFFICULTY_LEVEL 값을 높이면 좀더 잘 두지만 속도는 느려진다. 반대로 값을 낮추면  속도는 빨라지지만 잘 두지는 못한다.

가끔씩 엉뚱한 수를 두는 이유는 DIFFICULTY_LEVEL 제한으로 minimax트리검색이 중간에 중단되어 마지막으로 중단된 위치에 수를 놓기 때문이다. 해당 속도문제를 속도 최적화 1차, 속도 최적화 2차를 통해 개선하도록 하겠다.

# 필요한 모듈 임포트
import pygame
import random
import numpy as np
import sys

# 게임 보드 설정
BOARD_SIZE = 9  # 게임 보드 크기 (9x9)
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 초기화
        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 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_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
            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:
            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, 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_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

    # 최적의 수를 찾는 함수
    def find_best_move(self, player):
        # 최적의 수를 찾는 함수
        if self.sequence == 0:
            row = BOARD_SIZE // 2 + random.randint(-2, 2)
            col = BOARD_SIZE // 2 + random.randint(-2, 2)
            return (row, col)

        alpha = -float('inf')
        beta = float('inf')
        best_move = None
        best_score = -float('inf') if player == AI else float('inf')
        empty_cells = self.find_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, (0, 0, 0))
                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):
            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):
                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:
                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)

아래는 게임 실행화면이다.
게임 오버 상태에서 텍스트가 겹치는 오류가 있네.. -_-;;
중요한 문제 아니니 그건 나중에 수정하도록 하겠다.

2023.10.27 - [AI,ML, Algorithm] - Gomoku(Five in a Row, Omok) (1/5) - 기본 구현 (minimax, alpha-beta pruning)

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 체크 추가

신경망 알고리즘을 이용하여 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) - 머신러닝을 이용한 게임 구현