Форум программистов, компьютерный форум, киберфорум
Python: Решение задач
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
0 / 0 / 0
Регистрация: 04.05.2020
Сообщений: 23

Можете проверить, правильно ли мой алгоритм ищет наилучший ход через альфа-бета отсечение

20.03.2022, 02:36. Показов 471. Ответов 0

Студворк — интернет-сервис помощи студентам
Если есть время, можете проверить код, правильно ли он ищет наилучший ход через минимакс альфа бета отсечение. Игра называется отелло (другое название реверси). Самая главная функция, это функция move() в классе MyPlayer. Если что- то не будет понятно, спрашивайте.

Python
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
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
import copy
from random import shuffle, randint
import numpy as np
 
 
class MyPlayer():
    '''MiniMax AlphaBeta pruning'''
        
    def __init__(self, my_color,opponent_color, board_size=8):
        self.my_color = my_color
        self.opponent_color = opponent_color
        self.board_size = board_size
        self.empty_color = -1
 
 
    def move(self, board):
        moves = self.get_all_valid_moves(board)
        print(moves)
        opponent_color = self.opponent_color
        if not moves:
            return None
        move = self.find_best_move(board, 10, opponent_color)
        return move
 
    def __is_correct_move(self, move, board):
        dx = [-1, -1, -1, 0, 1, 1, 1, 0]
        dy = [-1, 0, 1, 1, 1, 0, -1, -1]
        for i in range(len(dx)):
            if self.__confirm_direction(move, dx[i], dy[i], board)[0]:
                return True, 
        return False
 
    def __confirm_direction(self, move, dx, dy, board):
        posx = move[0]+dx
        posy = move[1]+dy
        opp_stones_inverted = 0
        if (posx >= 0) and (posx < self.board_size) and (posy >= 0) and (posy < self.board_size):
            if board[posx][posy] == self.opponent_color:
                opp_stones_inverted += 1
                while (posx >= 0) and (posx <= (self.board_size-1)) and (posy >= 0) and (posy <= (self.board_size-1)):
                    posx += dx
                    posy += dy
                    if (posx >= 0) and (posx < self.board_size) and (posy >= 0) and (posy < self.board_size):
                        if board[posx][posy] == -1:
                            return False, 0
                        if board[posx][posy] == self.my_color:
                            return True, opp_stones_inverted
                    opp_stones_inverted += 1
 
        return False, 0
 
    def get_all_valid_moves(self, board):
        valid_moves = []
        for x in range(self.board_size):
            for y in range(self.board_size):
                if (board[x][y] == -1) and self.__is_correct_move([x, y], board):
                    valid_moves.append( (x, y) )
 
        if len(valid_moves) <= 0:
            print('No possible move!')
            return None
        return valid_moves
    
    
    def alphabeta(self, board, current_player, depth, alpha, beta):
        """
        param board: current state
        depth: how deep i want to predict
        alpha: maximum score for me
        beta: max opponent score
        current_player: player color
        """
        if Board().is_draw:
            return 0
        if Board().is_win or depth == 0:
            return Board().evaluate(current_player)
        if Board().turn == current_player:
            for move in Board().legal_moves:
                scores = self.alphabeta(Board().right_move(move), current_player, depth-1, alpha, beta)
                alpha = max(scores, alpha)
                if alpha >= beta:
                    break
            return alpha
        else:
            for move in Board().legal_moves(board):
                scores = alphabeta(Board().right_move(move), current_player, depth-1, alpha, beta)
                beta = min(scores, beta)
                if alpha >= beta:
                    break
            return beta
 
    def find_best_move(self, board, max_depth, opponent_color):
        """Finds the best valid move for player
            board - current_state,
            max-depth - the depth of searching
            returns best move - (x, y)
        """
        player = Board().turn
        moves = Board().legal_moves
        best_scores = float('-inf')
        min_scores = -best_scores
        best_move = moves[0]
        for move in moves:
            scores = self.alphabeta(Board().right_move(move), player, max_depth, alpha=best_scores, beta=min_scores)
            print(move, scores)
            if opponent_color:
                scores = self.alphabeta(Board().right_move(move), player, max_depth, alpha=-best_scores, beta=-min_scores)
            if scores > best_scores:
                best_move = move
                best_scores = scores
        return best_move
 
    def get_opposite_color(self, player_color):
        """looking for the color of the opponent"""
        if player_color == self.my_color:
            return self.opponent_color
        elif player_color == self.opponent_color:
            return self.my_color
        else:
            return self.empty_color
 
 
 
class Board():
    """Basic class for a board of game. Contains state of board for current turn."""
 
    def __init__(self, turn = 0, size = 10, field = None):
        if field is None:
            pass
        self._field = field
        self._size = size
        self._turn = turn
        self._legal_moves = set()
 
    def turn(self):
        """Returns number of current player."""
        return self._turn
 
    def field(self):
        return self._field
 
    def last_turn(self):
        """Returns number of previous player."""
        return MyPlayer().get_opposite_color(self._turn)
 
    def get_neighbours(self, location, area_size = 1):
        """Returns a list of adjacent locations."""
        x, y = location
        neighbours = ((x - i, y - j) for i in range(-area_size, area_size + 1)
                      for j in range(-area_size, area_size + 1))
        possible_neighbours = [(x, y) for x, y in neighbours if 0 <= x < self._size and 0 <= y < self._size]
        return possible_neighbours
 
    def right_move(self, location):
        """
        Returns board with next state after move.
        :param location:
        :return: copy of board with new state
        """
        pass
 
    def is_win(self):
        """Returns True if player wins."""
        pass
 
    def is_draw(self):
        """Returns True if there are no moves and no one wins."""
        return not (self.is_win or self.legal_moves)
 
    def legal_moves(self):
        """Returns list of possible and reasonable moves. It's necessary for ai."""
        return list(self._legal_moves)
 
    def evaluate(self, player):
        """Evaluate state of board for current player and returns estimation of scores. It's necessary for ai."""
        pass
 
    def get_value(self, x, y):
        """Returns value from field"""
        return self._field[x][y].value
 
 
class Reversi(Board):
 
    def __init__(self, size = 10, turn = 0, field: np.ndarray = None, boundary_moves: set = None,
                 last_move = None):
        """
        A game board for reversi (otello).
        :param size: 6, 8 or 10 for board size. If new board is empty
        :param turn: 0 or 1 for player number.
        :param field: Old field with new move. If a new board is obtained by making a move on the previous board.
        :param boundary_moves: Set of positions for moves along the border of placed pieces.
        :param last_move: Position of last move.
        """
        if field is None:
            # If creating new empty field
            field = np.array([[-1 for _ in range(size)] for _ in range(size)])
            field[size // 2 - 1][size // 2 - 1] = 0
            field[size // 2][size // 2] = 0
            field[size // 2 - 1][size // 2] = 1
            field[size // 2][size // 2 - 1] = 1
            boundary_moves = {(i, j) for i in range(size // 2 - 2, size // 2 + 2)
                              for j in range(size // 2 - 2, size // 2 + 2) if field[i][j] == 0}
        self._field = field
        self._size = size
        self._turn = turn
        self._boundary_moves = boundary_moves
        self._legal_moves = []
        self._gem_counters = [0, 0, 0]
        self.last_move = last_move
        # Recount gems
        for i in range(3):
            self._gem_counters[i] = (self._field == i).sum()
        self.check_legal_moves()
        # When player can't do any move return turn
        if len(self._legal_moves) == 0:
            self._turn = self.last_turn
            self.check_legal_moves()
        # When even opponent can't do any move set clear positions to zero to end game
 
    def get_gem_count(self):
        return self._gem_counters[0], self._gem_counters[1]
 
    def check_legal_moves(self):
        self._legal_moves = []
        for x, y in self._boundary_moves:
            # Flag that move is added to stop checking
            move_added = False
            # Check all directions
            for dx, dy in ((0, 1), (0, -1), (1, 0), (-1, 0), (1, 1), (-1, -1), (1, -1), (-1, 1)):
                k = 1
                next_x, next_y = x + k * dx, y + k * dy
                # Flag to know when we reached reverse color
                got_reverse_color = False
                while 0 <= next_x < self._size and 0 <= next_y < self._size and self._field[next_x][next_y] != -1:
                    if self._field[next_x][next_y] == self.last_turn:
                        got_reverse_color = True
                    else:
                        if self._field[next_x][next_y] == self.turn and got_reverse_color:
                            # We can change color of at least one piece
                            self._legal_moves.append((x, y))
                            move_added = True
                        break
                    k += 1
                    next_x, next_y = x + k * dx, y + k * dy
                if move_added:
                    break
 
    def right_move(self, location):
        """
        Returns board with next state after move.
        :param location:
        :return: copy of board with new state
        """
        if location not in self._legal_moves:
            return None
        x, y = location
        new_boundary_moves = self._boundary_moves.copy()
        for i, j in self.get_neighbours((x, y)):
            if 0 <= i < self._size and 0 <= j < self._size and self._field[i][j] == -1:
                new_boundary_moves.add((i, j))
        new_boundary_moves.remove((x, y))
        new_field = self._field.copy()
        new_field[x][y] = self.turn
        for dx, dy in ((0, 1), (0, -1), (1, 0), (-1, 0), (1, 1), (-1, -1), (1, -1), (-1, 1)):
            k = 1
            next_x, next_y = x + k * dx, y + k * dy
            # Flag to know when we reached reverse color
            got_reverse_color = False
            while 0 <= next_x < self._size and 0 <= next_y < self._size and self._field[next_x][next_y] != -1:
                if self._field[next_x][next_y] == self.last_turn:
                    got_reverse_color = True
                else:
                    if self._field[next_x][next_y] == self.turn and got_reverse_color:
                        next_x -= dx
                        next_y -= dy
                        while next_x != x or next_y != y:
                            new_field[next_x][next_y] = self.turn
                            next_x -= dx
                            next_y -= dy
                    break
                k += 1
                next_x, next_y = x + k * dx, y + k * dy
        new_turn = self.last_turn
        return Reversi(self._size, new_turn, new_field, new_boundary_moves, location)
 
    def is_win(self):
        """Returns true if it is win"""
        if self._gem_counters[0] > self._gem_counters[1]:
            self._turn = 1
            return True
        if self._gem_counters[1] > self._gem_counters[0]:
            self._turn = 0
            return True
        return False
 
    def is_draw(self):
        """Returns True if it is draw"""        
        if self._gem_counters[0] == self._gem_counters[1]:
            return True
        return False
 
    def evaluate(self, player):
        return self._gem_counters[player] -self._gem_counters[MyPlayer().get_opposite_color(player)]
0
cpp_developer
Эксперт
20123 / 5690 / 1417
Регистрация: 09.04.2010
Сообщений: 22,546
Блог
20.03.2022, 02:36
Ответы с готовыми решениями:

Правильно ли код ищет лучший ход через альфа бета отсечение?
Если есть время, можете проверить код, правильно ли он ищет наилучший ход через минимакс альфа бета отсечение. Игра называется отелло...

Альфа-бета отсечение
Нужен человек, который разбирается в этом. необходимо пояснить картинку, которая в википедии. с минимаксом вроде как разобрался, а вот с...

Альфа-бета отсечение
Здравствуйте! Есть задача: Осуществить альфа-бета отсечение на приведенном на рисунке дерева, просматривая вершины в направлении слева -...

0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
raxper
Эксперт
30234 / 6612 / 1498
Регистрация: 28.12.2010
Сообщений: 21,154
Блог
20.03.2022, 02:36
Помогаю со студенческими работами здесь

Альфа-бета-отсечение на отсортированном дереве
Глубина дерева 3, у каждой вершины степень 10 (у каждого узла 10 потомков). Если на этом отсортированным дереве запустить...

Четыре в ряд. (Connect Four) Альфа-бета отсечение
Уважаемые! Представляю вам игру компьютер vs игрок - Четыре в ряд. Цель - выставлять по очереди фишки на поле 6х7 (причем фишки падают...

Стратегия min-max, альфа-бета отсечение в игре Калах
Здравствуйте. Помогите пожалуйста разобраться. Нужно переделать(подкорректировать) код игры с использованием алгоритмов min-max,...

Можете проверить мой код? Спасибо заранее
//Программа: &quot;Двусвязный список&quot; //1.) Автоматизированная информационная система на железнодорожном вокзале содержит сведения об...

Метрическая задача. Через точку В провести плоскость Бетта перпендикулярную прямой АС и построить линию пересечения плоскостей Бета и Альфа
Через точку В провести плоскость Бета перпендикулярную прямой АС и построить линию пересечения плоскостей Бета и Альфа ( Альфа задана...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
1
Ответ Создать тему
Новые блоги и статьи
PhpStorm 2025.3: WSL Terminal всегда стартует в ~
and_y87 14.12.2025
PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .
Access
VikBal 11.12.2025
Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.
Новый ноутбук
volvo 07.12.2025
Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro
Музыка, написанная Искусственным Интеллектом
volvo 04.12.2025
Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .
От async/await к виртуальным потокам в Python
IndentationError 23.11.2025
Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
Поиск "дружественных имён" СОМ портов
Argus19 22.11.2025
Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .
Сколько Государство потратило денег на меня, обеспечивая инсулином.
Programma_Boinc 20.11.2025
Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .
Ломающие изменения в C#.NStar Alpha
Etyuhibosecyu 20.11.2025
Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .
Мысли в слух
kumehtar 18.11.2025
Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .
Создание Single Page Application на фреймах
krapotkin 16.11.2025
Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2025, CyberForum.ru