Моделирование и нестандартные алгоритмы выбора стратегий в недетерминированных антагонистических играх и родственных задачах

Вторая глава. Во второй главе рассматривается дерево антагонистической игры двух лиц — формализм, используемый при моделировании игр. Рассматривается и обосновывается метод минимакса — метод поиска оптимальной стратегии в дереве игры. Как обоснование подхода к выбору оптимального хода формулируется и доказывается теорема о существовании динамических оценок вершин дерева детерминированной игры и теорема о существовании динамической оценки вершин в дереве недетерминированной игры.

Третья глава. В третьей главе рассматривается основанный на «функции риска» метод улучшения качества псевдооптимальных стратегий, получаемых методом минимакса в сильно ветвящихся деревьях антагонистических недетерминированных игр двух лиц. Метод разработан, а также реализован в виде компьютерной программы автором4, которая продемонстрировала довольно сильную игру5 при простой оценочной функции.

В начале главы рассматриваются традиционные подходы к сокращению перебора. Так, в разделе 3.1 рассматривается эвристика сведения поиска оптимальной стратегии к поиску псевдооптимальной стратегии в усеченных деревьях, как один из самых распространенных методов сокращения перебора. В результате такого усечения возникает проблема точного оценивания динамической оценки вершины дерева игры по ее усеченному дереву. Различные приближения к «настоящим» оценкам пытаются получить при помощи оценочных функций. Небольшой обзор6 этого будет в разделе 3.2.

В разделе 3.3 рассматривается модификация метода мини.

4Идея метода принадлежит научному руководителю автора.

5Программа одержала победу в играх с несколькими компьютерными программами backgammon, которые было возможно взять из сети Internet. бВ данной работе не ставилась цель нахождения способов построения оценочной функции, хотя, конечно, от ее вида многое зависит. Но минимаксный алгоритм на базе функции риска дает хорошие результаты используя даже тривиальную оценочную функцию. макса, базирующаяся на понятии функции риска. За основу метода снова взят традиционный подход к сокращению перебора, а именно: предлагается модификация вычисления динамических оценок вершин со случайнным ходом. Предварительные оценки позиций дерева игры в этой модификации получаются, если можно так выразиться, временным «удалением» недетерминированности. Для этого сначала предполагается, что уже реализовался конкретный исход случайного события и вычисляется динамическая оценка для оцениваемой позиции (с ходом белых или черных) так же, как и в методе минимакса. Затем вычисляется динамическая оценка позиции для следующего исхода случайного события и так далее для всех исходов.

Окончательная динамическая оценка некоторой вершины со случайным ходом дерева игры определяется на основе всех детерминированных7 оценок, полученных для всех возможных исходов случайного события. Полученные значения детерминированных оценок специальным образом усредняются. Это и есть построенная динамическая оценка для вершины со случайным ходом. С физической точки зрения такое усредение дает положение центра тяжести одномерной системы тел с массами, определяемыми специально подобранной функцией (функцией риска). Координатами тел системы — значения соответствующей детерминированной оценки.

Четвертая глава. В четвертой главе рассматриваются некоторые специфические особенности backgammon. В этой игре четко выделяются две фазы — фаза «противоборства» и фаза вывода фишек8. В отличие от первой фазы, вторая использует минимаксный алгоритм для выбора оптимального хода только формально, так как во второй фазе игры ходы игрока не влияют на последующие ходы его противника. По-этому выбор

7Детерминированной оценкой здесь называется динамическая оценка, полученная для вершин с ходом белых или черных.

8 См. правила backgammon в разделе 1.1.2. хода можно проводить без моделирования поведения игрока-соперника. В свою очередь, возникает вопрос об оценочной функции для вывода фишек: действительно ли ее вид существенно влияет на количество ходов, необходимых для вывода фишек с доски?

Этот вопрос обсуждается далее в четвертой главе на примере пяти сравнительно простых алгоритмов вывода фишек. Алгоритмы исследуются на предмет эффективности, под которой понимается среднее количество бросков костей, необходимое для вывода с доски всех фишек.

1. Адельсон-Вельский Г. М., Арлазаров В. Л., Донской М. В. Программирование игр. — М.: Наука, 1978.

2. Богатырев Р. Шахматы по-американски // Мир ПК. — 1997. — N 7−8.

3. Ботвинник М. Алгоритм игры в шахматы. — М.: Наука, 1968.

4. Кибернетика ожидаемая и кибернетика неожиданная. — М.: Наука, 1968.

5. Компьютер и задачи выбора. М.: Наука, 1989.

6. Компьютеры, модели, вычислительный эксперимент. — М.: Наука, 1988.

7. Мельников Б. Ф., Радионов А. Н. О выборе стратегии в недетерминированных антагонистических играх // Программирование — 1998. — N5.

8. Радионов А. Н. Некоторые критерии риска в играх с неполной информацией // Тезисы докладов на XI Международной конференции по проблемам теоретической кибернетики. — Ульяновск: СВНЦ, 1996.

9. Радионов А. Н. Критерии риска в программных моделях игр с нулевой суммой // Фундаментальные проблемы математики и механики. Выпуск 1. Часть 2. / Под ред. А. А. Бутова. — Ульяновск: изд-во УлГУ, 1996.

10. РадионовА. Н. Нестандартные методы оценивания позиции в недетерминированных антагонистических играх // Фундаментальные проблемы математики и механики. Выпуск 2. / Под ред. Б. Ф. Мельникова. — Ульяновск: изд-во УлГУ, 1996.

11. РадионовА. Н. Игровые ассистирующие программы // Фундаментальные проблемы математики и механики. Выпуск 3. / Под ред. Б. Ф. Мельникова. — Ульяновск: изд-во УлГУ, 1997.

12. Шеннон К. Э. Машина для игры в шахматы // Работы по кибернетике и теории информации. — М.: Физматгиз, 1956. — с. 180−191.

13. Angeline, Р. J. (1994). An alternate interpretation of the iterated prisoner’s dilemma and the evolution of non-mutual cooperation.

14. Angeline, P. J. and Pollack, J. B. (1994). Competitive environments evolve better solutions for complex tasks. InForrest, S., editor, Genetic Algorithms: Proceedings of the Fifth International Conference.

15. Axelrod, R. (1984). The evolution of cooperation. Basic Books, New York.

16. Barto, A., Sutton, R., and Anderson, C. (1983). Neuronlike adaptive elements that can solve difficult learning control problems. IEEE Transactions on Systems, Man, and Cybernetics, 13.

17. Berliner, H., 1980. Computer Backgammon. Sci. Am. 243, 6472.

18. Berliner, H., Principal Research Scientist. HTML Page.

19. Boyan, J. A. (1992). Modular neural networks for learning context-dependent game strategies. Master’s thesis, Computer Speech and Language Processing, Cambridge University.

20. Cliff, D. and Miller, G. (1995). Tracking the red queen: Measurements of adaptive progress in coevolutionary simulations. In Third European Conference on Artificial Life, pages 200−218.

21. Epstein, S. L. (1994). Toward an ideal trainer. Machine Learning, 15(3).

22. Fogel, D. B. (1993). Using evolutionary programming to create neural networks that are capable of playing tic-tac-toe. In International conference on Neural Networks, pages 875−880. IEEE Press.

23. Galperin, G., and Tesauro, G., Parallel Monte-Carlo Simulation of Nirual Network Controllers. HTML Page.

24. Hillis, D. (1992). Co-evolving parasites improves simulated evolution as an optimization procedure. In C. Langton, C. Taylor, J. F. and Rasmussen, S., editors, Artificial Life II. Addison-Wesley, Reading, MA.

25. Holland, J. (1975). Adaptation in Natural and Artificial Systems. The University of Michigan Press.

26. Holland, J. H. (1994). Echoing emergence. In Cowan, G., Pines, D., and Meltzer, D., editors, Complexity: Metaphors, Models, and Reality, pages 309−342. Addison-Wesley.

27. International Business Machines, Press Release (Sept. 12, 1995). «IBM's family funpak for OS/2 Warp hits retail shelves» .

28. Juille, H. and Pollack, J. (1995). Massively parallel genetic programming. In Kinnear, P. A.. K., editor, Advances in Genetic Programming II. MIT Press, Cambridge.

29. Kauffman, S. A. (1993). The origins of Order: Self-Organization and Selection in Evolution. Oxford University Press.

30. Kieth, T., Backgammon Galore, HTML Page.

31. Klopf, A. H. (1982). The Hedonistic Neuron. Hemisphere Publishing Corporation, Washington, D.C.

32. Lindgren, K. (1992). Evolutionary phenomena in simple dynamics. In C. Langton, C. Taylor, J. F. and Rasmussen, S., editors, Artificial Life II. Addison-Wesley, Reading, MA.

33. Littman, M. L. (1994). Markov games as a framework for multi-agent reinforcement learning. In Machine Learning: Proceedings of the Eleventh International Conference, pages 157−163. Morgan Kaufmann.

34. Marsland, T.A. (1992) Computer Chess and Search // Encyclopedia of Artificial Intelligence./ Ed. by S. Shapiro. John Wiley and Sons, 1992).

35. Masters, J., A History Of Traditional Games: Backgammon, HTML Page.

36. Michie, D. (1961). Trial and error. In Science Survey, part 2, pages 129−145. Penguin.

37. Mitchell, M., Hraber, P. T., and Crutchfield, J. P. (1993). Revisiting the edge of chaos: Evolving cellular automata to perform computations. Complex Systems, 7.

38. Packard, N. (1988). Adaptation towards the edge of chaos. In Kelso, J. A. S., Mandell, A. J., and Shlesinger, M. F., editors, Dynamic patterns in complex systems, pages 293−301. World Scientific.

39. Pollack, J., Blair, A., and Land, M., 1996. Coevolution of a Backgammon Player. Proceedings of the Fith Artificial Life Conference. May, Nara, Japan. HTML Page.

40. Pollack, J., Blair, A., and Land, M., HC-Gammon, HTML Page.

41. Ray, T. (1992). An approach to the synthesis of life. In C. Langton, C. Taylor, J. F. and Rasmussen, S., editors, Artificial Life II. Addison-Wesley, Reading, MA.

42. Reynolds, C. (1994). Competition, coevolution, and the game of tag. In Proceedings 4th Artificial Life Conference. MIT Press.

43. Rosin, C. D. and Belew, R. K. (1995). Methods for competitive coevolution: finding opponents worth beat-ing. In Proceedings of the 6th international conference on Genetic Algorithms, pages 373−380. Morgen Kauffman.

44. Rumelhart, D., Hinton, G., and Williams, R. (1986). Learning representations by back-propagating errors. Nature, 323:533 536.

45. Samuel, A. L. (1959). some studies of machine learning using the game of checkers. IBM Joural of Research and Development.

46. Schnieder, A., First Internet Backgammon Server. HTML Page.

47. Schraudolph, N. N., Dayan, P., and Sejnowski, T. J. (1994). Temporal difference learning of position evaluation in the game of go. In Advances in Neural Information Processing Systems, volume 6, pages 817−824. Morgen Kauffman.

48. Sconyer, H., Bearoff Equities and Backgame Probabilities. Gammon Press, vl HTML Page.

49. Scott, J., Gerald Tesauro’s TD-Gammon. HTML Page.

50. Scott, J., The Hillclimbing HC-Gammon. HTML Page.

51. Sims, K. (1994). Evolving 3d morphology and behavior by competition. In Proceedings 4th Artificial Life Conference. MIT Press.

52. Sutton, R. (1984). Temporal Credit Assignment in Reinforcement Learning. PhD thesis, University of Massachusetts, Amherst.

53. Sutton, R. (1988). Learning to predict by the methods of temporal differences. Machine Learning, 3:9- 44.

54. Tepandi, J., Temporal difference learning and TD-Gammon, ACM Review., Communications of the ACM. HTML Page.

55. Tesauro, G., and Sejnowski, T.J. 1989. A parallel network that learns to play backgammon. Artificial Intelligence 39, 357−390.

56. Tesauro, G., 1989. Neurogammon wins Computer Olympiad. Neural Computation 1, 321−323.

57. Tesauro, G., 1994. TD-Gammon, ASelf-Teaching Backgammon Program, Achieves Master-Level Play. IBM Thomas J. Watson Research Center, HTML Page.

58. Tesauro, G., 1995. Temporal Difference Learning and TD-Gammon. Communications of the ACM. 38, 58−68. HTML Page.

59. Tesauro, J., Public Evaluation Function (PUBEVAL) Source Code, HTML Page.

60. Tesauro, G. (1992). Practical issues in temporal difference learning. Machine Learning, 8:257−277.

61. Tesauro, G. (1995). Temporal difference learning and TD-Gammon. Communications of the ACM, 38(3):58−68.

62. Turner, S., The WWW Backgammon Page, HTML Page.