Материал из ProgSchool

Шесть пешек

(Оригинал записи 12 февраля, 2011: http://olymp-omsk.livejournal.com/31398.html)

Вообще, раз мы тут программируем, то есть желание создавать интересные программы. Многие с детских лет помнят, что наиболее интересные программы — это игры. Поэтому хочется написать какую-нибудь игру. Не менее интересно написать такого игрока в игру, который мог бы выиграть человека. Любой, кто увлекается математикой и решал задачки на игры и стратегии, задавался вопросом о выигрышной стратегии в крестики-нолики, шашки или шахматы. Собственно, если стратегия известна, то создать программу, которая выигрывает у человека — не проблема. А что делать, если стратегия неизвестна, а выиграть всё равно хочется?

Можно попытаться придумать машину которая как-то анализирует ситуацию на несколько шагов вперёд и пытается ходить, неким выгодным с её точки зрения способом. Тут сложность состоит в том, чтобы понять, как измерять выгодность. Непонятно, как соотносится выбранная величина с тем, приближается игрок к победе или отдаляется от неё.

Мартин Гарднер в одной из своих статей предложил игру и машину, которая училась бы играть у своего соперника. Сначала машина играет плохо, но затем начинает делать это всё лучше и лучше. Подробно эта игра и алгоритм описаны здесь: Мартин Гарднер «Самообучающаяся машина из спичечных коробков», но суть сводится к тому, что у различных вариантов хода есть вес, определяющий вероятность, с которой машина сделает этот ход. Если какой-то ход привёл к победе, то его вес увеличивается, если ход привёл к поражению, то его вес уменьшается. Таким образом обученная машина начинает отдавать предпочтение ходам с высоким весом, т.е. тем, которые с большой вероятностью приводят к победе.

На занятиях в ШП ребятам было предложено реализовать машину, действующую по этому алгоритму. Теперь можем предложить вашему вниманию игру шесть пешек с самообучающейся машиной, реализованную Сергеем Скрипниковым на Java: Самообучающаяся Машина с Адаптацией

На графике видно, что компьютер сначала много проигрывал (график идёт вниз), а затем стал выигрывать всё чаще и чаще (график начинает идти вверх). Когда человек меняет тактику, компьютер снова начинает проигрывать, но постепенно обучается и этой тактике.

Алгоритм установки и запуска программы:

• Скачиваете JAR-файл
• Запускаете игру командой: java -jar sama.jar