Шахматный язык

Очевидная идея ускорить просчет ходов - собрать эквивалентные вещи в одно множество и выполнять операции над такими множествами целиком, или только над границами. Это быстрее. Любой алгоритм использует эту идею. Например в минимаксе есть [только один и очень своеобразный] вид группировки - собираются последовательности ходов с совпадающими начальными ходами. В общем же случае нужен целый специальный шахматный язык. Естественно не стоит вручную расписывать алгоритмический смысл разных понятий типа "атака" или "линия защиты", нужно сделать механизм генерации таких понятий, а сами они пусть будут пронумерованы, это удобнее. И задать операции над этими понятиями. Такого шахматного языка, как я понял, шахматисты не знают, теории нет, везде одно только рукоделие и местами искусство. На самом деле это очень распространенная проблема, я честно говоря собирался в шахматах получиться тому как это делается.
Итак:
1. Базовые атомы - {черный, белый, пешка..король, a1..h8}
1.1. Однотипные атомы - цвет={черный, белый}, фигура={пешка..король}, поля={a1..h8}
1.2. Каждый атом как множество из одного элемента - {a1}
2. Множества полуемые ходами. ходы(ситуация, поле, фигура)={поля}
2.1. Все фигуры, которые бьют одно поле - e5:{ладья, пешка, конь, конь}
2.2. Все поля, котрые бьет заданная фигура - пешка:{d3,f3}
3. Из них создаются другие абстракции:
3.1. Перечислением базовых - {{d3,f3},{a1},{c5,d5}}, это множество из 3 элементов
3.2. Логическими связками - пересечение, объединение, дополнение - {d3,f3,a1,c5,d5}, тут 5 элементов
3.3. Выполнением {{конь,пешка},b2}={a4,c4,b3,b4}

в 2. ситуация это не обязательно вся доска, это может быть просто пустая ситуация, тогда получим все возможные ходы согласно правилам, или какое-то частично описание, например участка доски, или даже требования включащие требование исключить какие-то ходы
в 3.3. выполнение ходов может быть получено логически, как пересечение объекта фигура*поле и объекта 2.2.

Если логические операции {совпадает, выполнить, пересечение...} тоже обозначить и сделать базовыми атомами, то получим язык рассуждений, отличный от языка ходов и позиций. В программировании такие языки называют мета- или динамическими. Например Лисп. Для сравнения Пролог является языком только 1 порядка, он работает с данными, а предикаты пишет только программист. На таком мета- языке компьютер мог бы сам(!) вычислить фишку что результаты минимакса и альфа-беты совпадают. Но это сейчас совсем сложно. Сначала бы сделать до 3.3, а вместо мета- рассуждений можно пока сделать тестирование вариантов и статистику.

Когда метод абстрагирования только один мы получаем математику. То есть 3 отличается от 5 точно так же как 7 отличается от 2 - числом. Сами объекты тоже числа. Математика очень абстрактна, поэтому (1) оказывается адекватной в очень многих задачах, (2) у нее и всегда проблема с полнотой отражения задачи. Получаются "сферические кони в вакууме", но получаются почти всегда и относительно легко. В качестве более универсального языка есть человеческий, который вследствии невозможности всем его знать одинаково хорошо из соображений политкорретности считается неформальным. Для шахмат, которые имеют высокую комбинаторную сложность, но все же совершенно определены, наверно лучше ориентироваться на некий код, чем на язык или числа. Еще раз отмечу, числа это очень абстрактно, и нужны очень веские основания чтобы делать математику основным методом выбора ходов - сравнивать их по ценности и т.п.

 

Ищи в инете БитБоард (BitBoard) представление позиции.
Опять велосипед изобретаешь.
А что результат минимакса/альфа-беты/негаскаута совпадает - доказательства простейшие, и они есть в инете (Так же как и доказательство того, что каждый последующий из этих методов просматривает позиций не больше, чем предыдущий)
Шахматисты (Если ты так называешь шахматных программистов) - знают намного больше, чем ты думаешь.

 

NS:
BitBoard я в свое время сам придумал, году в 95. Решил сделать самую быструю Жизнь Конвэя
Потом один человек изучал инварианты алгоритмов на примере этих самых Жизней, у него их было 300 разных программ. Я спросил была ли такая, он ответил что не было. Кстати о программистах. Программа лежит на моей странице, еще под MSDOS. Вообще это вариант так называемой memoization, она например функцию Аккермана ускоряет даже не на порядки, а переводит ее в другой класс O()-сложности. Но тут не подходит. В пункте 3.2. не ИЛИ от нескольких списков, а список списков. Если такое представлять битмапами потребуется не 64 бит, а 2^64. Если найдете мне компьютер с таким объемом памяти я с удовольствием воспользуюсь советом. Так что пока снова мимо. Есть у вас куда послать еще подальше?

 

Позиция представляется не одним 64-битным числом (множеством из 64 элементов), а есно набором 64-битных чисел (набором множеств).

 

Очень выгодно, но не факт что выгодней, чем тот-же 0x88 и его вариации, особенно под w32...

 

Чтобы найти биты в 64-битном слове можно составить массив 16-битовый списков бит, потом 4 раза берем 16 бит и получаем готовый список, возможно даже не номеров бит, а готовых указателей в доску, куда эти индексы должны разыменовываться.
Это все тонкости кодерского ремесла, почитать можно про оптимизацию годогенерации в компиляторах, там все это стараются собрать и систематизировать.

А суть специального языка под шахматы это не ускоренние перебора, а вообще по возможности его полное исключение. Исследовать нужно только границы множеств, особые точки. Не обрабатывать все множество одной 64-битной операцией, а обычными операциями обрабатывать только то, что имеет смысл обрабатывать.
Первая возникающая проблем в том, что значимость ходов зависит от следующих, т.е. только выполнив их мы получим приоритеты чтобы принять решение, что выполнять их было не нужно. Это свойство неупрощаемых систем или машины Тьюринга. Но шахматы не МТ, тут конечная доска, как следствие конечная сложность всей задачи, и очевидно есть возможность разбивать задачу на подзадачи. Но методология этого разбиения должна быть не статичной, а зависимой от позиции. Статичные модели всегда очень умные и всегда содержат небольшое примечание "...а остальное можно и перебором проветить", а потом на этот перебор приходися все 100% машинного времени.
То есть язык не просто кодировка, а весь культурный феномен, в рамках которого эти кодировки возникают и существуют. У животных тоже есть язык - эмоций, запахов, но он привязан к физиологии и никакой гибкости не дает. Понимаете, чем отличаются языки людей от языков животных?

Шахматная позиция делится на фигуры и их позиции, влияние фигур ограничено. В каких-то границах отдельные элементы позиции можно просчитать до конца, закрыть эти "ветви" раз и навсегда. Получается такие виртуальные под-игры или псевдо-фигуры, в которые и которым нужно играть дальше, выходя на макро-уровень. Они более сложные, правила другие и количество "ходов" там больше чем у просто фигурок. Дерево перебора получается на порядки больше в ширину. Но должно быть намного меньше, чем просто перебор фигурок, хотя у каждой из них ходов меньше чем у макро-фигуры и правила более простые чем у под-игры. В под-игре не квадратная доска и она меняется с ходами, однако всилу соображений в других под-играх это влияние вполне ограничено. Нужно ее решить ее саму полностью, как крестики-нолики 3*3, получить лучшую стратегию для этого фрагмента. Полностью решенная под-игра из игры превращается в статичную макро-фигуру. Перебор уходит на проверку отношений этих макрофигур и их устойчивости. Проверяются только границы. Если граничные ситуации оказываются более интересными чем сами фигуры, то дерево игр реструктуризируется. Получам дерево игр. В каждой свои фигуры и свои правила. Вот поэтому один язык (кодировка) не подходит.

 

WinPooh:
Честно говоря лень
Я вижу что вы и так уловили на том же уровне, как я и сам понимаю. А кто совсем не понял, мне пофиг.

 

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

 

Но идеи бывают здоровые, а бывают и не очень)))
Исключение перебора - эт очень хорошо. Оценили 40 позиций, и сделали ход ведущий в позицию с наилучшей оценкой... А тут всякие идиоты мучаются с переборными алгоритмами и кучей Эвристик...

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

 

У Ботвинника была несколько другая идея (точнее - совсем другая идея, и идеи!!!). И Ботвинник хотя бы знал что такое Альфа-бета.

 

Я просто пытаюсь его толкать в правильном направлении.
Чтоб изобретать что-то своё - сначала нужно изучить основы.

 

Kirr:
Да в общем-то задушили. Оставайтесь с NS.

 

Васик, это ты ?