TD-Gammon - это искусственная нейронная сеть, обученная с помощью TD (λ), которая учится играть в нарды самостоятельно.
В этом посте TD-Gammon 0.0 реализован на Python с использованием Keras и Tensorflow. Полное описание TD-Gammon дано в разделах Обучение с временной разницей и TD-Gammon и Практические вопросы в обучении с временной разницей. Пример использования TD-Gammon также приведен в книге Обучение с подкреплением: введение (Саттон и Барто).
Код этой реализации можно найти на GitHub.
Нейронная сеть и выбор действий
Нейронная сеть используется для оценки значения каждого состояния (положения доски). Он принимает положение платы в качестве входных данных и выводит реальное значение от 0 до 1 с использованием сигмоидной функции активации. Во время обучения награда для каждого состояния равна 0, за исключением случая, когда игрок 1 выиграл, и в этом случае награда равна 1. Следовательно, функция значения может быть интерпретирована как вероятность выигрыша первого игрока, начиная с этого состояния (таким образом, вероятность выигрыша второго игрока просто 1 минус функция значения).
Каждый ход агента TD-Gammon:
- Бросает кости,
- Находит все разрешенные ходы с учетом текущего положения на доске и бросков кубиков,
- Вычисляет послесостояние для всех разрешенных ходов (новое положение доски после каждого хода),
- Вычисляет значение каждого послесостояния, заданного сетью,
- Затем, наконец, играет ход, который приводит к пост-состоянию с наибольшей вероятностью выигрыша.
Следовательно, это просто жадная политика в отношении функции ценности, заданной сетью.
def action(self, board, roll, player):
"""Predicts the optimal move given the current state.
This calculates each afterstate for all possible moves given the
current state and selects the action that leads to the state with
the greatest afterstate value.
Arguments:
board -- board containing the game state
roll -- list of dice rolls left in the players turn
player -- number of the player
"""
start = time.time()
max_move = None
max_prob = -np.inf
permitted = board.permitted_moves(roll, player)
for move in permitted:
afterstate = copy.deepcopy(board)
if not afterstate.move(*move, player):
logging.error("model requested an invalid move")
continue
state = afterstate.encode_state(player)[np.newaxis]
prob = tf.reduce_sum(self._model(state))
# The network gives the probability of player 0 winning so must
# change if player 1.
prob = 1 - prob if player == 1 else prob
if prob > max_prob:
max_prob = prob
max_move = move
if self._state is None:
self._state = tf.Variable(board.encode_state(player))
if self._value is None:
self._value = tf.Variable(self._model(self._state[np.newaxis]))
duration = time.time() - start
logging.debug("playing move [player = %d] [move = %s] [winning prob = %f] [duration = %ds]", player, str(max_move), max_prob, duration)
return max_moveВ исходной статье описывается сеть с 4 выходами, соответствующими первому или второму игроку, которые выигрывают либо обычный выигрыш, либо гаммон, хотя я использую сеть, описанную у Саттона и Барто, которая имеет единственный выход.
Положение доски кодируется как 198 входных единиц, кодирующих позиции шашек каждого игрока на доске, на панели и удаляемые с доски. Также два дополнительных юнита кодируют, какой игрок будет рядом.
Сеть имеет единственный скрытый слой из 40 единиц и использует функцию активации сигмовидной кишки. Обратите внимание, что в более поздних версиях используется больше скрытых единиц, хотя это реализует только TD-Gammon 0.0.
def __init__(self, restore_path = None):
"""Construct a model with random weights.
Arguments:
restore_path -- path to stored checkpoint to restore if given
(default None)
"""
inputs = tf.keras.Input(shape=(198,))
x = tf.keras.layers.Dense(40, activation="sigmoid")(inputs)
outputs = tf.keras.layers.Dense(1, activation="sigmoid")(x)
self._model = tf.keras.Model(inputs=inputs, outputs=outputs)
// ...Обучение
Модель учится, играя против самой себя во многих играх. После каждого перемещения модель будет вычислять градиент значения нового состояния по отношению к весам сети.
Затем ошибку TD можно рассчитать как вознаграждение плюс значение нового состояния минус значение предыдущего состояния.
Наконец, трассу соответствия можно обновить и применить к весам.
def update(self, board, player):
"""Updates the model given the current state and reward.
This is expected to be called after the player has made their move.
The aim is to move the predicted values towards the actual reward
using TD-lambda.
Arguments:
board -- board containing the game state
roll -- list of dice rolls left in the players turn
"""
start = time.time()
x_next = board.encode_state(player)
with tf.GradientTape() as tape:
value_next = self._model(x_next[np.newaxis])
trainable_vars = self._model.trainable_variables
grads = tape.gradient(value_next, trainable_vars)
# Lazily initialize when gradient shape known.
if len(self._trace) == 0:
for grad in grads:
self._trace.append(tf.Variable(
tf.zeros(grad.get_shape()), trainable=False
))
if player == 0 and board.won(player):
reward = 1
else:
reward = 0
td_error = tf.reduce_sum(reward + value_next - self._value)
for i in range(len(grads)):
self._trace[i].assign((self._LAMBDA * self._trace[i]) + grads[i])
grad_trace = self._ALPHA * td_error * self._trace[i]
self._model.trainable_variables[i].assign_add(grad_trace)
self._state = tf.Variable(x_next)
self._value = tf.Variable(value_next)
duration = time.time() - start
logging.debug("updating model [player = %d] [duration = %ds]", player, duration)Обратите внимание, что альфа и лямбда даны в Практических вопросах обучения временной разнице как 0,7 и 0,1 соответственно, и используется ставка дисконтирования, равная 1.
Оценка
Для простоты оценки агент TD-Gammon играет 1000 игр против агента, выбирающего действия случайным образом из разрешенных ходов каждый ход. Запуск notebook.ipynb в AWS SageMaker для 500 учебных эпизодов, что заняло около дня (на ml.t2.medium экземпляре), поскольку каждый эпизод представляет собой несколько тысяч ходов.
После 500 тренировочных серий агент TD-Gammon выиграл 97,5% игр.
Первоначально опубликовано на http://andrewdunstall.com.
