В игры играют со стратегией. Каждый игрок или команда должны разработать стратегию перед началом игры, и они должны изменить или построить новую стратегию в соответствии с текущей ситуацией (-ями) в игре.
Алгоритмы поиска
Вы должны будете рассмотреть компьютерные игры также с той же стратегией, что и выше. Обратите внимание, что алгоритмы поиска — это те, которые определяют стратегию в компьютерных играх.
Как это устроено
Цель алгоритмов поиска — найти оптимальный набор ходов, чтобы они могли добраться до конечного пункта назначения и выиграть. Эти алгоритмы используют выигрышный набор условий, различных для каждой игры, чтобы найти лучшие ходы.
Визуализируйте компьютерную игру в виде дерева. Мы знаем, что у дерева есть узлы. Начиная с корня, мы можем прийти к последнему выигрышному узлу, но с оптимальными ходами. Это работа поисковых алгоритмов. Каждый узел в таком дереве представляет будущее состояние. Алгоритмы поиска осуществляют поиск по этому дереву, чтобы принимать решения на каждом этапе или узле игры.
Комбинационный поиск
Основным недостатком использования поисковых алгоритмов является то, что они носят исчерпывающий характер, поэтому они исследуют все пространство поиска, чтобы найти решение, которое приводит к неэффективному использованию ресурсов. Было бы более громоздким, если бы этим алгоритмам приходилось искать все пространство поиска для нахождения окончательного решения.
Чтобы устранить такую проблему, мы можем использовать комбинационный поиск, который использует эвристику для исследования пространства поиска и уменьшает его размер, устраняя возможные неправильные движения. Следовательно, такие алгоритмы могут экономить ресурсы. Некоторые из алгоритмов, которые используют эвристику для поиска пространства и сохранения ресурсов, обсуждаются здесь —
Минимаксный алгоритм
Это стратегия, используемая комбинационным поиском, которая использует эвристику для ускорения стратегии поиска. Концепция стратегии Minimax может быть понята на примере игр с двумя игроками, в которых каждый игрок пытается предсказать следующий ход противника и пытается минимизировать эту функцию. Также, чтобы выиграть, игрок всегда старается максимизировать свою собственную функцию в зависимости от текущей ситуации.
Эвристика играет важную роль в таких стратегиях, как Minimax. Каждый узел дерева будет иметь эвристическую функцию, связанную с ним. Исходя из этой эвристики, будет принято решение сделать шаг в сторону узла, который принесет им наибольшую пользу.
Альфа-бета-обрезка
Главная проблема алгоритма Minimax заключается в том, что он может исследовать те части дерева, которые не имеют отношения к делу и приводят к потере ресурсов. Следовательно, должна быть стратегия, чтобы решить, какая часть дерева является релевантной, а какая неактуальной, и оставить не относящуюся к делу неисследованную часть. Альфа-бета-обрезка является одним из таких стратегий.
Основная цель алгоритма отсечения альфа-бета-версии — избежать поиска тех частей дерева, которые не имеют никакого решения. Основная концепция сокращения альфа-бета-версии заключается в использовании двух границ, называемых Альфа , максимальная нижняя граница и Бета , минимальная верхняя граница. Эти два параметра являются значениями, которые ограничивают множество возможных решений. Он сравнивает значение текущего узла со значением альфа- и бета-параметров, чтобы он мог перейти к той части дерева, которая имеет решение, и отбросить остальные.
Алгоритм Негамакс
Этот алгоритм не отличается от алгоритма Minimax, но имеет более элегантную реализацию. Основным недостатком использования алгоритма Minimax является то, что нам нужно определить две разные эвристические функции. Связь между этими эвристиками заключается в том, что чем лучше состояние игры для одного игрока, тем хуже для другого игрока. В алгоритме Negamax одинаковая работа двух эвристических функций выполняется с помощью одной эвристической функции.
Создание ботов для игр
Чтобы собрать ботов для игры двух игроков в AI, нам нужно установить библиотеку easyAI . Это среда искусственного интеллекта, которая предоставляет все функциональные возможности для создания игр для двух игроков. Вы можете скачать его с помощью следующей команды —
pip install easyAI
Бот, который сыграет последнюю монету
В этой игре будет куча монет. Каждый игрок должен взять несколько монет из этой стопки. Цель игры — не брать последнюю монету в стопку. Мы будем использовать класс LastCoinStanding, унаследованный от класса TwoPlayersGame библиотеки easyAI . Следующий код показывает код Python для этой игры —
Импортируйте необходимые пакеты, как показано на рисунке —
from easyAI import TwoPlayersGame, id_solve, Human_Player, AI_Player from easyAI.AI import TT
Теперь унаследуйте класс от класса TwoPlayerGame для обработки всех операций игры.
class LastCoin_game(TwoPlayersGame): def __init__(self, players):
Теперь определите игроков и игрока, который собирается начать игру.
self.players = players self.nplayer = 1
Теперь определите количество монет в игре, здесь мы используем 15 монет для игры.
self.num_coins = 15
Определите максимальное количество монет, которое игрок может взять за ход.
self.max_coins = 4
Теперь есть некоторые определенные вещи, которые нужно определить, как показано в следующем коде. Определите возможные ходы.
def possible_moves(self): return [str(a) for a in range(1, self.max_coins + 1)]
Определите удаление монет
def make_move(self, move): self.num_coins -= int(move)
Определите, кто взял последнюю монету.
def win_game(self): return self.num_coins <= 0
Определите, когда остановить игру, то есть когда кто-то выиграет.
def is_over(self): return self.win()
Определите, как рассчитать счет.
def score(self): return 100 if self.win_game() else 0
Определите количество монет, оставшихся в стопке.
def show(self): print(self.num_coins, 'coins left in the pile') if __name__ == "__main__": tt = TT() LastCoin_game.ttentry = lambda self: self.num_coins
Решение игры с помощью следующего блока кода —
r, d, m = id_solve(LastCoin_game, range(2, 20), win_score=100, tt=tt) print(r, d, m)
Решить, кто начнет игру
game = LastCoin_game([AI_Player(tt), Human_Player()]) game.play()
Вы можете найти следующий вывод и простую игру этой игры —
d:2, a:0, m:1 d:3, a:0, m:1 d:4, a:0, m:1 d:5, a:0, m:1 d:6, a:100, m:4 1 6 4 15 coins left in the pile Move #1: player 1 plays 4 : 11 coins left in the pile Player 2 what do you play ? 2 Move #2: player 2 plays 2 : 9 coins left in the pile Move #3: player 1 plays 3 : 6 coins left in the pile Player 2 what do you play ? 1 Move #4: player 2 plays 1 : 5 coins left in the pile Move #5: player 1 plays 4 : 1 coins left in the pile Player 2 what do you play ? 1 Move #6: player 2 plays 1 : 0 coins left in the pile
Бот для игры в крестики-нолики
Крестики-нолики — очень знакомая и одна из самых популярных игр. Давайте создадим эту игру с помощью библиотеки easyAI на Python. Следующий код Python-код этой игры —
Импортируйте пакеты как показано —
from easyAI import TwoPlayersGame, AI_Player, Negamax from easyAI.Player import Human_Player
Унаследуйте класс от класса TwoPlayerGame для обработки всех операций игры.
class TicTacToe_game(TwoPlayersGame): def __init__(self, players):
Теперь определите игроков и игрока, который собирается начать игру —
self.players = players self.nplayer = 1
Определите тип доски —
self.board = [0] * 9
Теперь есть некоторые определенные вещи, которые можно определить следующим образом:
Определите возможные ходы
def possible_moves(self): return [x + 1 for x, y in enumerate(self.board) if y == 0]
Определить ход игрока —
def make_move(self, move): self.board[int(move) - 1] = self.nplayer
Чтобы повысить ИИ, определите, когда игрок делает ход —
def umake_move(self, move): self.board[int(move) - 1] = 0
Определите условие проигрыша, когда у противника три в линии
def condition_for_lose(self): possible_combinations = [[1,2,3], [4,5,6], [7,8,9], [1,4,7], [2,5,8], [3,6,9], [1,5,9], [3,5,7]] return any([all([(self.board[z-1] == self.nopponent) for z in combination]) for combination in possible_combinations])
Определите чек на финиш игры
def is_over(self): return (self.possible_moves() == []) or self.condition_for_lose()
Показать текущую позицию игроков в игре
def show(self): print('\n'+'\n'.join([' '.join([['.', 'O', 'X'][self.board[3*j + i]] for i in range(3)]) for j in range(3)]))
Подсчитайте баллы.
def scoring(self): return -100 if self.condition_for_lose() else 0
Определите основной метод для определения алгоритма и запуска игры —
if __name__ == "__main__": algo = Negamax(7) TicTacToe_game([Human_Player(), AI_Player(algo)]).play()
Вы можете увидеть следующий результат и простую игру этой игры —