Machine Learning in Games

• Learning strategies based on feedback from the environment (reinforcement)

• Games like Chess, Tic Tac Toe, Go, Backgammon

• Elevator Dispatching

• Robot Control

• Job-Shop Scheduling

• MENACE is playing algorithm for the game of Tic Tac Toe

• Initial position:

  • 287 Matchboxes (one for each position)

  • Beads in 9 different colors (one for each square)

• Playing algorithm:

  • Select the matchbox corresponding to the current position

  • Randomly draw a bead from this matchbox

  • Play the move corresponding to the color of the drawn bead

• Learning algorithm:

  • Game lost → drawn beads are kept (negative reinforcement)

  • Game won → put the drawn bead back and add another one in the same color to this box (positive reinforcement)

  • Game drawn → drawn beads are put back (no change)

• No regard of the credit assignment assignment

• The learner normally knows whether it has won or lost not before the end of the game

• The learner does not know which move(s) are responsible for the win / loss

• TD-Gammon –> learned to play Backgammon

• MENACE –> learned to play Tic Tac Toe

• Knight Cap –> learned to play Chess

• Problem –> one does not know what the opponents legal moves are in the future so Minimax is not longer applicable

• Solution –> standard game trees are extended with chance nodes (A node where the successor is determined not by the choice of moves of one the opponents, but by a chance event)

• 
  

• The higher N the better is the approximation

• Roll out: Play the position many times, each time with a different (random) dice roll

• Instead of searching until a certain depth for all nodes (like Minimax) alternatively, we can limit the breadth of the search tree

• Algorithm:

  • estimate the expected value of each move by counting the number of wins in a series of complete games

  • at each chance node select one of the options at random

• Properties:

  • We need a fast algorithm for making the decisions at each node in the roll-out games

  • Often works well even if the move selection is not that strong

  • Is easily processed parallel

• Monte-Carlo search is a extreme case of simulation search

  • play a large number of games where both players make their moves randomly

  • average the scores of these games

  • make the move that has the highest average score

• Monte-Carlo search can also be used for deterministic games not only on games of chance

• There are several one-armed bandit machines

• Each of them has a different average reward/loss

• How can we figure out which machine to play, if we want to lose as less money as possible/win as much money as possible

• The Upper Confidence Bound (UCB) algorithm

• Exploitation: Pull the best arm in order to maximize your earnings

• Exploration: Try if other arms are more promising

• Monte-Carlo Search can be integrated with conventional game-tree search algorithms

• Construction:

  • incrementally build up a search tree

  • evaluate the leaf nodes via roll-outs

  • evaluate promising moves more often than bad moves

• MCTS uses two poicies:

  • tree policy –> how is the tree traversed in order to find the best outcome

  • rollout policy –> how are the moves in the roll-out games selected

• The tree grows deeper in regions of good moves, since these are chosen more often

• UCT Search is a variation of UCB

• It randomly adds a selected node to the game tree

• First perform one iteration of Mone-Carlo Search

• Then use backpropagation and adjust the values for each node

• Select the move which has been visited most often

• UCT Search caused breakthrough in Go

• In the early 2000s Computer Go programs could not beat a child

• But then there was Alpha Go and it defeated a human champion for the first time –> this was not expected

• 
  

• Aplha Go combined Monte-Carlo Search, Deep Learning and Reinforcement Learning

• used a (fast) learned roll-out policy instead of random sampling

• use a depth-limit in MCTS where a learned evaluation

  function is used instead of real game outcomes

• roll-out policy –> learned from expert games, inaccurate but fast

• expert policy –> learned from expert games, accurate but takes a long time to compute

• selection policy –> refine expert policy with reinforcement learning

• utility function –> using self-play from selection policy

• improved version of Alpha Go that learned to play only from self-play

• Brought improvement not only to Go but also to games like Chess

• try to predict the opponent's next move

• try to predict what move the opponent predicts that your next move will be and so forth

• Difference between your winnings and the winnings you would have got if you had always played the (unknown) optimal arm.

• Policy: A strategy for selecting actions

• Policy networks –> using move probabilities

• Value networks –> using Evaluation functions

• Learning of policies (action selection strategies) based on feedback from the environment (reinforcement)

• MENACE: 

  Learns to play Tic-Tac-Toe and uses 287 matchboxes filled with beads in 9 different colors (1 color for each square). While playing, one selects the matchbox of the corresponding position, draws a bead from the box and plays the move indicated by the bead. If the game is lost, all drawn beads are kept (negative reinforcement), if the game is drawn the beads are put back and if the game is won the beads are doubled when put back (positive reinforcement)

• TD-Gammon: Learns to play backgammon. Improvements over MENACE:

  • faster convergence because of Temporal Difference (TD) Learning - backpropagating every move

  • NN used instead of matchboxes - allows generalization

  • use of positional characteristics as features

• Example on multi-armed bandit problem: Pull the best arm in order to maximize your earnings (exploitation) vs. try if other arms are more promising (exploration)

  • solved by UCB (upper confidence bound) algorithm consisting of:

    • exploitation term - average earning of arm i

    • exploration term - inverse probability of how often arm i has been played

    • always play the arm with highest UCB

• Player A cannot directly maximize their gain because they don’t know what B’s legal actions will be. Standard game trees are therefore extended with chance nodes - an expected value (average) of the outcome needs to be computed at each chance node. A deep look ahead is not feasible since the probability of reaching a given node shrinks with increasing depth.

• If exact probabilities for the outcomes at the chance nodes are not known, values can be sampled. 

• Simulated Search:

  • we can limit the breadth of the search tree and sample some lines to the full depth

  • estimate the expected values of each move by counting the number of wins in a series of complete games

  • at each node select one of the options at random (according to probabilities) at MAX and MIN nodes make move

• Find the arm (move) with the highest long-term utility from observations of immediate utilities with as little regret as possible

• Extreme case of simulation search - play a large number of games where both players make their move randomly, average the scores of these games and make the move that has the highest average score. Can also be used in deterministic games.

Monte-Carlo Tree Search (MCTS):

• incrementally build up a search tree, evaluate the leaf nodes via roll-outs, evaluate promising moves more often than bad moves but give bad moves also a chance (UCB algorithm) - tree grows deeper in regions of good moves

• uses two policies

  • Tree Policy: how is the tree traversed in order to find the best leaf to be expanded

  • Roll-out/Default Policy: how are the moves in the roll-out games selected 

    

• UCT Search - the best-known formulation of MCTS, it combines a UCB-based tree policy with random roll-outs. 

  

• AlphaGo combines MCTS with deep learning and reinforcement learning from self-play.

  • use a (fast) learned roll-out policy

  • use a depth-limit in MCTS where a learned evaluation function is used

  • learn from expert games a fast but inaccurate roll-out policy

  • learn from expert games an accurate expert policy

  • refine the expert policy into a more accurate selection policy

  • use self-play from the selection policy to train a utility function

• AlphaGo Zero started without any knowledge and from random behavior

• For simple games we know optimal solutions, but optimal solutions are not maximal. Mind the difference between maximizing your winning (exploit your opponents’ weaknesses) and playing optimal.

  Opponent Modeling - try to predict the opponent’s next move, try to predict what move the opponent predicts that your next move will be,…