Популярно об ИИ
М-да, вообще, наша жизнь по мере своего развития — это процесс преобразования дерева поиска в граф:), в котором есть частые повторения ситуаций, но при этом к одной и той же ситуации можно прийти совершенно различными путями. На этом философские возлияния закончим. Включаем деструктор и…
С интересным алгоритмом я недавно столкнулся. Он может работать только при условии 0/0=1, x/0=+бесконечность, -x/0=-бесконечность, то есть вписано условие «как можно делить на ноль». Мало того, вместо понятия «бесконечность» там указаны конкретные цифры, которые меняются в зависимости от используемого типа данных. Когда я показал это знакомому алгоритмисту, тот вошел в состояние ступора:). Правильно, такое может случиться с каждым, кто внезапно сталкивается с явлениями, приводящими к нулю здравый смысл. Вернее, то, что мы считаем здравым смыслом. Алгоритм-то работает. Я, кстати, потом посмотрел другие работы его автора, программиста-экспериментатора, нашел много нового:)))… Например, тип данных superbool, в котором есть четыре значения: true, htrue (производная от «half true», т.е. полуправда), hfalse («half false») и false. Причем это только порядковое перечисление, а приоритеты расставлены так:
1. true (3)
2. hfalse (2)
3. htrue (1)
4. false (0)
Другими словами, «полуложь» ближе к правде, а «полуправда» — ко лжи, но в то же время htrue и hfalse является серединным, но не явно осязаемым, значением диапазона true и false, они показывают направление, тяготение и т.п. Многие сразу же вспомнят пример с оптимистом и пессимистом, когда один считает, что стакан наполовину полон, а другой — что наполовину пуст. Кстати, именно здесь и можно получить объяснение, почему так расставлены приоритеты. Допустим, стакан наполняться больше не будет. В нашем случае true — полный стакан, false — пустой. То есть, оптимист врет, используя понятие «полон», потому как стакан не будет полным никогда, поэтому hfalse, в то время как пессимист ближе к реальной оценке ситуации (htrue), используя слово «пуст». Примерно так!:)
Как это применяется на практике? Допустим, несобственному персонажу в компьютерной игре нужно проскочить в полуоткрытую дверь. Так вот, если эта дверь в данный конкретный момент закрывается, то «супербулевой» переменной присваивается значение htrue, а если открывается, то hfalse. Соответственно, дверь открыта — true, закрыта — false.
Помимо этого для «половинчатых» величин написаны специальные аналогии условных операторов if-else — ifh-elseh.
ifh (door_open) поспешить; elseh подождать;
Данное нововведение мне очень понравилось, потому как исправляет многие нелицеприятные моменты нечеткой логики, минимизирует вычисления. Нечеткая логика в основном применяется для очеловечивания поведения несобственных персонажей и других подобных систем. Например, если закрываются двери лифта, а вам нужно срочно в него попасть, вы не рассчитываете, сможете ли успеть добежать до него, вы просто предпринимаете конкретное действие.
Гимнастика для ума
Вообще, математика — вещь весьма занятная, особенно если учесть, что в ней много интересных направлений.
Не так давно ваш покорный слуга занялся «параллельной» арифметикой для гимнастики ума. И чтобы как-то разбавить довольно сложный материал по программированию шахмат, вначале обсудим эту интересную тему. Тем более что иногда требуется хорошая разминка мозга, прежде чем изучать что-то сложное.
Итак, под «параллельной» арифметикой подразумевается замена арифметических операций более простыми либо идентичными, которые явно не угадываются. В качестве основы возьмем ряд нечетных чисел (см. таблицу). Представим его в виде одномерного массива.
В таблице крайняя левая колонка — это порядковые номера (индексы) элементов, средняя колонка — значения чисел (это ряд нечетных чисел), правая сделана для удобства, в ней вычислены суммы всех элементов от первого до текущего. Многие отметят, что эти суммы равны квадратам действительных чисел, так оно и есть: 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.
Продолжение следует…
Кристофер christopher@tut.by
С интересным алгоритмом я недавно столкнулся. Он может работать только при условии 0/0=1, x/0=+бесконечность, -x/0=-бесконечность, то есть вписано условие «как можно делить на ноль». Мало того, вместо понятия «бесконечность» там указаны конкретные цифры, которые меняются в зависимости от используемого типа данных. Когда я показал это знакомому алгоритмисту, тот вошел в состояние ступора:). Правильно, такое может случиться с каждым, кто внезапно сталкивается с явлениями, приводящими к нулю здравый смысл. Вернее, то, что мы считаем здравым смыслом. Алгоритм-то работает. Я, кстати, потом посмотрел другие работы его автора, программиста-экспериментатора, нашел много нового:)))… Например, тип данных superbool, в котором есть четыре значения: true, htrue (производная от «half true», т.е. полуправда), hfalse («half false») и false. Причем это только порядковое перечисление, а приоритеты расставлены так:
1. true (3)
2. hfalse (2)
3. htrue (1)
4. false (0)
Другими словами, «полуложь» ближе к правде, а «полуправда» — ко лжи, но в то же время htrue и hfalse является серединным, но не явно осязаемым, значением диапазона true и false, они показывают направление, тяготение и т.п. Многие сразу же вспомнят пример с оптимистом и пессимистом, когда один считает, что стакан наполовину полон, а другой — что наполовину пуст. Кстати, именно здесь и можно получить объяснение, почему так расставлены приоритеты. Допустим, стакан наполняться больше не будет. В нашем случае true — полный стакан, false — пустой. То есть, оптимист врет, используя понятие «полон», потому как стакан не будет полным никогда, поэтому hfalse, в то время как пессимист ближе к реальной оценке ситуации (htrue), используя слово «пуст». Примерно так!:)
Как это применяется на практике? Допустим, несобственному персонажу в компьютерной игре нужно проскочить в полуоткрытую дверь. Так вот, если эта дверь в данный конкретный момент закрывается, то «супербулевой» переменной присваивается значение htrue, а если открывается, то hfalse. Соответственно, дверь открыта — true, закрыта — false.
Помимо этого для «половинчатых» величин написаны специальные аналогии условных операторов if-else — ifh-elseh.
ifh (door_open) поспешить; elseh подождать;
Данное нововведение мне очень понравилось, потому как исправляет многие нелицеприятные моменты нечеткой логики, минимизирует вычисления. Нечеткая логика в основном применяется для очеловечивания поведения несобственных персонажей и других подобных систем. Например, если закрываются двери лифта, а вам нужно срочно в него попасть, вы не рассчитываете, сможете ли успеть добежать до него, вы просто предпринимаете конкретное действие.
Гимнастика для ума
Вообще, математика — вещь весьма занятная, особенно если учесть, что в ней много интересных направлений.
Не так давно ваш покорный слуга занялся «параллельной» арифметикой для гимнастики ума. И чтобы как-то разбавить довольно сложный материал по программированию шахмат, вначале обсудим эту интересную тему. Тем более что иногда требуется хорошая разминка мозга, прежде чем изучать что-то сложное.
Итак, под «параллельной» арифметикой подразумевается замена арифметических операций более простыми либо идентичными, которые явно не угадываются. В качестве основы возьмем ряд нечетных чисел (см. таблицу). Представим его в виде одномерного массива.
| Эл-ты массива неч. Чисел odd[…] | Числа | Сумма (odd[1]…[n]) |
| [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.
Продолжение следует…
Кристофер christopher@tut.by
Компьютерная газета. Статья была опубликована в номере 27 за 2009 год в рубрике программирование
