Добрый вечер хаброжители!

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

Суть задачи, есть доска 8 на 8 клеток. У игрока есть 9 шашек они расположены в углу доски в квадрате 3 на 3, у противника тоже столько же шашек и они расположены симметрично по диагонали в другом углу в квадрате 3 на 3. Каждый игрок ходит по очереди, нужно дойти шашками на места изначального положения соперника через всю доску, кто первый дошел тот и победил. Ходить можно только на пустые клетки и только вверх, вниз, влево и вправо(по диагонали нельзя!).

Управление я добавил мышью, а играть против компьютерного алгоритма. Черные - человек, белые - ИИ.

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

Немного кода для наглядности:

Game::Game(){run = true;//флаг признак нажатия кнопки выхода F5Matrix = new int* [8];//Поле 64 ячейки - значения 0 - для пустой ячейки, для игрока каждая пешка-шашка от 1 до 9, для компьютера значения в матрице от 10 до 18for (int i = 0; i < 8; i++)Matrix[i] = new int[8];//Квадраты координат нужны чтобы программа знала какие ячейки над указателем мыши, 64 квадратаQuadCoorXleft = new int* [8];//каждой ячейки матрицы Matrix соответстует квадрат координат для мыши xleft означает левую координату xQuadCoorXright = new int* [8];//xright - правая xQuadCoorYdown = new int* [8];//верхняя y координатаQuadCoorYup = new int* [8];//нижняя y координатаfor (int i = 0; i < 8; i++){QuadCoorXleft[i] = new int[8];QuadCoorXright[i] = new int[8];QuadCoorYdown[i] = new int[8];QuadCoorYup[i] = new int[8];}//Координаты пешек для отрисовкиChessX = new double[18];//XChessY = new double[18];//Y//Выделяемая пешка ее координаты и значенияActiveX = -1;//XActiveY = -1;//YActive = -1;//Valuefirstplayer = true;//флаг того что можете игрок 1й ходитьsecondplayer = false;//флаг того что можете игрок 2й ходитьai = new bool[18];//ячейки флаги того что пешка на финишной позицииchessai tmp;for (int i = 0; i < 18; i++){ai[i] = false;if (i > 8){tmp.ai = ai[i];tmp.value = i+1;Ai.push_back(tmp);//Вектор с флагами финиша каждой пешки для искуственного интеллекта}}aicountfirstrow = 0;//счетчик кол-ва пешек ИИ(искуственного интеллекта) на верхней строчке(0-я)aicountsecondrow = 0;//счетчик кол-ва пешек ИИ на предверхней строчке(1-я)aicountthirdrow = 0;//счетчик кол-ва пешек ИИ на предпредверхней строчке(2-я)}

Для отрисовки и захвата мыши используется библиотеки OpenGL и SDL2.

void Draw_Circle(){//Отрисовка круга(пешек-шахмат) черногоfor (int i = 0; i <= 50; i++) {float a = (float)i / 50.0f * 3.1415f * 2.0f;glVertex2f(cos(a), sin(a));}}void Draw_Circle_Fill(){//Отрисовка круга(пешек-шахмат) белогоfor (int i = 0; i <= 50; i++) {float a = (float)i / 50.0f * 3.1415f * 2.0f;glVertex2f(0.0, 0.0);glVertex2f(cos(a), sin(a));}}

Самое удобное что можно использовать glTranslatef чтобы заполнить доску шашками с перемещениями

...for (int i = 0; i < 9; i++){glPushMatrix();glTranslatef(ChessX[i], ChessY[i], 0);glScalef(0.05, 0.05, 1);glBegin(GL_LINE_LOOP);Draw_Circle();glEnd();glPopMatrix();}//Рисуем белые пешки ИИfor (int i = 9; i < 18; i++){glPushMatrix();glTranslatef(ChessX[i], ChessY[i], 0);glScalef(0.05, 0.05, 1);glBegin(GL_LINES);Draw_Circle_Fill();glEnd();glPopMatrix();}...

Ходы игрока:

void Game::Move_Up(){//Ход игрока вверхif (Active > 0 && ActiveX != 0 && Matrix[ActiveX-1][ActiveY] == 0)//Если выделенная пешка и не самая верхняя строчка и ячейка выше пустая{Matrix[ActiveX-1][ActiveY] = Matrix[ActiveX][ActiveY] ;//присваиваем ячейке выше текущюю(выделенную пешку)Matrix[ActiveX][ActiveY] = 0;//затираем старую ячейку на пустую ChessY[Active-1] += 0.2;//перемещаем координату У пешки вверх для отрисовкиActiveX = -1;//стираем координаты выделенной пешкиActiveY = -1;//стираем координаты выделенной пешкиActive = -1;//делаем неактивной текущую выделенную фигуруstd::cout << " Player MoveUp " << Active << std::endl;firstplayer = false;secondplayer = true;//меняем флаги хода от игрока к ИИ}}void Game::Move_Down(){//Ход игрока внизif (Active > 0 && ActiveX != 7 && Matrix[ActiveX+1][ActiveY] == 0)//Если выделенная пешка и не самая нижняя строчка и ячейка ниже пустая{Matrix[ActiveX+1][ActiveY] = Matrix[ActiveX][ActiveY] ;//присваиваем ячейке ниже текущюю(выделенную пешку)Matrix[ActiveX][ActiveY] = 0;//затираем старую ячейку на пустую ChessY[Active-1] -= 0.2;//перемещаем координату У пешки вниз для отрисовкиActiveX = -1;//стираем координаты выделенной пешкиActiveY = -1;//стираем координаты выделенной пешкиActive = -1;//делаем неактивной текущую выделенную фигуруstd::cout << "Player MoveDown " << Active << std::endl;firstplayer = false;secondplayer = true;//меняем флаги хода от игрока к ИИ}}void Game::Move_Right(){//Ход игрока вправоif (Active > 0 && ActiveY != 7 && Matrix[ActiveX][ActiveY+1] == 0)//Если выделенная пешка и не самая правая строчка и ячейка справа пустая{Matrix[ActiveX][ActiveY+1] = Matrix[ActiveX][ActiveY] ;//присваиваем ячейке справа текущюю(выделенную пешку)Matrix[ActiveX][ActiveY] = 0;//затираем старую ячейку на пустую ChessX[Active-1] += 0.2;//перемещаем координату Х пешки вправо для отрисовкиActiveX = -1;//стираем координаты выделенной пешкиActiveY = -1;//стираем координаты выделенной пешкиActive = -1;//делаем неактивной текущую выделенную фигуруstd::cout << "MoveRight " << Active << std::endl;firstplayer = false;secondplayer = true;//меняем флаги хода от игрока к ИИ}}void Game::Move_Left(){//Ход игрока влево if (Active > 0 && ActiveY != 0 && Matrix[ActiveX][ActiveY-1] == 0)//Если выделенная пешка и не самая левая строчка и ячейка слева пустая{Matrix[ActiveX][ActiveY-1] = Matrix[ActiveX][ActiveY] ;//присваиваем ячейке слева текущюю(выделенную пешку)Matrix[ActiveX][ActiveY] = 0;//затираем старую ячейку на пустую ChessX[Active-1] -= 0.2;//перемещаем координату Х пешки влево для отрисовкиActiveX = -1;//стираем координаты выделенной пешкиActiveY = -1;//стираем координаты выделенной пешкиActive = -1;//делаем неактивной текущую выделенную фигуруstd::cout << "MoveLeft " << Active << std::endl;firstplayer = false;secondplayer = true;//меняем флаги хода от игрока к ИИ}}

Ходы компьютера почти аналогичны ходам игрока, в конце будет ссылка на полный код игры, если кому интересно.

void Game::ReccurentWalk(){//Реккурентный ход ИИcurrent = -1, currentI = -1, currentJ = -1;//изначально выделенная пешка не определенаfor (int i = 0; i < Ai.size(); i++)//поиск по массивуif (!Ai[i].ai)//если не завершены ходы для конкретных пешек{if (Check_MoveUp(Ai[i].value) || Check_MoveLeft(Ai[i].value))//Можно ли походить вверх или влево?{current = Ai[i].value;//запоминаем текущую пешкуbreak;}else{//Если походить нельзя стираем из массива ходов пешкуstd::vector<chessai>::iterator position = std::find_if(Ai.begin(), Ai.end(), find_s(Ai[i].value));if (position != Ai.end()) // == vector.end() means the element was not foundAi.erase(position);}}for (int i = 0; i < 8; i++)for (int j = 0; j < 8; j++)if (Matrix[i][j] == current)//ищем в матрице пешку и запоминаем индексы{currentI = i;currentJ = j;break;}if (currentI != -1 && currentJ != -1)//если какая либо найдена ходим либо вверх либо влево{if (!Move_UpAI(currentI, currentJ))if (!Move_LeftAI(currentI, currentJ)){ReccurentWalk();}}else{//если не найдена заполняем массив ходов снова пешкамиchessai tmp;for (int i = 0; i < 18; i++){ai[i] = false;if (i > 8){tmp.ai = ai[i];tmp.value = i + 1;Ai.push_back(tmp);}}//ищем ту которая может походить вправо или внизfor (int i = 0; i < Ai.size(); i++)if (!Ai[i].ai){if (Check_MoveRight(Ai[i].value) || Check_MoveDown(Ai[i].value)){current = Ai[i].value;break;}else{//если не может то стираем из массиваstd::vector<chessai>::iterator position = std::find_if(Ai.begin(), Ai.end(), find_s(Ai[i].value));if (position != Ai.end()) // == Vector.end() means the element was not foundAi.erase(position);}}//ищем ее индексы в матрицеfor (int i = 0; i < 8; i++)for (int j = 0; j < 8; j++)if (Matrix[i][j] == current){currentI = i;currentJ = j;break;}//ходим вправо или внизif(!Move_RightAI(currentI, currentJ))if (!Move_DownAI(currentI, currentJ)){std::cout <<"Artificial Intellegence asked: WTF?" << std::endl;}}chessai tmp;if(Ai.empty())//если список ходов пуст заполняем снова всемиfor (int i = 0; i < 18; i++){ai[i] = false;if (i > 8){tmp.ai = ai[i];tmp.value = i + 1;Ai.push_back(tmp);}}}

Ну и собственно опишу словами, что делает ИИ. Он собирает три пешки вверху на 0-ой строке и если ходить нельзя влево, то двигает вверх остальные 3 пешки на 1 строку, аналогично и на 2-ю строку. Если ходить влево и вверх нельзя, то он берет любую шашку и двигает либо вниз либо вправо если можно конечно, то есть стремится всегда двигать влево или вверх( при условии что выше меньше двух шашек в строке).

Ну собственно и геймплей:

https://youtu.be/XaQVeSKdQcs

И ссылка на исходный код:

https://github.com/Beginerok/DominiGames

Так какими же всё таки должны быть идеальные шахматы?

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

Чтобы понять какими могут быть идеальные шахматы, нужно сначала понять что не так с шахматами нынешними (классическими). Давайте попробуем сформулировать недостатки не только геймплея как такового, но и недостатки связанные с психологическим восприятием того, что происходит во время игры.

Проблемы объективные

1. Проблема инвентаря при изменении правил.

2. Бесконечные ничьи достигаемые тем или иным способом.

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

Проблемы субъективные (связанные с психологией восприятия)

1. Пат. (как проблема связанная с психологией восприятия)

2. Недостаточно материала для мата.

3. Проблемы связанные с слишком сильными изменениями в правилах.

Любые проблемы желательно решать так, чтобы не плодить новые проблемы. Исходя из этой предпосылки и давайте попробуем решить нынешние проблемы шахмат.

1. Как говорится, начнём по порядку!

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

Так что, шахматы Капабланки это замечательно, и может быть во времена Капабланки количество инвентаря было сильно меньше, и такую революцию можно было хотя бы пробовать осуществлять, но сейчас, если и имеет смысл изменять правила игры, то только с сохранением существующего шахматного инвентаря.

Значит определились. Доски остаются 8х8. Фигуры те же.

2. Ничьи

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

а. Пат.

б. Вечный шах.

в. Троекратное повторение позиции.

г. Правило 50 ходов.

д. Недостаточно материала для мата.

е. Ничья по соглашению сторон.

а. Одна из проблем, это пат и патовые идеи.

Новичкам не понятно, почему король попавший в пат, это ничья? Мы же проецируем это на наши представления о мире. Если вражеского полководца не убили, а обездвижили, то в этот момент мы не теряем опцию его прирезать. Это можно сделать в любой момент, если понадобится. То есть задача выполнена. В реальности, взять живым, даже зачастую ценится больше, чем доставить мёртвым.

Конечно, те люди, которые постоянно играют в шахматы свыкаются с данной им реальностью и уже не считают это чем-то неправильным, но если эта проблема приносит нам головную боль сразу двумя способами ничьи и психология, почему бы её не устранить?

Устраняем. Приравняем пат к мату. Пат победа. Тут всё просто. Едем дальше.

б, в, г. Эти проблемы так просто не решить.

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

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

Решаем. Любой из встреченных вариантов (б, в, г), приравнивается к победе чёрных.

Решение простое, элегантное, как говорится, дёшево и со вкусом. Мы заранее говорим белым: Да, вы первые ходите, но не бесплатно. Не допускайте вот этого.

д. Недостаточно материала для мата.

Тут мы снова сталкиваемся с двумя проблемами одновременно. Ничейные результаты от которых мы хотим максимально избавить шахматы и психология восприятия. Представим ситуацию. У начинающего игрока остался слон (конь) и король, а у его противника только король. Современные правила шахмат трактуют эту ситуацию как ничью ввиду недостаточности материала для мата, но на взгляд неофита это абсурд. Как? У него только король, а у меня ещё целый слон (или конь)! Фигура приравниваемая по силе к трём пешкам! А мне достаточно и одной, чтобы провести ферзя и победить. А тут три пешки. Как это ничья?

Выглядит и правда не очень. И если вам не понравилось как выглядит вышеописанное, то представьте теперь ситуацию, где у вас остался король и целых два коня! А у противника только король. И это тоже ничья.

Как решать проблему?

Как ни странно, тоже довольно не сложно. Достаём старое правило оголения короля, сдуваем с него пыль и имеем элегантное решение.

Небольшое пояснение для тех кто не знаком с историей шахмат. Раньше существовало правило, при котором, стороне у которой остался только голый король, засчитывалось поражение.

Но есть нюанс (даже три), но и их не сложно предусмотреть. Итак, нам нужно предусмотреть 3 возможных варианта.

*. Пешечный эндшпиль, где у одной из сторон остался только король, но он в ближайшее время съест пешку (пешки) противника.

Решением служит - не учитывать правило оголения короля, пока на доске есть пешки. Они либо пройдут и станут фигурами, либо их съедят.

*. Ситуация при которой слон или конь одной стороны, съел что-то последнее у другой. Тут нужно удостовериться, что король слабейшей стороны может или не может гарантированно съесть оставшуюся фигуру.

Самый сложный вариант в данном случае конь в углу. Королю может понадобится 3 хода, чтобы съесть этого коня, при этом конь спастись не может. Значит мы можем предусмотреть правило, при котором если нет пешек на доске, оголённый король имеет в своём распоряжении 3 хода, после которых засчитывается поражение. За эти 3 хода король гарантированно съест любую одинокую фигуру противника, если такая возможность теоретически существует.

*. Голые короли. Тут всё просто. Мы уже определили, что любая ничья, в пользу чёрных. Так что мы просто используем то же самое правило, что используется для решения проблем б, в, г.

е. Ничья по соглашению сторон.

Скажите мне, в каком-нибудь другом виде спорта вы видели ничью по соглашению сторон?

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

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

Решение тут простое. Никаких ничьих по соглашению быть не должно. Ни до тридцатого хода, ни до сорокового, ни до тысяча сорокового. Просто нет и всё.

3. Осталось самое сложное, /розы/ дебют

Проблема встала на повестке дня не сегодня и не вчера. Много десятилетий назад эту проблему пытался решить один из самых выдающихся шахматистов в истории шахмат Бобби Фишер. Он предложил перемешать шахматные фигуры, расставив их в случайном порядке. Правил не так много. Позиция должна быть симметрична и король должен располагаться между ладьями, чтобы можно было сделать рокировку в любую сторону. Но решение это столь радикальное, что только очень небольшой процент шахматистов относится к шахматам Фишера (chess 960) благодушно. Подавляющее большинство относится к шахматам Фишера негативно. Слишком уж сюрреалистична как начальная позиция, так и начало партии.

Однако, есть очень интересное предложение Марка Дворецкого, которым он поделился на страницах журнала 64 шахматное обозрение в первом номере от 2008 года. Статья называется Компоненты успеха и в общем-то посвящена не только проблемам современных шахмат, но часть статьи именно так и называется проблемы современных шахмат.

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

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

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

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

Заключение. Проблемы, связанные с слишком сильными изменениями в правилах

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

Если бы такой задачи не стояло, можно было бы внести более радикальные изменения. Например, отменить мат и вместо него ввести правило съедания короля противника. Кто съел короля противника, тот победил.

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

Это позволило бы в целом кардинально упростить правила шахмат. Например, не нужно правило, при котором короли не могут приближаться друг к другу. Пусть подходит вражеский король, мы его съедим нашим королём. И много, много других правил становятся не нужными.

Но такие изменения, это уже колоссальные изменения с точки зрения внутреннего мира шахматиста. Как правило это вызывает шок и отторжение. Проверено.

Так что, как я уже написал выше, приходится учитывать проблемы связанные со слишком сильными изменениями в правилах и от каких-то изменений, пусть и очень здравых отказываться.

И напоследок,

Добро пожаловать в новый мир шахмат!

Просветительский проект Arzamas и компания DataArt запустили онлайн-курс о роли ЭВМ и кибернетики в искусстве и массовой культуре в СССР. Проект построен как экскурсия по виртуальному музею, сейчас, кроме основной экспозиции, доступны два тематических зала: один посвящен кибернетическому изобразительному искусству, музыке и поэзии, второй шахматам. Экспозиции о фантастике, неформальной кибернетике, гуманитарных науках и профессии советского программиста откроются в марте и апреле.

Проект строится не столько вокруг самого железа и технических деталей разработки ЭВМ, сколько вокруг профессии эвмщика и отражения советской кибернетики в сознании современников. Авторы курса из Arzamas, как и команда IT-музея DataArt, верят, что это важно. На наш взгляд, в республиках Советского Союза и социалистических странах Восточной Европы во второй половине XX века сформировалась особая инженерная культура. Некоторые ее черты IT-специалисты могут и сейчас наблюдать в локальных профессиональных сообществах. Впрочем, эта идея пока остается гипотезой.

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

Мы стараемся смотреть на материал, который продолжаем набирать самостоятельно и вместе с нашими партнерами, в том числе и с этой точки зрения. К тому же, человеческие истории и неожиданный взгляд на знакомые проблемы нам попросту нравятся. Думаем, совместный проект с Arzamas может быть интересен всем, кто увлекается историей науки и технологий, искусством и социальной антропологией, в частности, задумывается, как достижения в IT влияют на повседневную жизнь и представления людей об окружающем мире.

В заключение мы хотим предложить читателям Хабра небольшой опрос.

Когда создавались первые вычислительные машины, их воспринимали только как дополнение к человеческому разуму. И до недавнего времени так и было. Программисты учили компьютеры играть в шахматы с 1960-х годов. И тогда победа у игрока-новичка уже считалась большим прогрессом. О серьёзных матчах даже не задумывались.

В 1980-х программа Belle достигла рейтинга Эло в 2250 пунктов, что примерно соответствует рейтингу мастера спорта. И с того времени развитие компьютерных шахмат вышло на совершенно новый уровень.

Сначала честь человечества не смог защитить Гарри Каспаров в 1996 году, а сегодня уже создана нейросеть с рейтингом около 5000 Эло, что в разы превосходит даже сильнейших игроков.

Сегодня разберёмся, как работают шахматные алгоритмы и почему нейросеть Alpha Zero думает практически так же, как человек, только лучше.

Как работает шахматный движок: от механического перебора вариантов до умного выбора

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

Но при этом вариативность шахмат просто огромна. Существует 400 уникальных комбинаций первого хода 20 вариантов первого полухода белых и 20 вариантов ответа чёрных. С каждым последующим ходом количество уникальных позиций увеличивается на степень.

Общее количество уникальных партий в шахматы составляет примерно 10120, что на 1040 превышает количество атомов во Вселенной.

Шахматам не грозит быть посчитанными полностью. Поэтому в бой вступают алгоритмы оценки позиции и дерево возможных ходов.

В шахматной теории у каждой фигуры есть своя ценность, которая измеряется в пешках:

• Конь 3 пешки;

• Слон 3 пешки;

• Ладья 5 пешек;

• Ферзь 9 пешек;

• Пешка 1 пешка.

Король бесценен, потому что его потеря означает проигрыш партии.

Анализ современных машин подтверждает истинность такой оценки. Так, в зависимости от позиции на доске компьютер оценивает ферзя в 912 пешек, ладью в 56, коня и слона в 35. Короля же машина оценивает в 300 пешек. Это задаёт максимальную границу оценки.

Анализ современных машин подтверждает истинность такой оценки. Так, в зависимости от позиции на доске компьютер оценивает ферзя в 912 пешек, ладью в 56, коня и слона в 35. Короля же машина оценивает в 300 пешек. Это задаёт максимальную границу оценки.

Чтобы было более понятно, преимущество в 0,5 пешки это уже неплохо для шахматиста. В целую пешку серьёзный перевес. В 3 пешки подавляющее преимущество, которое можно практически без проблем довести до победы.

Но счётные возможности машины ограниченны. Иногда она показывает оценку в +51 или что-то вроде. Это означает, что алгоритм видит колоссальное преимущество белых в позиции и материале, но не может найти конкретный путь к мату.

Минимакс, или прямой перебор вариантов, в таком случае не работает. Даже КМС без проблем найдёт на доске мат в 3 хода в миттельшпиле, когда на доске ещё много фигур. А программе для этого нужно будет перебрать свыше 750 млн. полуходов.

Даже если программа перебирает 1 млн вариантов в секунду, чтобы найти мат в 3 хода, ей понадобится до 750 секунд, или 12,5 минут.

И это глубина в 3 хода. В стратегических позициях, где развитие игры идёт с учетом на пять или десять ходов вперёд, такие программы и вовсе будут бесполезными.

Поэтому для анализа позиции используется алгоритм под названием альфа-бета-отсечение.

Система анализирует начальные варианты ходов и сразу отсекает те из них, которые ведут к мгновенному ухудшению оценки.

Программа отметает те варианты, в которых она сразу проигрывает материал или которые включают комбинации со стороны соперника, в ходе которых она выигрывает материал или партию.

Это позволяет сократить количество рабочих линий на порядки, сосредотачивая вычислительные ресурсы только на тех ветвях дерева, которые в перспективе ведут к улучшению позиции.

В варианте кода это может быть реализовано примерно следующим образом:

function alphabeta(node, depth, , , maximizingPlayer) is    if depth = 0 or node is a terminal node then        return the heuristic value of node    if maximizingPlayer then        value :=         for each child of node do            value := max(value, alphabeta(child, depth  1, , , FALSE))             := max(, value)            if    then                break (*  cutoff *)        return value    else        value := +        for each child of node do            value := min(value, alphabeta(child, depth  1, , , TRUE))             := min(, value)            if    then                break (*  cutoff *)        return value

За код особо не ругайте.

Рассмотрим на примере. Движок Stockfish считается сегодня одной из самых сильных компьютерных шахматных программ. Обратите внимание на первые пять линий.

Из всего множества вариантов развития событий программа выбирает ряд линий, которые в перспективе ведут к улучшению позиции. Их она анализирует более глубоко на 1520 ходов вперёд, чтобы отсечь возможные проигрышные варианты. В результате она выбирает лучшую из возможных линий и делает ход.

После ответа соперника ситуация снова анализируется по тому же алгоритму. Сначала отсекаются заведомо проигрышные линии (таких порядка 95 %), а затем путём более глубокого анализа перспективных вариантов выбирается лучший из них.

Новая эра в шахматных движках: нейросеть Alpha Zero

В 2017 году компания Deep Mind объявила о создании нейросети Alpha Zero. Тестировать её решили на трёх самых популярных стратегических настольных играх: шахматы, го и сёги.

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

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

Alpha Zero не использует ничего, кроме правил. Ей просто дали стартовую позицию, объяснили, как ходят фигуры, и цель игры поставить мат сопернику. И всё.

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

В декабре 2018 года Alpha Zero во второй раз сразилась с самой последней версией движка Stockfish.

Исследователи провели 1000 партий с контролем 3 часа на партию плюс 15 секунд на ход.Alpha Zero одержала уверенную победу, выиграв в 155 партиях, сыграв вничью 839 партий и проиграв только 6.

Более того, Alpha Zero одерживала победу даже в партиях с форой по времени на обдумывание. Имея в 10 раз меньше времени, чем у противника, нейросеть всё равно победила в суммарном итоге. Только 30-кратная фора во времени смогла уравнять шансы и дать Stockfish примерно равную игру 3 часа у движка и всего лишь 6 минут у нейросети.

Alpha Zero анализирует лишь 60 000 позиций в секунду, а тестируемая версия Stockfish 60 млн. позиций. Для достижения аналогичных результатов анализа нейросети нужно в 1000 раз меньше ресурсов, чем движку.

Секрет успеха в качественно другом уровне анализа. Нейросеть использует метод Монте-Карло, который высчитывает математическое ожидание комплекса ходов.

Если альфа-бета отсечение способно убрать большинство заведомо проигрышных вариантов, то проверять перспективные всё равно нужно механическим перебором, нейросеть сосредоточена на вариантах, которые ведут к улучшению позиции фигур, материальному перевесу, стеснению фигур соперника или созданию комплексных угроз, включающих матовые атаки.

И, что гораздо более важно, при оценке ситуации Alpha Zero учитывает стратегическую позицию.

Давайте рассмотрим на примере одной из партий.

После 20-го хода на доске творится невообразимая стратегическая борьба. Но если нейросеть шаг за шагом минимально укрепляет свою позицию, избавляясь даже от призрачных слабостей, то движок с 24-го по 29-й ход просто топчется на месте ладьёй.

Интересно, что Stockfish в упор не видит стратегических решений Alpha Zero, оценивая позицию как абсолютно ничейную. Но в результате минимальных укреплений позиции к 39-му ходу оказывается, что все фигуры белых активны, а чёрный конь и слон занимают пассивную оборонительную позицию. А после размена ферзей и ладей даже Stockfish оценивает преимущество нейросети в +2,2. Ещё несколько ходов и король черных зажат в углу доски, а конь в одиночку не способен справиться с проходной пешкой. Поэтому программа сдалась.

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

Тем не менее нейросеть умеет играть позиционно не хуже человека и при этом идеально играет тактические позиции, где преимущество достигается в течение 5 или меньше ходов.

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

Многие теоретики считают, что благодаря шахматным компьютерам повысился и средний рейтинг топовых шахматистов. Ведь современные тренировки включают глубокую проработку компьютерных вариантов и разбора партий движками. Средний рейтинг ведущих топ-100 шахматистов в 2000 году составлял 2644 пункта Эло, а в январе 2021 года 2715. За 20 лет среднее значение увеличилось на 71 пункт.

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

Она умеет мыслить позиционно и при этом не допускает зевков и ошибок. И самое интересное в этом ситуации шахматы для Alpha Zero являются только тестировочным полигоном, где система оттачивает навыки работы. Реальные же её цели Google не раскрывает. Поэтому здесь может быть всё что угодно: от анализа изменений климатической ситуации до создания системы идеально персонифицированной рекламы. А как вы считаете, для чего создают настолько мощную нейросеть?

Создать своего гениального цифрового шахматиста или получить Level Up по навыкам и зарплате можно пройдя онлайн-курсы SkillFactory со скидкой 40% и промокодом HABR, который даст еще +10% скидки на обучение. Узнайте подробности.

• Профессия Data Scientist

• Профессия Data Analyst

• Курс по Data Engineering

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

Начало

Это случилось в 2009 году: я решил написать простую шахматную программу, чтобы попрактиковаться в разработке игрового AI. Сам я не шахматист и даже не сказать что любитель шахмат. Но задача для тренировки вполне подходящая и интересная. Кроме того, играя в шахматы на доске или в программе, мне всегда было любопытно, почему тот или иной ход сильнее другого. Хотелось возможности наглядно видеть всё дерево развития шахматной позиций. Такой фичи в других программах я не встречал - так почему бы не написать самому? Ну а раз уж это тренировка - то придумывать и писать нужно с нуля, а не изучать другие алгоритмы и писать их собственную реализацию. В общем, думаю, дня за три можно управиться и сделать какой-то рабочий вариант :-)

Первая версия

Обычно шахматные движки используют поиск в глубину с алгоритмом "ветвей и границ" для сужения поиска. Но это не очень-то наглядно, поэтому решено: мы пойдём своим путём - пусть это будет поиск в ширину на фиксированную глубину. Тогда в памяти будет полное дерево поиска, которое можно как-то визуализировать. А также выяснить: а) на какую глубину можно просчитать шахматную игру в рамках имеющихся ресурсов CPU и памяти, б) насколько хорошо или плохо будет играть такой алгоритм?

Надо сказать, что на тот момент у меня был 2-ядерный процессор с 2 или 4 Гб памяти (точно уже не помню), 32-битная винда и 32-битный компилятор Turbo Delphi Explorer. Так что если временем работы ещё можно было как-то пожертвовать, то доступная процессу память была ограничена 2Gb. Про PE flag, расширяющий user memory до 3Gb я тогда не знал. Впрочем, поскольку память кушают и система, и Delphi и другие программы - для шахмат, чтобы не уходить в своп, доступно менее гигабайта.

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

• UI - основное окно, отрисовка доски с фигурами.

• Игровая логика - составление списка возможных ходов, выполнение хода, детекция завершения игры.

• AI:оценка - оценочная функция позиции.

• AI:перебор - поиск в ширину через очередь.

• UI:браузер - окно визуализации дерева поиска, в котором можно наглядно изучать как всё работает.

Выяснилось что:

• Поиск на глубину 3 полухода работает быстро - меньше секунды, и расходует немного памяти - 5-15 Мб. А вот поиск на глубину 4 полухода работает уже довольно долго и расходует большую часть доступной памяти. В отдельных ситуациях памяти и вовсе не хватает.

• При глубине поиска в 3 полухода уровень сложности - "младшая школа": компьютер вроде как-то играет, не позволяет "зевнуть" фигуру, не упускает возможность поставить "вилку". Но в то же время допускает грубые ошибки и легко попадается в ловушки. В общем, очень слабый соперник.

• При любой глубине поиска, компьютер совершенно не умеет играть в эндшпиле и не понимает что делать, если у противника остался один король.

Таким образом, вырисовались направления дальнейшей работы: углубить поиск, научить позиционной игре а также научить играть в эндшпиле. И многие проблемы можно решить за счёт оценочной функции.

Оценочная функция

Функция оценки позиции - важнейший компонент любого шахматного движка. Где-то она предельно простая и быстрая - учитывает лишь количество фигур и их стоимость, а где-то - сложная и учитывает множество факторов. Поскольку в моём случае количество оцениваемых позиций ограничено объемом памяти, имеет смысл использовать сложную оценочную функцию и заложить в неё как можно больше факторов.

В итоге пришел к примерно такому алгоритму:

• Для каждого игрока:

  • Подсчитать стоимость фигур: конь - 3, ладья - 5 и т.д. Начальная стоимость пешки - 1, но она растёт по мере её продвижения.

  • Бонус за сделанную рокировку, штраф за потерю возможности рокировки, штраф в миттельшпиле за невыведенные фигуры (коней и ладьи в углах). Штраф за сдвоенные пешки и бонус за захваченные открытые линии.

  • Определение какие поля находятся под боем и кем. Это медленная операция - основная часть времени выполнения оценочной функции тратится именно здесь. Зато польза от неё колоссальная! Незащищённая фигура под боем на ходу противника - минус фигура. Защищённая - минус разность стоимости фигур. Это позволяет получить эффект углубления поиска на 1-2 уровня.

  • Если остался один король: штраф за расстояние от центра доски и штраф за расстояние до короля противника. Такая формула в эндшпиле заставляет AI стремиться прижать короля противника к краю доски, т.е. получить позицию, из которой можно найти возможность поставить мат.

• Итоговая оценка = (white_rate - black_rate) * (1 + 10 / (white_rate + black_rate)). Эта формула делает разницу более значимой в эндшпиле, заставляя отстающего игрока избегать размена фигур, а ведущего - наоборот, стремиться к размену.

Углубление поиска

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

Кроме того, нужно развивать наиболее перспективные направления - ветки с наибольшей оценкой.

В итоге алгоритм получился такой:

1. На первой стадии строится дерево с базовой глубиной 3 (при этом ветки со взятиями и шахами могут достигать заметно большей глубины).

2. Оценка дерева алгоритмом минимакс.

3. Если выполнены критерии принятия решения - выбирается ветка с наилучшей оценкой и алгоритм завершается.

4. Обрезка дерева: последовательно удаляются ветки с наихудшей оценкой пока не будет свободно достаточно памяти для продолжения поиска.

5. Переход к следующей стадии: добавляем вес всем листьям дерева и продолжаем поиск. После завершения переходим к п 2.

Критерии принятия решения:

• Осталась единственная ветка - выбора нет.

• Одна из веток имеет оценку существенно более высокую чем у остальных - выбираем её.

• Истекло время на ход - выбираем ветку с наилучшей оценкой.

Кэширование

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

Всё просто: нужно вычислить хэш от позиции и если в кэше уже есть оценка с таким хэшем - использовать её вместо вычисления. А если нет - вычислить и сохранить в кэше оценок. Основная проблема - нужна достаточно качественная и быстрая хэш-функция. После множества экспериментов получилось написать приемлемую функцию, вычисляющую 64-битный хэш. Общее количество возможных шахматных позиций значительно больше 2⁶⁴, но количество позиций, оцениваемых в ходе партии значительно меньше 2³², поэтому более-менее качественная хэш-функция должна свести вероятность хэш-коллизий к минимуму.

Процент "попаданий" в кэш в ходе игры получился в районе 30-45%, но в эндшпиле достигает 80-90%, что даёт ускорение почти в 5-10 раз, а следовательно позволяет увеличить глубину поиска. Неплохой выигрыш!

Что получилось?

Я добавил библиотеку дебютов, и в таком состоянии программа играла уже довольно неплохо - примерно на уровне 2-го разряда, а может и чуть сильнее. Результат, в принципе, достойный - можно остановиться. Хотя были вполне очевидны недостатки и направления развития:

• AI работает в один поток - ресурс CPU задействован не полностью.

• А что если предоставить больше памяти?

• AI думает только во время своего хода. Почему бы не использовать время соперника для просчёта наиболее вероятных продолжений?

• Главная слабость: детерминированность. Каждый ход рассматривается как отдельная задача, каждая позиция приводит к детерминированному решению. Достаточно выиграть один раз, чтобы запомнить последовательность ходов, которая всегда приведёт к победе. А играть с таким соперником неинтересно.

Однако, к этому времени код проекта уже достаточно "замусорился" и требовал рефакторинга. Поскольку на него и так уже было потрачено много времени, я решил его забросить.

Дальнейшее развитие

Недавно наткнувшись на этот заброшенный проект, решил всё-таки привести его код в порядок и доработать. Доработки сделал такие:

• Многопоточность: сейчас у меня уже 8-поточный, а не 2-поточный CPU, поэтому многопоточный вариант даёт серьёзную прибавку в скорости.

• 64-битный режим: кроме возможности использовать больше памяти, было любопытно, будет ли алгоритм работать быстрее на архитектуре x64. Как ни странно, оказалось что нет! Хотя отдельные функции на x64 работают быстрее, в целом версия x86 оказалась на 5-10% быстрее. Возможно 64-битный компилятор Delphi не очень хорош, не знаю.

• Больше памяти: даже в 32-битном режиме за счёт PE-флага расширения адресного пространства доступной памяти стало больше. Однако практика показала, что больше 1 Гб памяти все-равно не нужно - разве что для хранения "обрезанных" ветвей дерева. К усилению игры увеличение памяти не приводит.

• Непрерывность поиска: теперь дерево поиска не создаётся с нуля каждый ход, а создаётся лишь в начале партии. Когда делается ход - неактуальные ветви дерева обрезаются а поиск продолжается с того состояния, которое было. В том числе и во время хода соперника - идёт проработка перспективных продолжений, поэтому когда соперник сделает ход, поиск продолжится не с нуля. Быть может и вовсе получится сразу же сделать ход. Момент времени, когда игрок сделает ход - это фактор случайности, который делает игру недетерминированной. Теперь уже нельзя запомнить выигрышную последовательность ходов.

• Оценка дерева. Ввёл новый атрибут узла - качество оценки. Качество равно сумме качества всех прямых потомков, умноженное на коэффициент затухания. Т.е. качество оценки показывает проработанность ветки.

• Углубление поиска. Качество оценки вместе с самой оценкой учитывается при выборе веток для углубления поиска. Чем выше оценка и чем ниже её качество - тем выше приоритет такой ветки для её развития. Потому что мало смысла до посинения развивать и так хорошо проработанную ветку с максимальной оценкой, которая уже вряд ли существенно изменится, когда она сравнивается со слабо проработанными ветками, чья оценка может значительно измениться.

• База оценок и самообучение. В процессе игры какие-то позиции детально прорабатываются и получают оценку с высоким качеством. Почему бы не сохранять такие оценки для использования в других партиях? Это ещё одна фича, которая делает игру недетерминированной.

В результате этих доработок AI стал сильнее, и вполне уверенно обыгрывает старую версию игры. Я провел несколько партий против AI на chess.com и выяснил, что уровень моей программы примерно соответствует рейтингу 1800-1900. Прогресс есть, и это хорошо!

Программирование игрового AI - занятие чертовски затягивающее: всегда хочется добиться большего. И хотя у меня по прежнему есть масса идей для дальнейшего развития, наступает момент, когда надо остановиться. Думаю, он наступил. Однако если кто-либо желает - может взять мой код, побаловаться, поэкспериментировать, что-нибудь реализовать. Благо, сейчас Delphi доступен каждому благодаря бесплатной Community Edition, не говоря уже про бесплатный Free Pascal и Lazarus. Код проекта (а также скомпилированный exe-шник) можно взять тут: https://github.com/Cooler2/chess (для компиляции понадобится также кое что из https://github.com/Cooler2/ApusGameEngine). Спасибо всем, кто дочитал :-)

Если зайти на какой-нибудь шахматный сайт типа личес, то там можно обнаружить помимо обычных шахмат шахматы с альтернативными правилами. Например, давно известна игра Шахматы Фишера. Так же очень популярны CrazyHouse, King of the hill, Horde и другие. Сегодня, хочу представить вашему вниманию новую шахматную игру Teleport. Кому интересно добро пожаловать под кат)

Проектируем Teleport

Предпосылка На данный момент шахматы с классическими правилами очень хорошо исследованы. Созданы огромные базы известных типовых позиций. Какие-то позиции хорошие, какие-то плохие. Профессиональных игроки заучивают такие позиции, чтобы усилить игру. В итоге может возникнуть ситуация, что побеждает такой игрок, кто лучше запомнил, как ходить в первоначальных позициях. Но хотелось бы, чтобы победил игрок, который быстрее и лучше мыслит за доской, чтобы изученные варианты меньше влияли на победу.Как же это сделать?Да просто нужно усложнить шахматы. В классических шахматах, чтобы сделать ход, у вас есть два варианта. Вы можете пойти либо на пустую клетку, либо срубить фигуру противника.Для игры Teleport предлагаю третий вариант. Можно пойти на клетку где стоит ваша фигура, в этом случае происходит так называемый Телепорт, и фигуры меняются местами. Вот пример, как это делается: Ходим Конь f3-g5

Конь и слон меняются местами. В данной ситуации первым в руку мы должны взять коня, потому что конь f3 может пойти на поле g5, а слон не может встать на f3. Значит инициатором телепорта будет конь.

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

Вот ситуация: Ход белых. Ладья h8-h2 и пешка стремительно проходит в ферзи. Хорош ли такой маневр в целом для игры?

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

Если пешка может телепортироваться, значит может произойти такая ситуация: Ладья первым же ходом делает телепорт h1-h2, и пешка становится на первую линию горизонтали. В том что пешка очутилась на первой линии, нет ничего страшного. Затем пешка сможет двигаться дальше. И она пойдет так: с поля h1-h2 пешка сдвинется на одну клетку, и снова очутится на второй линии. А со второй линии, как известно пешка может идти на третью линию или перепрыгнуть третью и сразу встать на четвертую. Здесь ничего не меняется.

Еще момент. Можно ли в этой позиции сделать телепорт?

Пешка ходит только в перед, по диагонали она только рубит. Рубить свою фигуру нельзя, значит пешкой по диагонали телепорт не возможен. Ладья ходит по вертикали и горизонтали, и значит в данной ситуации телепорт ладьей не возможен. В общем то это очевидно, но это надо проговорить.А как на счет короля, должен ли король делать телепорт?Рассмотрим позицию. Ход белых. Здесь численное преимущество белых. Если белый король находился бы в безопасности, исход был бы очевиден белые бы победили. Если мы разрешим королю телепортироваться (Слон a8-h1), то король убежит, а вместе с ним убежит зрелищность и накал страстей).

Было бы здорово, если бы в этой ситуации победили бы черные? Поэтому принимаем решение король телепортироваться не может!Просто с большим количеством фигур, легче организовать телепорт для короля, а значит мат в начале и середине игры будет поставить сложно. И это идет в разрез с тем, что мы хотим сделать игру зрелищной.Вот еще пример. Белые ставят детский мат.

Но если бы, король мог телепортироваться (Ферзь d8-e8), тогда бы король улизнул, и детского мата не произошло. В этом случае, зрелищность теряется.

ИТАК

Окончательные правила

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

Немного задачХод черных. Мат в 1 ход. Ну правда же красиво?

Белые начинают и выигрывают. Мат в 1 ход.

Белые начинают и выигрывают в 2 хода.