GomokuGamePlay/aiPlayer.py at master · Yousef-karem/GomokuGamePlay · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
import copy
import math
import random

DEPTH = 2
DIRECTIONS = [(1, 0), (0, 1), (1, 1), (1, -1)]
start = 3
N = 17
HUMAN = 'W'
AI = 'B'


def get_available_moves(grid):
    moves = []
    for i in range(start, N):
        for j in range(start, N):
            if grid[i][j] == ' ':
                for dx, dy in DIRECTIONS:
                    for d in [-1, 1]:
                        ni, nj = i + dx * d, j + dy * d
                        if start <= ni < N and start <= nj < N and grid[ni][nj] != ' ':
                            moves.append((i, j))
                            break
                    else:
                        continue
                    break
    if not moves:
        count = 0
        while count < 10:
            i, j = random.randint(start, N), random.randint(start, N)
            if grid[i][j] == ' ':
                moves.append((i, j))
                count += 1
    return moves


def evaluate_line(line, player):
    score = 0
    opponent = 'B' if player == 'W' else 'W'
    if line.count(player) == 5:
        score += 100000
    elif line.count(player) == 4 and line.count(' ') == 1:
        score += 9000
    elif line.count(player) == 3 and line.count(' ') == 2:
        score += 1000
    elif line.count(player) == 2 and line.count(' ') == 3:
        score += 100
    elif line.count(opponent) == 4 and line.count(' ') == 1:
        score -= 10000
    return score


def evaluate_board(grid, player):
    total_score = 0

    # horizontal vertical diagonal
    for i in range(start, N):
        for j in range(start, N):
            for dx, dy in DIRECTIONS:
                line = []
                for k in range(5):
                    ni, nj = i + dx * k, j + dy * k
                    if start <= ni < N and start <= nj < N:
                        line.append(grid[ni][nj])
                if len(line) == 5:
                    total_score += evaluate_line(line, player)
    return total_score


def minimax(grid, depth, is_maximizing, player):
    opponent = 'B' if player == 'W' else 'W'
    best_score = float('-inf') if is_maximizing else float('inf')
    best_move = None

    for move in get_available_moves(grid):
        i, j = move
        new_grid = copy.deepcopy(grid)
        new_grid[i][j] = player if is_maximizing else opponent

        if depth == 1:
            score = evaluate_board(new_grid, player)
        else:
            score, _ = minimax(new_grid, depth - 1, not is_maximizing, player)

        if is_maximizing:
            if score > best_score:
                best_score = score
                best_move = move
        else:
            if score < best_score:
                best_score = score
                best_move = move

    return best_score, best_move


def minimax_move(grid, is_white=True):
    player = 'W' if is_white else 'B'
    _, move = minimax(grid, DEPTH, True, player)
    return move


def alphaBetaPruning(grid, depth, alpha, beta, isMaximizing, player):
    if depth == 0:
        return evaluate_board(grid, player), None

    best_move = None
    moves = get_available_moves(grid)

    if not moves:
        return 0, None

    opponent = 'W' if player == 'B' else 'B'

    if isMaximizing:
        finalResult = -math.inf

        for move in moves:
            i, j = move
            new_grid = copy.deepcopy(grid)
            new_grid[i][j] = player

            result, _ = alphaBetaPruning(new_grid, depth - 1, alpha, beta, False, player)

            if result > finalResult:
                finalResult = result
                best_move = move

            alpha = max(alpha, finalResult)
            if beta <= alpha:
                break

    else:
        finalResult = math.inf

        for move in moves:
            i, j = move
            new_grid = copy.deepcopy(grid)
            new_grid[i][j] = opponent

            result, _ = alphaBetaPruning(new_grid, depth - 1, alpha, beta, True, player)

            if result < finalResult:
                finalResult = result
                best_move = move

            beta = min(beta, finalResult)
            if beta <= alpha:
                break

    return finalResult, best_move


def getAlphaBetaMove(grid, is_white):
    player = 'W' if is_white else 'B'
    _, move = alphaBetaPruning(grid, DEPTH, -math.inf, math.inf, True, player)
    return move