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

Тема в разделе "Машинное отделение", создана пользователем NO, 7 май 2006.

  1. TopicStarter Overlay

    NO Учаcтник

    • Участник
    Рег.:
    01.05.2006
    Сообщения:
    31
    Симпатии:
    0
    Репутация:
    0
    Оффлайн
    Очевидная идея ускорить просчет ходов - собрать эквивалентные вещи в одно множество и выполнять операции над такими множествами целиком, или только над границами. Это быстрее. Любой алгоритм использует эту идею. Например в минимаксе есть [только один и очень своеобразный] вид группировки - собираются последовательности ходов с совпадающими начальными ходами. В общем же случае нужен целый специальный шахматный язык. Естественно не стоит вручную расписывать алгоритмический смысл разных понятий типа "атака" или "линия защиты", нужно сделать механизм генерации таких понятий, а сами они пусть будут пронумерованы, это удобнее. И задать операции над этими понятиями. Такого шахматного языка, как я понял, шахматисты не знают, теории нет, везде одно только рукоделие и местами искусство. На самом деле это очень распространенная проблема, я честно говоря собирался в шахматах получиться тому как это делается.
    Итак:
    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) у нее и всегда проблема с полнотой отражения задачи. Получаются "сферические кони в вакууме", но получаются почти всегда и относительно легко. В качестве более универсального языка есть человеческий, который вследствии невозможности всем его знать одинаково хорошо из соображений политкорретности считается неформальным. Для шахмат, которые имеют высокую комбинаторную сложность, но все же совершенно определены, наверно лучше ориентироваться на некий код, чем на язык или числа. Еще раз отмечу, числа это очень абстрактно, и нужны очень веские основания чтобы делать математику основным методом выбора ходов - сравнивать их по ценности и т.п.
  2. NS Нефёдов Сергей

    • Заслуженный
    • Ветеран
    Рег.:
    02.05.2006
    Сообщения:
    6.811
    Симпатии:
    96
    Репутация:
    3
    Адрес:
    Санкт-Петербург
    Оффлайн
    Ищи в инете БитБоард (BitBoard) представление позиции.
    Опять велосипед изобретаешь.
    А что результат минимакса/альфа-беты/негаскаута совпадает - доказательства простейшие, и они есть в инете (Так же как и доказательство того, что каждый последующий из этих методов просматривает позиций не больше, чем предыдущий)
    Шахматисты (Если ты так называешь шахматных программистов) - знают намного больше, чем ты думаешь.
  3. TopicStarter Overlay

    NO Учаcтник

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

    • Заслуженный
    • Ветеран
    Рег.:
    02.05.2006
    Сообщения:
    6.811
    Симпатии:
    96
    Репутация:
    3
    Адрес:
    Санкт-Петербург
    Оффлайн
    Позиция представляется не одним 64-битным числом (множеством из 64 элементов), а есно набором 64-битных чисел (набором множеств).
  5. krey Михаил Кройтор

    • Команда форума
    Рег.:
    10.04.2006
    Сообщения:
    3.692
    Симпатии:
    41
    Репутация:
    1
    Адрес:
    Кишинев
    Оффлайн
    это... вопрос. насколько выгодней использовать битовое представление позиции целочисленного представления.
  6. WinPooh В.М.

    • Команда форума
    Рег.:
    13.02.2006
    Сообщения:
    9.220
    Симпатии:
    2.523
    Репутация:
    90
    Адрес:
    Москва
    Оффлайн
    Очень выгодно.
    Особенно на 64-битных архитектурах.
    Многие операции при оценке выполняются за один-два такта, простым сложением битборда с маской.
    Например, "найти все фигуры противника, атакованные нашими пешками" и т.п.
    Узкое место - дорогая операция сканирования битов. Найти номер самого левого (правого) ненулевого бита в 64-битном слове. Поэтому часто для неё используют ассемблер.

    В Греке эта магия реализована на С++, но почему этот код работает - для меня самого загадка :)
  7. NS Нефёдов Сергей

    • Заслуженный
    • Ветеран
    Рег.:
    02.05.2006
    Сообщения:
    6.811
    Симпатии:
    96
    Репутация:
    3
    Адрес:
    Санкт-Петербург
    Оффлайн
    Очень выгодно, но не факт что выгодней, чем тот-же 0x88 и его вариации, особенно под w32...
  8. krey Михаил Кройтор

    • Команда форума
    Рег.:
    10.04.2006
    Сообщения:
    3.692
    Симпатии:
    41
    Репутация:
    1
    Адрес:
    Кишинев
    Оффлайн
    просто к чему это я спрашиваю - вообще говоря, существует по крайней мере один движок, играющий в силу гроссмейстера, но не использующий битборды. это Delfi. Так вот, насколько измениться может его сила, если перевести его на них? конечно, можно сразу же сказать, что полностью изменится структура движка и это будет уже что-то другое... но все же.
  9. WildCat Коршунов Игорь

    • Команда форума
    Рег.:
    04.05.2006
    Сообщения:
    3.599
    Симпатии:
    3
    Репутация:
    0
    Адрес:
    Гомель
    Оффлайн
    WildCat тоже не использует битборды. И Фрукт их использует чисто символически.
  10. TopicStarter Overlay

    NO Учаcтник

    • Участник
    Рег.:
    01.05.2006
    Сообщения:
    31
    Симпатии:
    0
    Репутация:
    0
    Оффлайн
    Чтобы найти биты в 64-битном слове можно составить массив 16-битовый списков бит, потом 4 раза берем 16 бит и получаем готовый список, возможно даже не номеров бит, а готовых указателей в доску, куда эти индексы должны разыменовываться.
    Это все тонкости кодерского ремесла, почитать можно про оптимизацию годогенерации в компиляторах, там все это стараются собрать и систематизировать.

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

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

    • Команда форума
    Рег.:
    13.02.2006
    Сообщения:
    9.220
    Симпатии:
    2.523
    Репутация:
    90
    Адрес:
    Москва
    Оффлайн
    Привести пример можете? Желательно с диаграммой.

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

    Не надо ничего сложного, только proof of concept.
    Один пример будет стоить тыcячи слов, которые вы уже написали.
  12. TopicStarter Overlay

    NO Учаcтник

    • Участник
    Рег.:
    01.05.2006
    Сообщения:
    31
    Симпатии:
    0
    Репутация:
    0
    Оффлайн
    WinPooh:
    Честно говоря лень :)
    Я вижу что вы и так уловили на том же уровне, как я и сам понимаю. А кто совсем не понял, мне пофиг.
  13. NS Нефёдов Сергей

    • Заслуженный
    • Ветеран
    Рег.:
    02.05.2006
    Сообщения:
    6.811
    Симпатии:
    96
    Репутация:
    3
    Адрес:
    Санкт-Петербург
    Оффлайн
    Кто-то здорово понимает, но у него ничего не играет, и оказывается что он не знает даже сути простых методов, при этом постоянно их упоминая.
    А кто-то понимает очень плохо, но у него написана нормально играющая шахматная программа, и реализованы все необходимые алгоритмы... И программа не зевает мат из-за Альфа-беты;)))))
  14. WinPooh В.М.

    • Команда форума
    Рег.:
    13.02.2006
    Сообщения:
    9.220
    Симпатии:
    2.523
    Репутация:
    90
    Адрес:
    Москва
    Оффлайн
    Научиться писать альфа-бету - дело наживное.

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

    И с этой точки зрения подход NO мне нравится. Надо сдвигать точку сборки, как говорил тов. Хуан :)
  15. NS Нефёдов Сергей

    • Заслуженный
    • Ветеран
    Рег.:
    02.05.2006
    Сообщения:
    6.811
    Симпатии:
    96
    Репутация:
    3
    Адрес:
    Санкт-Петербург
    Оффлайн
    Но идеи бывают здоровые, а бывают и не очень;))))
    Исключение перебора - эт очень хорошо. Оценили 40 позиций, и сделали ход ведущий в позицию с наилучшей оценкой... А тут всякие идиоты мучаются с переборными алгоритмами и кучей Эвристик...

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

    • Команда форума
    Рег.:
    10.04.2006
    Сообщения:
    3.692
    Симпатии:
    41
    Репутация:
    1
    Адрес:
    Кишинев
    Оффлайн
    2 NO
    вот у меня возник маленький вопросик. вы можете указать способы (хотя бы один) разбития шахмат (позиции) на подигры с, естественно, обоснованием способа? это означает, что получаемая подигра будет решаема (то есть существует алгоритм выбора наилучшего хода) и подобное разбитие будет охватывать все возможные ходы в текущей позиции?
  17. WinPooh В.М.

    • Команда форума
    Рег.:
    13.02.2006
    Сообщения:
    9.220
    Симпатии:
    2.523
    Репутация:
    90
    Адрес:
    Москва
    Оффлайн
    Мне кажется, что одна из таких попыток была у Ботвинника. Да, она не была доведена до уровня играющей программы - но изложена в его работах на достаточном уровне подробности, и кажется вполне реализуемой.
  18. NS Нефёдов Сергей

    • Заслуженный
    • Ветеран
    Рег.:
    02.05.2006
    Сообщения:
    6.811
    Симпатии:
    96
    Репутация:
    3
    Адрес:
    Санкт-Петербург
    Оффлайн
    У Ботвинника была несколько другая идея (точнее - совсем другая идея, и идеи!!!). И Ботвинник хотя бы знал что такое Альфа-бета.
  19. Kirr Администратор

    • Команда форума
    Рег.:
    11.02.2006
    Сообщения:
    1.208
    Симпатии:
    22
    Репутация:
    8
    Оффлайн
    NS, вы зануда. Пусть человек мечтает, может попробует написать что-нибудь в итоге. Тогда ему придётся и альфа-бету понять и многое другое. Может даже интересное что получится. А то мы сейчас весь энтузиазм задушим нашим ворчанием. :)
  20. NS Нефёдов Сергей

    • Заслуженный
    • Ветеран
    Рег.:
    02.05.2006
    Сообщения:
    6.811
    Симпатии:
    96
    Репутация:
    3
    Адрес:
    Санкт-Петербург
    Оффлайн
    Я просто пытаюсь его толкать в правильном направлении.;)
    Чтоб изобретать что-то своё - сначала нужно изучить основы.
  21. TopicStarter Overlay

    NO Учаcтник

    • Участник
    Рег.:
    01.05.2006
    Сообщения:
    31
    Симпатии:
    0
    Репутация:
    0
    Оффлайн
    Kirr:
    Да в общем-то задушили. Оставайтесь с NS.
  22. Позиционер Зарегистрирован

    Рег.:
    01.11.2006
    Сообщения:
    240
    Симпатии:
    0
    Репутация:
    0
    Оффлайн
    Васик, это ты ? :)

Поделиться этой страницей