Поготовка
Примем следующие правила:
- Агент ходит первым и играет «крестиками».
- Агент будет принимать только решения имеющие максимальную ценность.
- С 5% вероятностью агент будет принимать зондирующие решения.
- Только в случае выигрыша агента, он получает вознаграждение.
Следующим этапом необходимо подготовить функцию ценности для агента. В нашем случае, функцией ценности будет являться таблица состояний игры, в которой значение от 0 до 1 будет указывать что то или иное состояние «лучше» другого. Изначально зададим в нашей таблице что все выигрышные комбинации (три крестика в ряд, столбец или по диагонали) дают вероятность равную 1. Аналогично, всех состояний с тремя нулями — 0. Для всех прочих состояний вероятность — 0,5.
С целью упрощения составления таблицы вероятностей примем, что всего состояний. Конечно же, половина этих комбинаций невозможна, но и оптимизации кода в целях не стояло.
float V[19683];
//-------
void setV(int a1,int a2,int a3,int b1,int b2,int b3,int c1,int c2,int c3,float v)
{
int num;
num = ((((((((a1*3)+a2)*3+a3)*3+b1)*3+b2)*3+b3)*3+c1)*3+c2)*3+c3;
V[num] = v;
}
//-------
for (int i1=0;i1<3;i1++)
for (int i2=0;i2<3;i2++)
for (int i3=0;i3<3;i3++)
for (int i4=0;i4<3;i4++)
for (int i5=0;i5<3;i5++)
for (int i6=0;i6<3;i6++)
for (int i7=0;i7<3;i7++)
for (int i8=0;i8<3;i8++)
for (int i9=0;i9<3;i9++) {
setV(i1,i2,i3,i4,i5,i6,i7,i8,i9,0.5);
if (i1==i2 && i2==i3 && i3==1) setV(i1,i2,i3,i4,i5,i6,i7,i8,i9,1);
if (i4==i5 && i5==i6 && i6==1) setV(i1,i2,i3,i4,i5,i6,i7,i8,i9,1);
if (i7==i8 && i8==i9 && i9==1) setV(i1,i2,i3,i4,i5,i6,i7,i8,i9,1);
if (i1==i5 && i5==i9 && i9==1) setV(i1,i2,i3,i4,i5,i6,i7,i8,i9,1);
if (i7==i5 && i5==i3 && i3==1) setV(i1,i2,i3,i4,i5,i6,i7,i8,i9,1);
if (i1==i4 && i4==i7 && i7==1) setV(i1,i2,i3,i4,i5,i6,i7,i8,i9,1);
if (i2==i5 && i5==i8 && i8==1) setV(i1,i2,i3,i4,i5,i6,i7,i8,i9,1);
if (i3==i6 && i6==i9 && i9==1) setV(i1,i2,i3,i4,i5,i6,i7,i8,i9,1);
if (i1==i2 && i2==i3 && i3==2) setV(i1,i2,i3,i4,i5,i6,i7,i8,i9,0);
if (i4==i5 && i5==i6 && i6==2) setV(i1,i2,i3,i4,i5,i6,i7,i8,i9,0);
if (i7==i8 && i8==i9 && i9==2) setV(i1,i2,i3,i4,i5,i6,i7,i8,i9,0);
if (i1==i5 && i5==i9 && i9==2) setV(i1,i2,i3,i4,i5,i6,i7,i8,i9,0);
if (i7==i5 && i5==i3 && i3==2) setV(i1,i2,i3,i4,i5,i6,i7,i8,i9,0);
if (i1==i4 && i4==i7 && i7==2) setV(i1,i2,i3,i4,i5,i6,i7,i8,i9,0);
if (i2==i5 && i5==i8 && i8==2) setV(i1,i2,i3,i4,i5,i6,i7,i8,i9,0);
if (i3==i6 && i6==i9 && i9==2) setV(i1,i2,i3,i4,i5,i6,i7,i8,i9,0);
}
Ход игры
Оппонетном будет являться человек, который соответственно будет играть за нолики и периодически поддаваться. В ходе игры будет происходить изменение ценности ее состояний. Для того, чтобы правильно оценить действия агента, необходимо записывать последовательность тех состояний, которые он выбрал и по окончании игры перерасчитать их. Формула расчета ценности V(s) будет иметь следующий вид:
,
где А — размер шага, влияющего на скорость обучения. V(s') — ценность действия по окончанию игры (1 — если выиграл, 0 — иначе).
Размер шага влияет на то, будет ли меняться стратегия оппонента или нет. Если необходимо учитывать изменчивость стратегии, то необходимо оставить размер шага константой. Иначе при уменьшении шага до нуля агент остановит свое обучение.
Использование зондирующих ходов (не имеющих высокую ценность) позволяет проверить состояния, которые ввиду высокой ценности других ходов никогда бы не исполнились, что дает небольшой шанс на изменение стратегии в выигрышную сторону.
void stepAI(void)
{
int flag;
c_var=0;
for (int i=0;i<19683;i++)
{
flag=0;
readMap(i);
for (int j=1; j<10;j++)
if (rm[j]!=m[j])
if ((m[j]==0) && (rm[j]==1)) flag++;
else flag+=2;
if (flag==1) {
var[c_var]=i;
c_var++;
}
}
float v_max;
int v_num_max;
if (random(100)<5) v_num_max=random(c_var);
else {
v_max = V[var[0]];
v_num_max = 0;
if (c_var>1)
for (int i=1;i<c_var;i++)
if (V[var[i]]>v_max)
v_num_max = i;
}
steps++;
steps_m[steps]=var[v_num_max];
readMap(var[v_num_max]);
for (int i=1;i<10;i++)
m[i]=rm[i];
paintMap();
}
В выше расположенном коде происходит отбор возможных ходов (состояния в которых элементы идентичны текущему состоянию поля, а также присутствует еще один крестик). Затем из полученных состояний выбирается либо произвольный ход (с вероятностью 5%), либо «жадный» ход (с максимальной ценностью). По окончании выбора, данный ход записывается в отдельный массив сделанных ходов.
По окончании игры происходит как уже сказано перерасчет ценности сделанных ходов.
void learnAI(int res)
{
for (int i=0;i<steps;i++)
V[steps_m[i]] += A * (res - V[steps_m[i]]);
A -= 0.01;
}Итог
> Программа и проект в С++ Builder 6
В данном примере был кратко рассмотрен один из аспектов обучения с подкреплением. Если обычно агент контактирует со средой, то в данном примере обучение осуществлялось с игроком-противником. Хотя этот пример довольно прост, может показаться что данный метод на других примерах будет очень ограничен чем это есть на самом деле.
Используемая литература
Обучение с подкреплением/ Р.С.Саттон, Э.Г.Барто — Москва: БИНОМ. Лаборатория знаний, 2014
Комментарии (13)
ginkage
02.05.2017 11:34+4Глаза болят…
«Выйгрышный», «выйграл», «выйгрыш»… Пожалуйста, напишите нормально.
MonteKarlo
02.05.2017 12:46честно, видимо это заблуждение всей моей жизни, всегда считал что «выигрыш» пишется через «й»
maxzuber
02.05.2017 13:04+2У Мартина Гарднера, и не только у него, по-моему, приводилась ссылка на статью 1961 года о построении обучающегося «автомата» на спичечных коробках. Есть в сети на русском языке, поищите MENACE (Mathbox Educable Naughts and Crosses Engine).
migs911
02.05.2017 13:59+59 циклов, по циклу на каждый ход…
Боже, а что бы вы сделали, если бы было поле 5х5? а если 10х10?
Нельзя так, а то попадёте на доску почёта вот этого сайта.MonteKarlo
02.05.2017 14:01-2цель была изначально сделать не оптимизируя. понимаю что не эффективно, не практично. но как иначе если нужно делать определенные выборки. приму любые предложения. да и к тому же это всего лишь инициализация и делается всего один раз при запуске.
charypopper
03.05.2017 11:51+1Здравствуйте.
Можно было бы сделать рекурсию, и использовать массив параметров. При погружение наращивать значения параметра с индексом i — где i глубина. В конце рекурсии выполнять то, что у вас написано в теле вложенного цикла.
Данный способ будет помедленнее(из-за вызовов и передачи параметров), но короче в записи.
Еще в C++ есть директива inline, которая (возможно) развернет рекурсию до определенной глубины(зависит от компилятора), и получится подобное вашим циклам.
С точки зрения подачи материала, я бы привел код Вами написанный, затем сказал — что это все круто, пока циклов 2, и можно сделать так, как я описал выше.alexeykuzmin0
03.05.2017 14:31Там все и так уложено в плоский массив, так что логику пересчета из индекса в набор индексов стоило бы инкапсулировать в отдельном классе, который может быть приведен к (и из) как int, так и std::array<std::array<int, 3>, 3>, и использовать один-единственный цикл от 0 до общего числа состояний доски — 1.
На мой взгляд, так будет лучше, чем при использовании рекурсии и явно гораздо лучше, чем девять вложенных циклов.MonteKarlo
03.05.2017 15:13Спасибо за идею! Размышляю уже второй день как все можно было бы организовать, но особых мыслей не было. Пришел только к следующему выводу: надо было всем сосотояниям указать одинаковое значение больше 1 с целью перебора всех возможных состояний в процессе обучения. Тогда можно было бы вложить в один цикл.
alexeykuzmin0
А можно хотя бы отступы в коде расставить? Читать же невозможно.
MonteKarlo
пробовал расставить переносы в первом коде, но после сохранения все пропадает, в следующих статьях постараюсь разобраться
GlukKazan
Используйте тег source:
