Шахматные алгоритмы

[sergey1963]

Тема создана для обсуждения шахматных алгоритмов...
Минимакс.
Крестики-нолики 3х3 всего 9ходов- на каждый из них 8ответов и т.п. Длина игры 9полуходов или быстрее. Сверху листа бумаги нарисуем начальную позицию. Из неё возможно 9ходов, проведём 9чёрточек- ветвей. В конце каждой ветви нарисуем позицию после этого хода, далее проведём из неё ветви- ходы, возможные из данной позиции и т.п. Эта структура- дерево- у неё есть корень- начальная позиция, есть листья - позиции, где не идёт ветвей- игрок победил или ничья, и она похоже на дерево, если лист бумаги перевернуть. Припишем каждому листу его оценку. Выигрыш крестиков -1, ноликов +1, ничья- 0. Поднимаем оценку вверх по дереву - рассмотрим вершину, стоящую над листом (терминальной позицией). Из неё ведёт несколько ветвей (в крестиках-ноликах 1). Ход крестиков- он заинтересован в получении -1, выберет вариант с минимальным значением (-1, если возможно, а если нет- 0). Т.о. он выберет минимальную оценку из тех, какую имеют его потомки, припишет её этой вершине. Уровнем выше- очередь хода ноликов. Он заинтересован в получении +1- будет максимизировать полученную снизу оценку. Так поднимем оценку до корня. В крестиках-ноликах это 0- теоретический результат при оптимальной игре- ничья. С деревом играть легко- крестики выбирают ход в позицию с минимальной оценкой; нолики- с максимальной. Это- минимакс.
Альфа-бета.
Минимакс работает и на деревьях, листьям которых приписаны числа. Минимакс- трудоёмкий алгоритм, для определения результата размечается всё дерево. Можно поменьше? Да, это алгоритм- альфа-бета. Идея его: есть корень, у него- 2потомка, у каждого из них по 3потомка-листа. В корне - очередь хода мина, в вершинах 2уровня- ход макса. Листам-потомки левого поддерева, приписаны оценки 0, 5, 10. В вершинах 2подуровня мы максимизируем, левому поддереву припишем оценку 10. Рассматриваем правое поддерево. Пусть у самого левого листа оценка 100. Мы знаем, что уровнем выше мы будем максимизировать. Это означает, что оценка *всего правого поддерева* будет не меньше 100, т.к. оставшиеся листья могут эту оценку только поднять. Мы знаем, что в начальной позиции будем минимизировать, и выберем левое поддерево, оценка которого 10. Итого, получили оценку всего дерева, рассмотрев 4 позиции из 6. Шахматная аналогия- посмотрел один из своих ходов и обнаружил, что после всех ответов противника позиция равна. Посмотрел, что происходит после другого моего хода и обнаружил, что одним из ответов соперник выигрывает коня. Рассматривать другие его ответы не имеет смысла- этот свой ход я не сделаю. Нам повезло- в правом поддереве оценку 100 имеет самый левый лист. Будь он правым, и если при этом оба левых имеют оценку 7, нам пришлось бы обойти все 6 листьев. В наихудшем случае (мы всегда рассматриваем поддерево/лист с наилучшей оценкой в последнюю очередь) альфа-бета вырождается в минимакс. В наилучшем случае рассматривается 2*(количества вершин, рассматриваемых минимаксом).
Применение теории к практике.
Всё дерево машина обойти не сможет, идут на жульничество. Во-первых, всё дерево не строят- памяти не хватит. Хранят текущую позицию и последовательность ходов. Во-вторых, точная оценка заменяется на приближённую. После перебора на некоторую глубину, если нет мата или форсированной ничьи- вместо перебора дальше, мы зовём оценочную функцию, приписывающую текущей позиции некоторую оценку. Мы рвем с теорией, т.к. оценочная функция- нечто приближённое...
Однако на помощь приходит... математика...

[sergey1963]

Поиск Negamax- фундамент, на котором основаны остальные алгоритмы поиска по шахматному дереву, идея- чем хуже лучший ответ вашего оппонента, тем лучше ваш ход. Шахматы- симметричная игра- поэтому функция анализа дает симметричный результат- оценка для белых равна минус оценка для черных, т,к. сумма двух оценок всегда равна нулю. Если белые выигрывают пешку- черные проигрывают на ту ​​же сумму, если у белых сдвоенные ладьи на одной вертикали, то у белых бонусный счет, а позиция черных из-за этого на такую ​​же величину слабее.
Альфа-бета обрезка- метод уменьшения размера дерева. В средней шахматной позиции 32хода (коэффициент ветвления), пусть программа анализирует 1млн ходов в секунду. Как глубоко мы ищем-
1глубина- слой- 32хода за такт
2- 1000ходов за 32 такта
3- 32т за 0,032с
4- 1млн- 1с
5- 32млн- 32с
6- 1млрд- 17мин
7- 32млрд- 9час
8- 1трлн- 12дней
Дерево поиска становится большим- нужен быстрый анализ, поиск всего-то 7 слоев в миттельшпиле важен для движка, ограничение по времени 5 минут дает 5секунд на каждый ход. Используя текущий метод, мы не можем искать даже на слое-5. Нужно уменьшать размер дерева по отсечению альфа-бета- не проверять ходы, не могущие повлиять на результат поиска. Предположим, поиск просматривал первые 6ходов, лучший результат +15, он начинает поиск 7хода- все ответы оппонента на этот ход, получая следующие баллы -22,-11,-18,-30,-70, теперь лучший -11. Каждый раз когда ищем, мы проверяем, больше ли наш ход, чем альфа. Если да- мы заменяем альфу на новую оценку. Т.о. альфа отслеживает лучший результат на данный момент. Если результат хода меньше альфа- он нас не интересует- потому что недостаточно хорош, чтобы ухудшить оценку хода, на который является ответом. Если результат находится между альфа и бета- он будет уменьшать счет предыдущего хода соперника, но не настолько, чтобы сделать предыдущий ход плохим. Если ответный ход равен бета или превышает его, то этот ход настолько хорош, что последний ход оппонента становится плохим, и противник никогда бы не сыграл его, поэтому нам больше не нужно искать, мы возвращаем это значение лучшего результата- это отсечка высокого уровня при отказе. Альфа-бета поиск снижает фактор ветвления на каждом узле с 32 до 8, при условии, что у нас есть процедура первоначального упорядочивания перемещений- лучшие ходы в верхней части списка, чтобы остальные ходы с большей вероятностью привели к преждевременным отсечениям. Математика говорит- такое уменьшение коэффициента ветвления удвоит глубину поиска за фиксированное время.
Альфа-бета поиск не меняет результат поиска с фиксированной глубиной ни на один бит, поскольку все ветви, которые он отсекает, не имеют значения и не повлияли бы на оценку хода, более того, с вдвое большей глубиной поиска можно улучшить ходы и играть сильнее.
Однако в Стокфише коэффициент ветвления...2...

[sergey1963]

Промежуточные итоги-
1. Шахматы- исчерпываются минимаксом- деревом ходов с выигрышем-проигрышем-ничьей.
2. Т.к. проигрыш нам не нужен, значит выбор из 2 вариантов- выигрыш-ничья, значит можно улучшить минимакс до альфа-беты.
3. Раз шахматы- симметричны- выигрыш белых= проигрышу черных, по закону сохранения энергии- сколько у кого-то прибыло- столько у другого и убыло, вводим
негамакс.
4. Негамакс также можно улучшить альфа-бета обрезкой (как и минимакс альфа-бета поиском)- на движке с миллионом позиций в секуду мы дошли от 1глубины за 0,00032с (наш ход и ответ соперника с 32 различными ходами) и 7глубины с 32млрд ходов за 9часов до-
1глубина- 8ходов за 0,...с
2- 64хода за 0,...с
3- 512 за 0,...с
4- 4т за 0,004с
5- 32т за 0,032с
6- 256т - 0,256с
7- 2млн - 2с
8-16млн - 16с
9- 128млн- 2мин
10-1млрд- 16мин
11-8млрд - 2 часа
12-64 млрд-16часов
Итак, от 14 полуходов при К-ветвления= 32 дошли до 24 полуходов при К-ветвления= 8.
Как же развитие алгоритмов привело Стокфиш до К-ветвления= 2?
1глубина- 2хода за 0,...с
2- 4хода за 0,...с
3- 8- 0,...с
4- 16- 0,...с
5- 32- 0,...с
6- 64- 0,...с
7- 128-0,...с
8- 256- 0,...с
9 - 512- 0,...с
10- 1т- 0,001с
11- 2т- 0,002с
12- 4т- 0,004с
13- 8т- 0,008с
14- 16т- 0,016с
15- 32т- 0,032с
16- 64т- 0,064с
17- 128т- 0,128с
18- 256т- 0,256с
19- 512т- 0,512с
20- 1млн- 1с
21- 2млн- 2с
22- 4млн- 4с
23- 8млн- 8с
24- 16млн- 16с
25- 32млн- 32с
26- 64млн- 1мин
27- 128млн- 2мин
28- 256млн- 4мин
29- 512млн- 8мин
30- 1млрд- 16мин
31- 2млрд- 32мин
32- 4млрд- 1 час
33- 8млрд- 2 часа
34- 16млрд- 4 часа
35- 32млрд- 8часов
36- 64млрд- 16часов
Итак- уже 72 полухода... впечатляет...но какой ценой?

[sergey1963]

1.engine_score.cpp- используется для оценки позиции, представлены массивы очков за нахождение фигуры в данной клетке поля.
2.альфа-бета с амортизацией отказов, задача- как сократить число ходов для этого алгоритма.
3.transposition tables- хэш-таблицы- позиция при переборе часто повторяется- выявить такую позицию позволяет хэш-таблица, в ней хранятся “уникальные” значения, отличающие одну позицию от другой, они строятся просто выполняя операцию xor для ключей элементов, описывающих позицию, поэтому нужны массивы уникальных 64 битных чисел.
4.статистика истории- если ходы улучшают оценку позиции стоит это отмечать и в дальнейшем использовать при сортировке ходов- делаем массив 64х64 (начальная позиция фигуры на поле 8x8- конечная позиция фигуры на поле 8x8), обнулить в начале оценки выбора лучшего хода и в дальнейшем увеличиваем счётчик на 1 в случае хода, улучшающего оценку позиции.
5.late move reduction (LMR)- сортировка ходов- первыми должны быть ходы с максимальной выгодой по оценке позиции, ходы взятия приоритетнее обычных “тихих” ходов, сортируются по принципу MVV/LVA- наиболее ценная жертва- наименее ценный нападающий. При этом стоит продвигать все необычные ходы со взятием (любой ход, который не имеет тип MOVE_TYPE_SIMPLY), вперёд стоит продвинуть и взятие последней ходившей фигуры противника (если взятие будет). Обычные ходы сортируются по возрастанию оценки позиции с учётом эвристики истории, вся эта сортировка очень важна- она сама по себе позволяет сократить обход дерева игры, но более того, на нижних уровнях дерева можно выбросить почти все “тихие” ходы, если король не под шахом.
6.продлевать анализ взятий и шахов- позволит увеличить точность оценки позиции.
7.killer- эвристика убийцы- сильный ход в одной позиции, скорее всего, окажется сильным и в похожей, при анализе веток дерева пробовать первым ход, вызвавший отсечение на предыдущей ветке- это сократит перебор. Однако, такой ход может быть только “тихий”- взятия и необычные ходы использовать для таких проверок нельзя.
8.эвристика ответного хода- ответы на некоторые ходы очевидны независимо от позиции- на ab5 обычно отвечают ab5.
9.null move- нулевой ход, самая сильная эвристика- дала свыше 200эло- делать пропуск хода и посмотреть, насколько всё станет плохо, при этом можно сократить глубину анализа дерева (сделать редукцию)- всё равно оценка предварительная и не забыть пометить хэш позиции ключом нулевого хода.
10.futility prunning- на последних 2полуходах дерева оценка позиции не точна и в ряде случаев- если мы не в нулевом ходе, если ход не является шахом, взятием и ход не продление анализа ветки, если разность оценки позиции была больше некоторой небольшой величины- можно просто вернуть эту оценку и не анализировать глубже- также ускоряет работу программы.
11.razoring- относится к последним 4полуходам, граница оценки задаётся в некоторую стоимость допустимых потерь.
12.quiescence search- статический поиск, некоторые ходы стоит продлевать в анализе- взятия, шахи, приближения фигур противника к королю, продлевать лучше отдельной функцией анализа, в которой только для шахов стоит запускать полный перебор, для остальных ходов достаточно анализировать только взятия.
13.principal variation- линия игры, которую программа считает лучшей- корректируется во время перебора позиций, ход из главной линии при сортировке продвигается вперёд.

[sergey1963]

Решил немного "освежить" тему раз уж никаких новостей и идей не нашлось... Хотя самый большой "плюс-минус" Стокфиша его коэффициент ветвления, который меньше 2, т.е. в основном Сток рассматривает 1-2 хода... и все... плюс этого- огромная глубина, минус- и это мы все видим- "проскок" мимо неочевидного хода. Стокфиш не так уж и силен в тактике как разрекламирован- "длинную тактику" он не видит, так же как и "длинную позиционную стратегию"... Огромная сила Стока в сочетании тактики и стратегии- он просто "середнячок", но сразу в 2 ипостасях.
Итак буду потихоньку выкладывать нужные программы для ПК и шахмат, которые не требуют установки- это так называемые портабельные программы- открыли-запустили-поработали- закрыли и все... от них и следа нет на ПК.
https://pixeldrain.com/l/UskQPQMk#item=0
7z- архиватор всего и вся- сжимает программы, например, следующая база данных "My" 190т партий ИКЧФ 2004-2021-август с рейтингом 2300+ и ходами 20+ имеет размер 120мб, с помощью этого архиватора сжата до 20мб...
Далее- WEI- индекс производительности компьютера- оценки вашего процессора, памяти, видеокарты и диска... от 1,0 до 9,9.
Эту же оценку можно получить мгновенно в командной строке или Windows PowerShell, введя после их запуска Get-CimInstance Win32_WinSAT

[Maratka]

Цитата: Сообщение от sergey1963

Решил немного "освежить" тему раз уж никаких новостей и идей не нашлось... Хотя самый большой "плюс-минус" Стокфиша его коэффициент ветвления, который меньше 2, т.е. в основном Сток рассматривает 1-2 хода...

От количества ядер зависит. Ну вот так оно!

Я видел задачи, которые на моем FX'е не решались за пол-часа на 8 ядрах, но когда выделил 40 виртуальных - решались за единицы минут.

Есть подтверждение от другого человека, где старенький i7 (4 ядра/8 потоков), собственно от него эту задачу и взял. У него также было все это добро весьма быстро решено.

Т.е. насколько я понимаю алгоритмику этого "ленивого поиска", когда у него ресурсов в два ведра - он позволяет себе резать меньше, искать неочевидное, и находит.
Собственно, это одна из причин того, что SF после перехода с 43 ядер старого сервера на 176 потоков нового стал гораздо стабильнее в неудобных дебютах. А вот LZ от перехода с 2080 TI + 2080 на 4 2080 Ti (позже- 4 Тесла) - особо не прибавил, ибо архитектурно ему и одной RTX 2060 для этого достаточно. Замечу, это было задолго до перехода на NNUE у SF!

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

[sergey1963]

2 портабельные программы-
- Диск Инфо- информация о состоянии ваших дисков
- Диск Марк- проверка скорости ваших дисков- последовательное и случайное чтение и запись, для шахмат наиболее важно случайное чтение блоками по 4кб...
https://pixeldrain.com/u/hvmzPgjD
Ссылка на проверку файлов и сайтов на вирусы- вставляете ссылку или файл в поле поиска-
https://www.virustotal.com/gui/home/url
- вот информация о нашем сайте

[sergey1963]

еще пара портабель-прог-
- hwinfo- полная информация о комплектующих вашего ПК, кроме блока питания и корпуса (но монитор есть)
- hwmonitor- также, но попроще
https://pixeldrain.com/u/iWDBUpYt

[sergey1963]

3 портабельные программы-
- Сpu-z- информация о вашем процесоре, материнской плате, памяти и видеокарте
- Rapr- информация о всех драйверах вашего ПК, бывает что половина из них устаревшие и лишние
- Rufus- сделает вашу флешку загрузочной, нужен при переустановке или восстановлении ОС- windows
https://pixeldrain.com/u/bi7vt2Gm

[sergey1963]

Ну поехали... эти программы не портабельные-
- Tool21H1- виндовс 10- 21г-1-полугодие... распаковываете, вставляете в ПК флешку не менее 8гб, запускаете- все скачивается само с официального сайта Майкрософт с ЛИЦЕНЗИЕЙ, советую выбрать 64 разрядную версию- PRO, затем с флешки устанавливаете уже лицензионную 10-ку
- Sophia Script v5.12.1- скрипт для настройки виндовс 10- 21г-1-полугодие- можно (и нужно) убрать все лишнее- телеметрию, диагностику, отслеживание и т.п., запускается в PowerShell
- DigitalActivation- активатор всех Виндовс-10 Майкрософта- 2 вида- цифровая лицензия и просто до 2038г...
А кто сказал, что только Линукс бесплатен? Также и 10-ка- это все с сайта Майкрософт и они это знают, но чтобы быть "первой ОС в мире"- якобы не замечают. Все равно пользователи что-нибудь да купят у них- для удобства, комфорта, престижа... Да и в Линуксе полно платно навязываемого софта.
https://pixeldrain.com/l/6LpH94Tf#item=0

[sergey1963]

Чуть не забыл- команда на включение скрипта в PowerShell-
Set-ExecutionPolicy -ExecutionPolicy Bypass -Scope Process -Force
- далее Enter и после ее выполнения вставляем-
.\Sophia.ps1 и снова Enter...
- всего убирается 200 пакетов-программ Винды из 600 (поэтому Винда и весит 10гб)... за 5минут делается работа вручную на час...

Ну и портабельные шахматные оболочки- СВ-14 и ЛукасЧесс-
https://pixeldrain.com/l/zwmRLyvv#item=0