TLDR
Реализация агента MCTS выполняется без ошибок локально, достигая
вероятность выигрыша> 40% против эвристического минимакса, но
автогрейдер - это требование, прежде чем проект может быть
Отправлено. Автогрейдер бросает IndexError: Cannot choose from an empty sequence. Я ищу предложения по части кода
скорее всего, это исключение.
Привет, в данный момент я застрял в этом проекте, который мне нужно очистить, прежде чем я завершу программу, в которую я зачислен, через 2 недели. Моя задача, которую я уже выполнил, состоит в том, чтобы заставить агента играть против минимаксного агента, управляемого эвристикой, в игре «Изоляция» между двумя шахматными рыцарями. Полную информацию о реализации игры можно найти здесь . Для моего проекта игра будет играть на доске размером 9х11, используя кодирование битборда. Моя реализация MCTS проста, точно следуя псевдокоду, представленному в этой статье (стр. 6).
По сути, общий подход MCTS включает эти 4 части, и каждая из них реализуется следующими вложенными функциями в классе CustomPlayer:
- Выбор - tree_policy
- Расширение - best_child, расширение
- Simulation - 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's 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's 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.
Из моего обсуждения с представлением курса мы считаем, что ошибка, вероятно, вызвана использованием random.choice(). В моей реализации есть 4 случая его использования:
- Строка 39, перед алгоритмом MCTS, для подачи случайного перемещения в очередь
- Строка 66, чтобы случайным образом выбрать один ход, который не был опробован
- Строка 114, для случайного выбора действия, если в счете лучших ходов есть ничья
- Строка 122, для случайной симуляции игры до состояния терминала для выбранного хода
Я предполагаю, что реализация игры правильная, и вызов state.actions () всегда будет возвращать список возможных ходов, пока состояние является терминальным. Следовательно, единственным экземпляром, который может вызвать это исключение, является элемент 3. Элементы 1 и 4 просто случайным образом выбирают из доступных действий, в то время как существует явная проверка, чтобы убедиться, что random.choice () не снабжается пустым списком. Поэтому я применил логирование к пункту 3 (хотя при локальном запуске не было создано ни одного исключения) и, конечно же, не обнаружил никаких исключений после 50 игр.
Я прошу прощения за длинный пост, но я надеюсь, что кто-то там сможет поймать то, что я пропустил в моей реализации.