public:

RandoinPlayer (char syinbol) : Player ( synibol) {}

virtual void MakeMoveO {

vector<int> v;

запомнить номера всех пустых клеток for(int i = 0; i < 9; i++) if(GameField[i] == ) v.push back(i); записать символ в случайно выбранную пустую клетку GameField[v[random(v.sizeO )] ] = Symbol;

Класс обучаемого игрока содержит несколько дополнительных закрытых функций-членов и полей данных:

class SmartPlayer : public Player {

private:

элемент истории текущей игры

struct HistoryElement

map<TField, TWeight>::iterator Situation; позиция

int Move; сделанный ход

HistoryElement(map<TField, TWeight>::iterator s, int m)

: Situation(s), Move(m) {}

stack<HistoryElement> History; история сделанных ходов map<TField, TWeight> Database; полная база знаний игрока

поиск в базе знаний текущей игровой ситуации map<TField, TWeight>::iterator GetSituation();

генератор случайных чисел, учитывающий матрицу весов int GetWRandom(map<TField, TWeight>::iterator s);

public:

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

virtual void MakeMoveO; void Learn(int step);

Обучаемый компьютерный ихрок действует следующим образом. База знании Database сопоставляет каждой известной игроку ситуации некоторую

матрицу, указывающую веса (то есть предпочтительность выбора) возможных ходов. Изначально база знаний, естественно, пуста.

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

Все ходы игрока SmartPlayer в текущей партии записываются в стек History. В процессе обучения, которому соответствует вызов функции Learn (), записанные ходы будут поощряться или наказываться.

Остановимся поканаэтомирассмотримфункции-члены Get Situation (), GetWRandom() и MakeMove():

найти в базе знаний ситуацию, сложившуюся на игровом поле map<TField, TWeight>::iterator SmartPlayer::GetSituation() {

поиск в базе объекта TField, инициализированного содержимым GameField map<TField, TWeight>::iterator p = Database.find(TField()); если объект не найден if(p =- Database.end()) {

TWeight w; создать новую матрицу весов

for(int i = 0; i < 9; i++)

if(GameField[i] != ) если клетка игрового поля занята W.Weight[i] =0; ход невозможен (его вес равен нулю)

Database[TField()] = w; записать текущую ситуацию в базу return Database.find(TField());

return p;

возвращает случайное число, соответствующее матрице весов s->second

int SmartPlayer::GetWRandom(map<TField, TWeight>::iterator s)

найти сумму всех весов матрицы

int sum = accumulate{s->second.Weight, s->second.Weight +9, 0);

если все ходы одинаково плохи (их веса равны нулю)

if(sum == 0)

выбираем первую попавшуюся пустую клетку

return find(GameField, GameField +9, ) - GameField;

vector<int> coords; генерация случайного числа

for (int i = 0; i < 9; i++) (см. комментарий после

листинга)

fill ri (back inserter(coords), PrecCoeff*s->second.Weight[i] / sum, i); return coords[random(coords.size())];

сделать очередной ход void SmartPlayer::MakeMoveO {

извлечь ситуацию из базы знаний

map<TField, TWeight>::iterator s = GetSituation();

int move = GetWRandom(s);

сгенерировать ход

GameField[move] = Symbol; сделать ход

History.push(MistoryElement(s, move)); запомнить ход d истории

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

о 50 80 200 О 70 100 100 100

Действия алгоритма логически (хотя на уровне исходного кода всё выглядит проще) делятся на четыре шага. На первом шаге производится нормализация весов, то есть каждый вес делится на сумму всех весов таблицы (в данном случае 700):

о 0.07 0.11 0.29 О 0.1 0.14 0.14 0.14

На втором пшге полученные элементы умножаются на значение Р г е сСое f f, представляющее собой точность генератора случайных чисел. Дробная часть результата отбрасывается. Чем больше PrecCoef f, тем лучше генерируемые числа будут соответствовать весам из таблицы. За точность, однако, приходится расплачиваться скоростью работы.

Допустим, PrecCoef f = 50. Тогда таблица после умножения приобретёт следующий вид:

о 3

14 О 7 7

На третьем этапе генерируется массив, содержащий столько значений К, сколько записагю в К-й клетке матрицы весов (значение К лежит в пределах от нуля до восьми включительно):

1112222233333333333333555556666666 777777788888888

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

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

Последний ход поощряется или наказывается на полную катушку : соответствующий вес в матрице весов изменяется на значение LearningStep. Затем действие повторяется для предьщущего хода, но на сей раз вес изменится на меньшее по модулю значение LearningStep * StepCoef f. Для следующего шага изменение окажется ещё менее существенным и так далее.

На уровне исходного кода всё выглядит ненамного сложнее:

void SmartPlayer-.: Learn (int step) {

ecnyi история ходов уже пуста if(History.empty О)

return;

итерация обучения завершена

извлечь очередной ход HistoryElement h = History.top(); History.pop();

ссылка на матрицу весов TWeight& w = h.Situation->second;

изменить вес хода w.Weight[h.Move] += step; if(w.Weight[h.Move] < 0) w.Weight[h.Move] = 0;

нижний предел веса - нуль

выполнить обучение для предыдущего хода Learn(step * StepCoeff);

Самая сложная часть работы уже позади. Осталось лишь написать функцию, отвечающую за проведение игры, и главную функцию main ():

провести одну игру между игроками Хр (крестики) и Ор (нолики) параметр Verbose указывает, следует ли выводить на экран игровое поле (во время обучения печать лишь замедляет процесс) void PlayGame(Player *Хр, Player *0р, bool Verbose)

Player *Cp[] = { Xp, Op }; номер текущего хода int move = 0;

fill(GameField, GameField +9, пока игра не закончилась while(GetOutcome() == UNFINISHED)

); очистить поле

alaUausi

сделать очередной ход Ср[move++ % 2]->MakeMove{);

при необходимости вывести игровое поле на экран if(Verbose)

PrintField();

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

(поощряем выигравщую сторону, наказываем проигравшую) if(GetOutcome() == Xs)

{ Xp->Learn(LearningStep); Op->Learn(-LearningStep); } else if(GetOutcome() == Os)

{ Xp->Learn(-LearningStep); Op->Learn(LearningStep); }

int main(int argc, char* argv[]) {

randomize();

RandomPlayer *r = new RandomPlayer(o); HumanPlayer *h = new HumanPlayer(o); SmartPlayer *s = new SmartPlayer(x);

сыграть 50000 партий между игроками s и г for(int к = 0; к < 50000; к++) PlayGame(s, г, false);

сыграть партию между s и человеком PlayGame(s, h, true);

delete s; delete h; delete r; return 0;

ol I Ixl xl I

ol lo

Ixl xl I

о I x I о

Ixl xl I

о Ixl о

Ixl xlol

olxlo Ixlx xlol

о I x ;o olxlx xlol

olxlo olxlx xl о Ix

Качество обучения определяется прежде всего значениями параметров LearningStep и StepCoef f. Я советую с ними поэкспериментировать.

После обучения в виде пятидесяти тысяч партий с рандомным игроком игрок S кое-чему способен научиться. Ниже приведена типичная партия между человеком и обученным компьютерным соперником (компьютер играет крестиками, человек - ноликами):

о I 1x1 I I

6.2.2. Самообучающаяся программа для игры в ним. Автоматический поиск выигрышной стратегии

В ним играют на доске с 12 фишками, расположенными в три ряда. Начальная позиция приведена на рис. 6.6. Игроки по очереди забирают одну или более фишек из любого ряда (брать фишки из разных рядов запрещено). Выигрывает тот, кто сделает последний ход.

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

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