зима солнечно отличное зима солнечно хорошее зима пасмурно отличное весна пасмурно плохое

на каток в гости в гости в бар

В этих четырёх строках встречаются только три различных значения V - накаток , вгости и вбар . Вероятность встретить значение накаток равна 1/4 (встретилось в одном случае из четырёх). Аналогично, р( В гости ) = 1/2, р( в бар ) = 1/4. Таким образом,

Info(T) = -4 * (1/4 * log 1/4 + 1/2 * log 1/2 + 1/4 * log, 1/4) = 4 * (1/2 + 1/2 + 1/2) = б

Чем сильнее варьируется значение V во множестве, тем больше энтропия. Если всем элементам множества сопоставлено одно и то же значение V ( в бар , например), то энтропия равна нулю (поскольку p(V) = 1, а log 1 = 0).

Значение Inf о (Т) (энтропия множества Т, разбитого на подмножества с помощью атрибута X) вычисляется несколько сложнее:

1=1

Здесь Т Т2,Т - это подмножества, образующиеся в результате разбиения множества Т атрибутом X (если атрибут X может принимать К раз-

личных значений, мы получим К новых подмножеств). Энтропия каждого подмножества умножается на его вклад , равный Т / Т . Чем больше рассматриваемое подмножество, тем более значима его энтропия для общего результата.

Итак, значение Gain представляет собой разность между мерой информации исходного множества и мерой информации множества после его разбиения атрибутом X.

Предположим, некоторый атрибут идеально разбивает исходное множество на подмножества, в каждом из которых встречается только одно значение V. Таким образом, Info(T) = О, и значение Gain максимально.

Описанная методика является жадной , выбирая на каждом шаге наилучшее разбиение (даже если это удачное разбиение впоследствии приведёт к десяти неудачным).

6.2. САМООБУЧАЮЩИЕСЯ ПРОГРАММЫ

6.2.1. Самообучающиеся крестики-нолики Компьютер учится на собственном опыте

Требуется создать самообучающуюся программу для игры в крестики-нолики.

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

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

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

В качестве используемого атрибута при очередном разбиении множества ситуаций Т на подмножества выбирается атрибут X, для которого значение

Gain = Info(T) - InfoX(T)

максимально.

Запись Info(T) обозначает меру информации (энтропию) множества Т, вычисляемую по формуле

Info(T) = - I т I * {p(V,)*logj p(V,) + p(VJ*log, p(Vp + ... + p(VJ*log p(VJ)

Здесь:

I T I - количество элементов BO множестве T;

v, v, - различные значения результата V, встретившиеся во множестве,

p(v.) - вероятность встретить значение v..

Поясню сказанное на примере. Допустим, разбиваемое множество содержит строки:

Рис 6.5. Крестики-нолики: типичная игровая ситуация

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

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

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

Разумна идея поощрять или наказывать не только последний ход, непосредственно приведший к победе или поражению, но и всю игровую стратегию, то есть все ходы, предшествующие победному. Можно предложить простую методику Вес хода, выбранного на предыдущем шаге, повышается (в случае победы компьютера) на значение LearningStep*StepCoeff, где значение StepCoef f лежит в интервале от нуля до единицы. Вес предшествующего ему хода увеличивается на LearningStep*StepCoeff и так далее.

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

вес первого: вес второго: вес третьего: вес четвёртого:

+ LearningStep*StepCoeff + LearningStep*StepCoef f* + LearningStep*StepCoeff + LearningStep

Поскольку значение StepCoef f меньше единицы, веса более ранних ходов слабее меняются в процессе обучения.

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

Важная часть задания - исследование процесса обучения. Требуется вывести динамику побед/ничьих/поражений за время сыгранных N партий (где N может варьироваться от десятков до сотен). Можно запрограммировать вторую процедуру, играющую ноликами, и свести программы друг с другом. Вторая процедура может быть необучаемой (то есть всегда использовать рандомную стратегию).

Решение

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

Начнём с описания глобальных объектов и пары служебных функций:

const int InitWeight = 100; начальный вес

const int PrecCoeff =50; точность генератора случайных чисел const double StepCoeff = 0.65; коэффициент обучения const int LearningStep =20; шаг обучения

. Игровое поле (3x3, построчно). Может содержать три вида символов - крестик (х), нолик (о) и пробел char GaineField[9] ;

текущее состояние игры: выиграли крестики, выиграли нолики,

ничья, игра ещё не завершилась

enum OUTCOME { Xs, Os, DRAW, UNFINISHED };

OUTCOME GetOutcomeO

все восемь победных расположений трёх символов игрока int V[8][3] = { {О, 1. 2}, {3, 4, 5), {6, 7, 8), {О, 3, 6},

{1, 4, 7), {2, 5, 8). {О, 4, 8), {2, 4, 6} };

если обнаружена победная комбинация for(int i = 0; i < 8; i++)

if(GameField[V[i][0]] == GameField[V[i][1]]

GameField[V[i][0]] == GameField[V[i][2]]

GameField[V[i][0]] != )

ScSc

Вес - это просто целое число, в начале работы программы равное InitWeight (выбор initWeight остаётся за вами; можно посоветовать взять значение около 100) для каждого возможного хода. Если какой-то ход ведёт к победе компьютера, его вес следует повысить.

Рассмотрим типичную ситуацию, возникшую в игре (рис. 6.5).

Компьютер может поставить крестик в любой из трёх свободных углов. Первоначально никаких предпочтений не существует, вес каждого хода равен InitWeight.

Предположим теперь, что компьютер случайным образом выбрал правый нижний угол и победил в игре. Теперь надо поощрить использование этого хода, увеличив его вес на значение LearningStep (разумное его значение лежит в диапазоне 10...30).

вывести текущее состояние игрового поля

void PrintFieldO

cout GameFicld[0) 1 GameField[1] I cout GameFicld[3 I GaineField[4] I cout GameField[6] I GameField[7] I cout endl; }

GairieField[2] endl GameField[5] endl GameField!8] endl

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

состояние игрового поля

struct TField

char Field[9];

конструктор: просто скопировать текущее содержимое реального поля

TFieldO { сору (GameField, GameField + 9, Field); }

для объединения в коллекцию требуется функция упорядочивания

bool operator<(const TFieldb rhs) const {

return lexicographical compare(Field, Field +9,

rhs.Field, rhs.Field + 9);

матрица весов struct TWeight {

int Weight[9];

изначально заполняется значением веса InitWeight TWeightO { fill(Weight, Weight + 9, InitWeight); }

Для полноценного экспериментирования нам потребуется поддержка трёх видов игроков:

игрок-человек (ходы вводятся с клавиатуры);

компьютерный игрок, использующий рандомную стратегию;

обучаемый компьютерный игрок.

Единый интерфейс для всех типов игроков обеспечивается абстрактным базовым классом Player:

class Player {

protected:

используемый игроком символ (крестик или нолик) char Symbol;

public:

Player(char symbol) : Symbol( symbol) {}

сделать очередной ход

virtual void MakeMoveO =0;

выполнить одну итерацию обучения

virtual void Learn(int) {}

Функция-член для обучения реально нужна только в классе обучаемого компьютерного игрока (в остальных местах она предназначена лишь для совместимости интерфейсов).

Классы первых двух типов игроков очень просты:

public Player

игрок-человек class HumanPlayer {

public:

HumanPlayer(char symbol)

Player( symbol) {}

virtual void MakeMoveO {

int Cell;

прочитать номер клетки и сделать ход (корректность хода не проверйется) cin Cell;

GameField[Cell] = Symbol;

компьютерный игрок, использующий рандомную стратегию class RandomPlayer : public Player

return GameField[V[i][0]] == х ? Xs : Os;

если победных комбинаций не обнаружено, то результат зависит от наличия на игровом поле пробельных символов (если пробелов нет, игра завершилась ничьей) return (find(GameField, GameField +9, ) == GameField + 9)

? DRAW : UNFINISHED;