Apply ant colony optimization to Tetris

ABSTRACT

Tetris is a falling block game where the player's objective is to arrange a sequence of different shaped tetrominoes smoothly in order to survive. In the intelligence games, agent imitates the real player and chooses the best move based on a linear value function. In this paper, we apply Ant Colony Optimization (ACO) method to learn the weights of the function, trying to search an optimal weight-path in the weight graph. We use dynamic heuristic to prevent premature convergence to local optima. Our experimental result is better than most of traditional reinforcement learning methods.

REFERENCES

• 1: Dimitri P. Bertsekas , John N. Tsitsiklis, Neuro-Dynamic Programming, Athena Scientific, 1996
• 2: N. Bohm, G. K¶okai, and S. Mandl. An evolutionary approach to tetris. In 6th Metaheuristics International Conference, pages CD{ROM, 2005.
• 3: J. Brzustowski. Can you win at tetris? Master's thesis, University of British Columbia, 1992.
• 4: E. Demaine, S. Hohenberger, and D. Liben-Nowell. Tetris is hard, even to approximate. In Proceedings of the 9th International Computing and Combinatorics Conference (COCOON 2003), 2003.
• 5: K. Driessens. Relational Reinforcement Learning. PhD thesis, Catholic University of Leuven, 2004.
• 6: H.-B. DUAN. Ant Colony Algorithms: Theory and Applications. Science Press, 2005.
• 7: C. P. Fahey. Tetris AI. http://www.colinfahey.com.
• 8: V. F. Farias and B. van Roy. Tetris: A study of randomized constraint sampling. In Probabilistic and Randomized Methods for Design Under Uncertainty. Springer-Verlag UK, 2006.
• 9: S. Kakade. A natural policy gradient. In Advances in Neural Information Processing Systems, volume 14, 2002.
• 10: Michail G. Lagoudakis , Ronald Parr , Michael L. Littman, Least-Squares Methods in Reinforcement Learning for Control, Proceedings of the Second Hellenic Conference on AI: Methods and Applications of Artificial Intelligence, p.249-260, April 11-12, 2002
• 11: István Szita , András Lörincz, Learning tetris using the noisy cross-entropy method, Neural Computation, v.18 n.12, p.2936-2941, December 2006 [doi>10.1162/neco.2006.18.12.2936]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Markov processes

General Terms:
Experimentation

Keywords:
Tetris, ant colony optimization, reinforcement learning, weight graph