Шахматные программы III. Дерево перебора

[GlukKazan]

про шашки было бы интересно.

[Rom77]

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

NS » 22.02.2009, 18:03

Чтоб прилично играл шашечный движок нужно совсем немного -

Перебор - Альфа-бета либо PVS, рассмотрение всех взятий за горизонтом.

Для сортировки - Хеш, киллеры, история, взятия сортировать по взятому материалу.

В переборных алгоритмах LMR, MultiCut, отсечения на малой глубине (Футилити/ProbCut/Рыбья схема)

В оценке достаточно PST. Накрутки (мобильность, центр, баланс флангов и т.д.) что-то прибавляют, но для силы Каллисто3 они совершенно необязательны.

http://www.sdchess.net

В международных шашках в годы до нейросетей наиболее сильной была программа Scan 2.0 Фабьена Летузи. У нее была оригинальная оценочная функция на основе набора паттернов. Она распознавала на доске структуры размером 4х4. Если я правильно помню.

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

https://laatste.info