Reinforcement Learning Tetris Example
In a previous AI life, I did some research into reinforcement
learning, q-learning, td-learning, etc.. Initially we wanted to use
these techniques to train a robot soccer team, however we soon learned that
these techniques were simply the wrong tool for the job. Other than Tesauro's
work on Backgammon we found few worthwhile applications of reinforcement
learning. There wasn't anything similar to our soccer problem domain.
Desperately stuck in the situation where we had to do something to pass this
course it suddenly hit me: "How about Tetris?".
Motivation
Consider the game of Tetris. The player is continually given pieces of varying
shape that must be positioned and rotated, then dropped on the pieces below.
Since these pieces begin to pile up, the player must try to stack them
efficiently. Furthermore, if the player manages to complete a row, then that
row dissapears thus freeing up more space. The objective is to keep the height
as low as possible. Note that the shape of each subsequent piece is random thus
making it difficult to plan ahead (non-deterministic).
People who play many hours of this addicting game, will likely develop
strategies for playing. For example, they may try to fill up the corners and
single-wide spaces first, while avoiding the situation where free spaces get
covered by objects on top thus becoming unaccessable.
We tested to see if an agent could learn to play tetris without giving it
heuristics or directly programming its strategies. The guts of the agent is a
utility function (or evaluation function) that indicates a value for a
configuration of pieces (state). When the agent is given a random piece to add,
it evaluates all the valid placements and chooses the action that results in
the best configuration (according to the utility function). This architecture
is very similar to what Tesauro used for TD-Gammon. Unlike Tesauro's neural
network structure, we used a table to represent our utility function. This
table is initially set to 0 for all input states. It is up to the agent to
learn this table as it places the tetris pieces (i.e. as it moves from state to
state).
Smaller Version of Game
For our experiments we used a smaller implementation of
the Tetris game. The pieces are at most 2x2:
The area where pieces are placed is 6 units wide, and the maximum working
height is 2. Some examples of states are:
As in the regular game of tetris, rows are removed when they become full. The
following picture (going left to right) shows how this happens when a piece is
added:
When the working height of 2 is exceeded, the bottom row is removed and the
total height (agent's score for this game) is incremented:
Our games consisted of 10000 pieces each. Even though the game parameters are
reduced, the size of our table (number of states) is 2^(6*2)=4096 which is
rather big (but manageable).
An example of a state that should have a low utility value is:
Given the next piece is a solid 2x2 block, the agent will be forced to increase
the total height of the pile by 2 units. Therefore it is desirable to avoid
getting into states like these.
Implementation and Results
Using reinforcement learning the agent adapted the utility function and
dramatically improved its performance as it played a number of games. The
following table and plot show the improvement in agents score (total height)
over a number of 10000 piece games:
|
|
Game Score
------------
1 1485
2 1166
4 1032
8 902
16 837
32 644
64 395
128 303
256 289
|
Note that the a lower score is better than a higher score. To
keep the table short only game numbers that are an even power of 2 were
reported.
The agent used the following incremental learning update rule:
U(state) = U(state)*(1-alpha) + (reward+gamma*U(nextstate))*alpha
Where U() is the utility function table. The agent is
penalized with a reward of -100 for each level it goes above the working
height, otherwise reward is set to 0. The intuition behind using a discount
factor, gamma < 1.0, is because even though we may eventually have to
position a piece that puts us above the working height it is best to avoid that
situation as long as possible. Furthermore, a discount factor bounds the
utility values which could otherwise go to positive or negative infinity. Using
incremental learning (alpha
<1.0) instead of just making the direct assignment: >
U(state) = reward + gamma*U(nextstate)
is necessary because of the non-deterministic element (the
shape of the next piece is random) in the Tetris environment.
Attempted Learning Enhancements
Ideally the value of alpha should be decreased over time to
help converge the utility values. Without a strategy for migrating alpha we
simply used a smaller constant value of 0.02. This turned out to be a fairly
good choice as we later tried some other values for comparison:
value of Alpha
Game 0.002 0.02 0.2
-------------------------
1 1451 1485 1404
2 1204 1166 1043
4 1043 1032 752
8 971 902 525
16 938 837 420
32 912 644 370
64 955 395 342
128 848 303 339
256 679 289 351
Learning is clearly slower with the lower alpha value of
0.002. Using the higher value (0.2) learns quicker at first but doesn't
eventually reach the performance achieved by setting alpha to 0.02.
Using only the adjacent state update rule (instead of the extended TD learning
update rule) was sufficient for the Tetris learner. This is because we were
able to apply penalties more frequently (every time the blocks stack too high).
Whereas, a backgammon game, which consists of many moves, must be completed
before the reward/penalty is applied. Furthermore, Tesauro used backpropogation
neural networks which are notoriously slow to train. We experimented with using
TD learning for learning Tetris. The following table shows compares our
previous results with a TD enhanced version of our agent.
Game Q TD
-------------------
1 1485 1520
2 1166 1182
4 1032 1000
8 902 903
16 837 855
32 644 635
64 395 394
128 303 289
256 289 256
As the results show, we were unable to achieve any significant
improvement in learning. This is understandable since in our Tetris environment
the effects of actions are realized sooner and actions do not have lasting
consequences. Given the different types of pieces, and all the possible
placements of them, from a state there can be up to 52 possible next states.
Its possible to get from any state to most others in 3 moves. TD learning is
more likely to improve learning in an environment with more states and a lower
branching factor.
Future Work
In most learning situations, an agent must decided whether to
choose what it thinks is the best action, or explore a different action in the
hopes of finding a better solution. It almost seems odd that our Tetris agent
is able to continually improve performance even though it only chooses the best
action. An explanation of this is that this game is a "losing
battle". Utility values are initially set to 0 and tend to move downward.
Nonetheless, we believe that adding an exploration strategy would provide some
benefit.
As mentioned earlier, this size of game we were experimenting with was smaller
than the regular version of Tetris. The biggest problem with scaling upward is
that the utility table is exponential in size compared to the working area
(game board). For a full sized game, an alternative implementation of the
utility function, such as a neural network, would have to be used.
Conclusion
In conclusion, reinforcement learning techniques work extremely well for
training agents to play Tetris-like games efficiently. We were able to tackle
this problem in a way that was very similar to the approach taken by Tesauro's
backgammon work, which is the most frequently (if not the only) mentioned
application of reinforcement learning. An example that is often used to explain
reinforcement learning is tic-tac-toe. One problem with using this as a
learning example is that it is much better solved with simple minimax search.
The small state space search problem in the Russell/Norvig AI textbook, which
was fabricated to explain learning algorithms, also fails to inspire practical
applications of this technology. In the famous cart-pole balancing problem
(also known as the inverted pendulum), the task that is learned is a very
simple reflex reaction. Our Tetris example shows a straightforward
reinforcement learning solution to a well known and reasonably sized problem
where there isn't a much more obvious and better solution that should be used
instead.
Thus we have accomplished the goal of AI research: Finding a problem to fit the
solution!
S Melax