Агент поиска дерева Монте-Карло в игре "Изоляция" - предложения по отладке
TL;DR
Внедрение агента MCTS выполняется без ошибок локально, достигая вероятности выигрыша> 40% по отношению к минимаксному эвристическому алгоритму, но не дает возможности автогрейдеру - что является обязательным требованием, прежде чем проект может быть представлен. IndexError: Cannot choose from an empty sequence выбрасывает IndexError: Cannot choose from an empty sequence. Я ищу предложения со стороны кода, который, скорее всего, сгенерирует это исключение.
Привет, я в настоящее время застрял в этом проекте, который мне нужно очистить, прежде чем я завершу программу, в которую я зачислен, через 2 недели. Моя задача, которую я уже выполнил, состоит в том, чтобы заставить агента играть против минимаксного агента, управляемого эвристикой, в игре "Изоляция" между двумя шахматными рыцарями. Полную информацию о реализации игры можно найти здесь. Для моего проекта игра будет играть на доске размером 9х11, используя кодирование битборда. Моя реализация MCTS проста, точно следуя псевдокоду, представленному в этой статье (стр. 6).
По сути, общий подход MCTS включает в себя эти 4 части, и каждая из них реализуется следующими вложенными функциями в классе CustomPlayer:
- Выбор - tree_policy
- Расширение - best_child, расширение
- Симуляция - default_policy
-
Обратное распространение - backup_negamax, update_scores
import math
import random
import time
import logging
from copy import deepcopy
from collections import namedtuple
from sample_players import DataPlayer
class CustomPlayer(DataPlayer):
""" Implement your own agent to play knight Isolation
The get_action() method is the only required method for this project.
You can modify the interface for get_action by adding named parameters
with default values, but the function MUST remain compatible with the
default interface.
**********************************************************************
NOTES:
- The test cases will NOT be run on a machine with GPU access, nor be
suitable for using any other machine learning techniques.
- You can pass state forward to your agent on the next turn by assigning
any pickleable object to the self.context attribute.
**********************************************************************
"""
def get_action(self, state):
""" Employ an adversarial search technique to choose an action
available in the current state calls self.queue.put(ACTION) at least
This method must call self.queue.put(ACTION) at least once, and may
call it as many times as you want; the caller will be responsible
for cutting off the function after the search time limit has expired.
See RandomPlayer and GreedyPlayer in sample_players for more examples.
**********************************************************************
NOTE:
- The caller is responsible for cutting off search, so calling
get_action() from your own code will create an infinite loop!
Refer to (and use!) the Isolation.play() function to run games.
**********************************************************************
"""
logging.info("Move %s" % state.ply_count)
self.queue.put(random.choice(state.actions()))
i = 1
statlist = []
while (self.queue._TimedQueue__stop_time - 0.05) > time.perf_counter():
next_action = self.uct_search(state, statlist, i)
self.queue.put(next_action)
i += 1
def uct_search(self, state, statlist, i):
plyturn = state.ply_count % 2
Stat = namedtuple('Stat', 'state action utility visit nround')
def tree_policy(state):
statecopy = deepcopy(state)
while not statecopy.terminal_test():
# All taken actions at this depth
tried = [s.action for s in statlist if s.state == statecopy]
# See if there any untried actions left
untried = [a for a in statecopy.actions() if a not in tried]
topop = []
toappend = []
if len(untried) > 0:
next_action = random.choice(untried)
statecopy = expand(statecopy, next_action)
break
else:
next_action = best_child(statecopy, 1)
for k, s in enumerate(statlist):
if s.state == statecopy and s.action == next_action:
visit1 = statlist[k].visit + 1
news = statlist[k]._replace(visit=visit1)
news = news._replace(nround=i)
topop.append(k)
toappend.append(news)
break
update_scores(topop, toappend)
statecopy = statecopy.result(next_action)
return statecopy
def expand(state, action):
"""
Returns a state resulting from taking an action from the list of untried nodes
"""
statlist.append(Stat(state, action, 0, 1, i))
return state.result(action)
def best_child(state, c):
"""
Returns the state resulting from taking the best action. c value between 0 (max score) and 1 (prioritize exploration)
"""
# All taken actions at this depth
tried = [s for s in statlist if s.state == state]
maxscore = -999
maxaction = []
# Compute the score
for t in tried:
score = (t.utility/t.visit) + c * math.sqrt(2 * math.log(i)/t.visit)
if score > maxscore:
maxscore = score
del maxaction[:]
maxaction.append(t.action)
elif score == maxscore:
maxaction.append(t.action)
if len(maxaction) < 1:
logging.error("IndexError: maxaction is empty!")
return random.choice(maxaction)
def default_policy(state):
"""
The simulation to run when visiting unexplored nodes. Defaults to uniform random moves
"""
while not state.terminal_test():
state = state.result(random.choice(state.actions()))
delta = state.utility(self.player_id)
if abs(delta) == float('inf') and delta < 0:
delta = -1
elif abs(delta) == float('inf') and delta > 0:
delta = 1
return delta
def backup_negamax(delta):
"""
Propagates the terminal utility up the search tree
"""
topop = []
toappend = []
for k, s in enumerate(statlist):
if s.nround == i:
if s.state.ply_count % 2 == plyturn:
utility1 = s.utility + delta
news = statlist[k]._replace(utility=utility1)
elif s.state.ply_count % 2 != plyturn:
utility1 = s.utility - delta
news = statlist[k]._replace(utility=utility1)
topop.append(k)
toappend.append(news)
update_scores(topop, toappend)
return
def update_scores(topop, toappend):
# Remove outdated tuples. Order needs to be in reverse or pop will fail!
for p in sorted(topop, reverse=True):
statlist.pop(p)
# Add the updated ones
for a in toappend:
statlist.append(a)
return
next_state = tree_policy(state)
if not next_state.terminal_test():
delta = default_policy(next_state)
backup_negamax(delta)
return best_child(state, 0)
Отсутствие цветного форматирования делает код действительно сложным для чтения. Поэтому, пожалуйста, не стесняйтесь проверить это на моем github. У меня нет проблем с локальным запуском игры, поскольку мой агент MCTS достигает выигрышных ставок> 40% (под лимитом 150 мс/ход) против минимаксного игрока. Однако, когда я пытаюсь отправить свой код авторейдеру, он отклоняется с помощью IndexError: Cannot choose from an empty sequence исключения IndexError: Cannot choose from an empty sequence.
Из моего обсуждения с представлением курса мы полагаем, что ошибка, вероятно, вызвана использованием random.choice(). В моей реализации есть 4 случая его использования:
- Строка 39, перед алгоритмом MCTS, для подачи случайного перемещения в очередь
- Строка 66, чтобы случайным образом выбрать один ход, который не был опробован
- Строка 114, чтобы случайным образом выбрать действие, если в счете лучших ходов есть ничья
- Линия 122, чтобы симулировать игру случайным образом до состояния терминала для выбранного хода
Я предполагаю, что реализация игры верна, и вызов state.actions() всегда будет возвращать список возможных ходов, пока состояние является конечным. Следовательно, единственным экземпляром, который может вызвать это исключение, является элемент 3. Элементы 1 и 4 просто случайным образом выбирают из доступных действий, в то время как существует явная проверка, чтобы убедиться, что random.choice() не снабжается пустым списком. Следовательно, я применил логирование к пункту 3 (хотя при локальном запуске не было создано ни одного исключения) и, конечно же, не обнаружил никаких исключений после 50 игр.
Я прошу прощения за длинный пост, но я надеюсь, что кто-то там сможет поймать что-то, что я пропустил в моей реализации.
Ответы
Ответ 1
Я бы порекомендовал написать модульные тесты для каждой из ваших функций. Проверьте свои предположения о поведении вашего кода. Попытайтесь быть всесторонним о тестировании этого, включая угловые случаи. Просто необходимость ввода абстрактных тестовых примеров обычно показывает многое об архитектуре и деталях решения.
Кроме того, вы можете попытаться позволить своему агенту играть в любую другую подходящую игру. Эти шаги дадут вам хороший шанс обнаружить ошибку в вашем коде и сделать ее более пригодной для повторного использования в будущем.
