Наша жизнь по мере своего развития — это процесс преобразования дерева поиска в граф:), в котором есть частые повторения ситуаций, но при этом к одной и той же ситуации можно прийти совершенно различными путями. На этом философские возлияния закончим. Включаем деструктор и…
Гимнастика для ума
Вообще, математика — вещь весьма занятная, особенно, если учесть, что в ней много интересных направлений.
Не так давно ваш покорный слуга занялся «параллельной» арифметикой для гимнастики ума. И чтобы как-то разбавить довольно сложный материал по программированию шахмат, вначале обсудим эту интересную тему. Тем более, что иногда требуется хорошая разминка мозга, прежде чем изучать что-то сложное.
Итак, под «параллельной» арифметикой подразумевается замена арифметических операций более простыми либо идентичными, которые явно не угадываются. В качестве основы возьмем ряд нечетных чисел (см. таблицу). Представим его в виде одномерного массива 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.
Кристофер Перепечатка материалов или их фрагментов возможна только с согласия автора
| 
