ITCS - Популярно об ИИ. Сезон 2. Программирование шахмат и логических игр-2 - РАЗРАБОТКА КОМПЬЮТЕРНЫХ ИГР
Сегодня: Понедельник, 05.12.2016, 23:35 (МСК)| Здравствуйте, Гость| Мой профиль | Регистрация | Вход | RSS

Работаем с VirtualDub

Спецэффекты в Cinema4D

Blu-ray приводы для ПК

Google Chrome. Таким должен быть браузер

Программы — виртуальные гитаристы
Главная » РАЗРАБОТКА КОМПЬЮТЕРНЫХ ИГР

Популярно об ИИ. Сезон 2. Программирование шахмат и логических игр-2

29.08.2010

Наша жизнь по мере своего развития — это процесс преобразования дерева поиска в граф:), в котором есть частые повторения ситуаций, но при этом к одной и той же ситуации можно прийти совершенно различными путями. На этом философские возлияния закончим. Включаем деструктор и… 


Гимнастика для ума

 
Вообще, математика — вещь весьма занятная, особенно, если учесть, что в ней много интересных направлений. 

Не так давно ваш покорный слуга занялся «параллельной» арифметикой для гимнастики ума. И чтобы как-то разбавить довольно сложный материал по программированию шахмат, вначале обсудим эту интересную тему. Тем более, что иногда требуется хорошая разминка мозга, прежде чем изучать что-то сложное. 

Итак, под «параллельной» арифметикой подразумевается замена арифметических операций более простыми либо идентичными, которые явно не угадываются. В качестве основы возьмем ряд нечетных чисел (см. таблицу). Представим его в виде одномерного массива odd, в котором хранятся нечетные числа:   


Элементы массива нечетных чисел odd[...]

Соответствующие им нечетные числа

Сумма элементов массива от odd[1] до odd[текущее]

[1]

1

1

[2]

3

4

[3]

5

9

[4]

7

16

[5]

9

25

[6]

11

36

[7]

13

49

[8]

15

64

[9]

17

81

[10]

19

100

[11]

21

121

[12]

23

144

[13]

25

169

[14]

27

196

[15]

29

225


В таблице крайняя левая колонка — это порядковые номера (индексы) элементов, средняя колонка — значения чисел (это ряд нечетных чисел), правая сделана для удобства, в ней вычислены суммы всех элементов от первого до текущего. Многие отметят, что эти суммы равны квадратам действительных чисел, так оно и есть: 1+3=4 (2 в квадрате), 1+3+5=9 (3 в квадрате) и так далее. Это так. Причем эти числа соответствуют нашим индексам. 
Поэтому можно написать формулу 

n x n=сумма(odd[1]…odd[n]);
 
и она будет верна. Математический знак суммы я заменил на слово «сумма», чтобы было несколько удобнее читать, а во-вторых, мои материалы постоянно кто-то «заимствует» в сети, и если я там пишу формулы, то в результате преобразований и всевозможных перипетий они принимают чуднЫе формы.

Чем примечателен переход от умножения к сложению? В принципе, это многое облегчает. Причем у «машины» такой арифметической операции как умножение нет, есть сложение. И набирая знак «умножить», если объяснять простыми словами, вы подразумеваете вызов соответствующей подпрограммы, которая переведет умножение в сложение. То есть, вы пишете 2*5, и это потом переведется в 2+2+2+2+2. Переход к сложению, иногда оптимизация с переменой мест множителей (2*5=5*2=5+5) — это отдельные операции.

Поэтому программисты старого поколения, которые привыкли бороться за ресурсы и оптимизацию скорости, избегают использовать умножение в простых случаях, заменяя его суммами. То есть, вместо a1=a*2, они практически всегда напишут a1=a+a;. Для процессора «легче» считать сумму, чем умножение. 

Вариант получения квадратов путем использования нечетных чисел в рамках первой выведенной формулы хуже, чем обычный переход к сложению. Потому как 3*3 в стандартном варианте будет восприниматься как 3+3+3, а в нашем случае 1+3+5, то есть количество операций сложения не будет меньшим, к тому же нам нужно еще определиться с нечетными числами, поместить их в массив и так далее.

То есть, выгоды это не принесет. 

Также начав крутить этот алгоритм можно вывести новые подобные формулы: 
  
n x (n+2)=сумма(odd[2]…odd[n+1]);
n x (n+4)=сумма(odd[3]…odd[n+2]);
n x (n+6)=сумма(odd[4]…odd[n+3]);
n x (n+8)=сумма(odd[5]…odd[n+4]);

Другими словами, 8*12 вызовет сумму (смотрим таблицу) элементов от третьего до десятого, а именно, 5+7+9+11+13+15+17+19. В принципе, и здесь явного выигрыша нет. Тем более появится много проблем с переводом индексов, как вы можете увидеть: с левой стороны формул приращения второго множителя идут с шагом +2, а с правой индексы растут — +1. В результате мы получаем много путаницы, хотя математически все интересно. 

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

Мои варианты таблицы умножения представлены ниже. Вы, кстати, можете сами в качестве эксперимента попробовать или оптимизировать написанное, или создать свои варианты, их на самом деле можно найти много. Итак, таблица умножения:
  • Для двух:
2 x k=odd[k]+1;
  • Для трех:
3 x k=odd[k]+k+1;
  • Для четырех
4 x k=odd[k]+odd[k+1];
  • Для пяти:
5 x k=odd[k]+ odd[k+1] +k;
  • Для шестерки:
6 x k=odd[k]+odd[k+1]+odd[k+2]-3
  • Для семи:
7 x k=odd[k]+odd[k+1]+odd[k+2]+(k-3);
  • Для восьми:
8 x k=odd[k]+odd[k+1]+odd[k+2]+odd[k+3]-8;
  • Для десяти:
10 x k=odd[k]+odd[k+1]+odd[k+2]+odd[k+3]+odd[k+4]-15;
  • Для двенадцати:
12 x k=odd[k]+odd[k+1]+odd[k+2]+odd[k+3]+odd[k+4]+odd[k+5]-24.

И так далее. Теперь давайте повторим нашу операцию с умножением 8 на 12. Смотрим формулу: 8 x k=odd[k]+odd[k+1]+odd[k+2]+odd[k+3]-8; и выбираем элементы из таблицы:
8 x 12 = 23+25+27+29-8 = 96. Пять операций сложения! Это уже выигрыш. Хотя мы используем массив плюс к этому обращаемся к его элементам. То есть фактического выигрыша нет. При обычном методе в рамках оптимизации, то есть, 8 и 12 поменяются местами, будет 8 операций сложения. 

Но это не все, оптимизировать можно и дальше. Например, сумма odd[k]+odd[k+1] это тоже самое, что и 2*odd[k]+2 (пока используем умножение просто для понимания, потом его следует заменить на суммы). В одном из вариантов оптимизации можем воспользоваться правилом:
 
2*odd[k]=odd[2*k]-1;

хотя это одна из утопичных веток оптимизации, как потом выяснится. 
Таким образом:

odd[k]+odd[k+1]=odd[2*k]+1;
odd[k]+odd[k+1]+odd[k+2]=3*odd[k]+2+4=odd[3*k-1]+6=odd[3*k]+4;
odd[k]+odd[k+1]+odd[k+2]+odd[k+3]=4*odd[k]+2+4+6=odd[4*k]+9;

Меняем ситуацию с таблицей умножения:

  • Для двух:
2 x k=odd[k]+1;
  • Для трех:
3 x k=odd[k]+k+1;
  • Для четырех
4 x k= odd[k*2]+1;
  • Для пяти:
5 x k= odd[k*2]+k+1;
  • Для шестерки:
6 x k= odd[k*3]+1;
  • Для семи:
7 x k= odd[k*3]+k+1;
  • Для восьми:
8 x k= odd[k*4]+1;

… и так далее, зависимость вы поняли, то есть, коэффициент перед k в индексе — это целое число в результате деления первого множителя на два (n/2). Если делится без остатка, то прибавляется 1, если с остатком, то прибавляется k+1. То же самое, что и определять чет/нечет.  

Конечно, умножение/деление на 2,4,8 (2 в степени) и т.п. лучше делать за счет битовых сдвигов. В общем, что-то получилось. Причем в последнем варианте вывода формул мы практически приблизились к обычному умножению, учитывая то, что нам нужно будет заполнять массив:). 

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


NegaMax, полный перебор


В принципе, реализации самого движка, считающего и сортирующего возможные перемещения могут быть различными. Также есть явная зависимость от языка, в котором вы программируете. То есть, написание шахмат на Java отличается от создания идентичной программы в Visual Basic. Большинство старых алгоритмов написано на С/С++. 

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

Итак, допустим, мы написали функции GenerateAllMoves() (SortMoves() пока не используем), MakeMove(), UnMakeMove() и EvaluatePosition() (см. прошлый материал серии). До этого, конечно, нужно определиться со структурой данных перемещения, в которой указывается фигура и ее новые координаты. Назовем ее PMove. Случаи взятия регистрируются в функции MakeMove(), а все варианты перемещений генерируются в GenerateAllMoves().

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

PMove Search(int score)
{
//лучший ход
PMove bestMove;
//получаем все перемещения
PMove move = GenerateAllMoves();
while (move) {
MakeMove(move);
int tmp_score= EvaluatePosition();
UnMakeMove(move);
if (tmp_score>score) 
bestMove=move;
move=move->next;
}
return bestMove;
}

Вызываем функцию строкой Search(-100000), где в качестве числа указываем какое-нибудь недостижимое минимальное значение. Что мы получили? В рамках цикла мы перебрали все возможные варианты ходов, вызвали для каждого из них оценочную функцию EvaluatePosition(), получили результат — лучший ход, точнее, полуход. В простейшем варианте Search() может стать частью нашей SortMoves(). Но пока «мы только мечтаем»:), тем более, что такой вариант не подходит.

Также мы можем видоизменить код, вынеся в качестве ответа не bestMove, а score, то есть максимальную оценку.

int Search(int score)
{
//получаем все перемещения
PMove move = GenerateAllMoves();
while (move) {
MakeMove(move);
int tmp_score= EvaluatePosition();
UnMakeMove(move);
if (tmp_score>score) 
score=tmp_score;;
move=move->next;
}
return score;
}

С одной стороны вам может показаться, что ничего сложного нет, но разберитесь внимательно, потому как дальнейшее будет трудновато читать. Что в данном случае нам возвращает функция? Лучший результат, максимальный из всех возможных в рамках одного полухода.

А можно ли сделать «качели», когда функция считает полуход белых, потом выбирает лучший вариант из ответных перемещений черных, и если этот вариант сильно повлияет на ситуацию белых, функция пойдет считать дальше? 

В принципе, это можно делать и без рекурсий. Каким образом? В шестой части материала «Lua для игр и не только» мы уже пробовали решать сложную задачу, заменив рекурсию циклами. Здесь будет примерно также.

Мы внесем разнообразие в функции GenerateAllMoves() и EvaluatePosition(). А именно поставим в качестве входного аргумента булеву переменную, true в которой будет означать расчеты для белых, а false — для черных. 

Итак, рассчитываем 2 полухода, функцию для второго ставим перед первой:

//второй полуход
//черные
int SearchBlack(int score)
{
PMove move = GenerateAllMoves(false);
while (move) {
MakeMove(move);
int tmp_score= EvaluatePosition(false);
UnMakeMove(move);
if (tmp_score>score) 
score=tmp_score;;
move=move->next;
}
return score;
}

//первый полуход
//белые
int SearchWhite(int score)
{
PMove move = GenerateAllMoves(true);
while (move) {
MakeMove(move);
//главные строки
int tmp_score=EvaluatePosition(true);
tmp_score = tmp_score –
SearchBlack(-100000);
//
UnMakeMove(move);
if (tmp_score>score) 
score=tmp_score;
move=move->next;
}
return score;
}

Итак, мы делаем вызов SearchWhite(-100000), указав в качестве значения аргумента недосягаемый минимум. Функция ведет себя фактически также, как и ранее описанная Search. Разница только в оценке позиции. В ее рамках, сделав ход и изменив ситуацию на доске, мы вызываем оценочную функцию, но после мы обращаемся к идентичной функции SearchBlack для черных. Она достаточно быстро вычисляет возможный максимум ответа на этот ход, и отдает его в качестве возвращаемого значения. После наша оценка хода будет складываться из разницы между вычисленной оценкой для белых в рамках этого хода и максимумом ответа на него черных. Другими словами, на один полуход белых мы просчитали 40 передвижений черных. В результате, если у нас среднее количество возможных перемещений равно 40, то полным перебором мы обработали 40х40, т.е. 160 ситуаций. 

Если бы мы не считали ответ черных, то компьютер бы, например, явно подумал: «А почему бы мне не сбить ферзем защищенную ладью — самый выгодный ход!». И действительно функция оценки полухода даст на такую операцию ответ +500 в сторону белых только материальной оценкой. Дальше, ведь, ситуация не просчитывается. А когда мы начинаем считать ответ черных, то понимаем, что в результате статические потери составят -400 после сбития ферзя. Поэтому, чем глубже копаем, тем лучше. 

Поиск в глубину практически всегда делается с помощью рекурсии. Допустим, вы еще сможете написать код для расчета в глубину 4,5,6 с помощью циклов, при этом нужна оптимизация и уход от полного перебора, потому как 40 в шестой степени, это, извините, 4 млрд операций. То есть, написать-то напишите, только работать будет это все с большим треском, а, скорее и работать не будет, потому как глубина 6 для полного перебора в шахматах — это современный максимум для вычислительных систем. 

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

int Search(bool color, int Depth)
{
//оценка конечной точки
if (Depth == 0) 
return EvaluatePosition(color);
int score=-100000;
PMove move= GenerateAllMoves(color);
while(move) {
MakeMove(move);
int tmp_score=
-Search(color?false:true, Depth-1, score);
UnMakeMove();
if (tmp_score>score) 
score = tmp_score;
move=move->next;
}
return score;
}

Вызываем так: Search(true, 4). Если мы указали глубину 4 (4 полухода) во время чего может состояться например, размен фигур, функция оценки вызывается для окончания 4 этапа. То есть, если у белых окажется, например, на одного коня больше, и мы берем в учет только материальную оценку (позиционную отключим), то нам будет выдан результат 300, если у белых будут потери, например, ладьи, то мы получим результат минус 500. 

В рамках данного алгоритма, как и в варианте с циклами, происходит полный перебор всех ситуаций (перемещений), и количество расчетов растет экспоненциально по закону W в степени D, где W — это среднее количество передвижений из одной позиции, а D — глубина. 

Данный рекурсивный алгоритм — одна из разновидностей NegaMax (вернее, это и есть NegaMax). Теперь разберемся со знаками — система оценок инвертирована. То есть для белых максимум высчитывается с одним знаком, для черных — с обратным. Это нам потом пригодится для alpha-beta.


Примечания по программированию


В варианте рекурсии мы вставили наш минимум (-100000) в код функции. Конечно, для начинающих немного трудно понять, что при каждом рекурсивном вызове функции Search мы будем иметь дело с разными переменными score. Об этом мы писали в специальном материале серии, говоря о теме рекурсии, а именно, каждая функция имеет свое определение, но есть и отдельное понятие активации функции — особого объекта данных, возникающего при вызове функции на базе ее определения. То есть, по существу, мы вызываем данную функцию как стороннюю (относиться нужно также), и все объявленные внутри ее переменные, если нет специального указания, являются локальными и действуют только в ее рамках. Если говорить более техническим языком, когда функция обращается сама к себе, в стеке выделяется память для новых переменных и параметров, и код функции с самого начала начинает выполняться с этими новыми(!) переменными. 

Второй момент… многие заметили строку color?false:true. Это тернарный оператор «?», о котором редко пишут в сериях книг «для чайников», и, в принципе, я избегаю его применять в рамках статей, потому как понятно не всем, но здесь он позволяет не раздувать код. «?» — замена конструкции if-then-else. Например, if(a>b) x=10; else x=20; эквивалентно записи x=(a>b)?10:20; А в нашем случае мы даже не вписывали левую часть — незачем вводить лишние переменные, поскольку результат color?false:true сообщается в качестве значения аргумента для следующей активации функции и там сохранится в переменной color. 

Кристофер

Перепечатка материалов или их фрагментов возможна только с согласия автора






Всего комментариев: 0
Добавлять комментарии могут только зарегистрированные пользователи.
[ Регистрация | Вход ]
Ассоциация боевых роботов
Рекомендуем...
Новости

Разделы

Опросы

Какой язык программирования вы считаете наиболее актуальным сегодня?
Всего ответов: 308

Друзья

3D-кино






Найти на сайте:








Об авторе       Контакты      Вопрос-ответ        Хостинг от uCoz