Самообучающаяся программа

Постановка задачи.

Задание посвящено созданию программы для игры с компьютером в качестве противника. Программу нужно сделать самообучающейся: первоначально, компьютер будет вам проигрывать, но постепенно он должен накапливать опыт и, в конце концов, станет вам достойным противником.

1. Описание игры

В игру " шесть пешек" играют на доске размером 3 на 3 клетки. Каждый из игроков имеет по три пешки. Начальная позиция показана на следующем рисунке.

Ходы разрешается делать лишь двух типов:

1) пешка может передвинуться на одну клетку вперед, если эта клетка пуста;

2) пешка может взять пешку другого цвета, стоящую справа или слева на соседней клетке по диагонали, и остаться на освободившейся клетке.

Взятая пешка снимается с доски. Ходы пешек, как видно из этих правил, в основном совпадают с ходами пешек в обычных шахматах. Однако в отличие от шахмат нашим пешкам не разрешается делать двойной ход в начале партии, брать пешку противника на проходе и превращаться в какие-либо другие фигуры того же цвета.

Партия считается выигранной в следующих трех случаях:

1) когда одну из пешек удается провести в третий ряд;

2) когда взяты все пешки противника;

3) когда противник не может сделать очередного хода.

Играющие делают ходы по очереди, передвигая каждый раз по одной пешке. Очевидно, что закончится вничью игра не может; далеко не так очевидно, какой из игроков имеет преимущество: делающий второй ход или тот, кто начинает игру.

Теория игры в шесть пешек совершенно тривиальна, тем не менее, я убедительно прошу читателя не проводить никакого анализа. Построив программу и постигнув все тонкости " шестипешия" в процессе обучения её игре, вы получите гораздо больше удовольствия.

2. Алгоритм самообучающейся программы

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

Обучение происходит следующим образом. Любая партия закончится после третьего хода программы. Если партию программа выиграла, то стратегия не меняется. Если программа проиграет, то необходимо понизить оценку (“вероятность”) тех ходов, которые сделала программа. Более подробно, пусть S1, S2, S3, S4, S5, S6, S7 - список последовательных позиций в партии, которую проиграла программа (для упрощения изложения, возможно, пришлось изменить нумерацию позиций). Программа делала ходы в позициях S2, S4 и S6. Таким образом, для обучения программы необходимо уменьшить оценку S6 и, возможно, вероятности S2, S4.

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

Для быстрейшего самообучения в программу следует заложить и второго партнера, играющего по той же или другой системе, так чтобы машина играла сама с собой.

Базовая программа на Прологе игры с самообучением:

game: -

'инициализировать'(Position, Gamer),

'отобразить игру'(Position, Gamer),

game(Position, Gamer, [], Rezalt).

game(Position, Gamer, History, Rezalt): -

/* History - список пар (Позиция/Кто ходил перед этим) */

'игра окончена'(Position, Gamer, Rezalt),!,

'объявить'(Rezalt),

'самообучение'(Position, Gamer, History, Rezalt).

game(Position, Gamer, History, Rezalt): -

'выбрать ход'(Position, Gamer, Go),!,

'ходить'(Go, Position, PositionNext),

'другой игрок'(Gamer, Gamer1),

'отобразить игру'(PositionNext, Gamer1),

game(PositionNext, Gamer1, [PositionNext/Gamer|History], Rezalt).

Возможно, следующие предикаты будут полезны.

Позиция представляется в виде пары

(Список белых пешек - Список черных пешек),

координаты пешек - целые числа от 1 до 9.

Исходная позиция - [1, 2, 3]-[7, 8, 9].

value(Позиция, С_точки_зрения, Оценка) - предикат базы знаний

'самообучение'(_, Gamer, _, Gamer).

'самообучение'(Position, Gamer, History, Rezalt): -

not(Gamer=Rezalt),

'другой игрок'(Gamer, Gamer1),

'уменьшить оценки'([Position/Gamer1|History], Gamer).

'возможный ход белыми'(W-B, From-Where)

'возможный ход черными'(W-B, From-Where)

'выбрать ход'(Position, white, From-Where)

'выбрать ход'(Position, black, Go): -

/* находим список всех позиций-преемников данной Position

и выбираем среди них позицию с большей оценкой */

'позиции-преемники'(Position, black, Sons),

'позиция с лучшей оценкой'(Sons, P),

'ходить'(Go, Position, P).