Рыбная ловля

Тема в разделе "Машинное отделение", создана пользователем Рыбкин, 16 мар 2007.

  1. TopicStarter Overlay

    Рыбкин Зарегистрирован

    Рег.:
    14.03.2007
    Сообщения:
    9
    Симпатии:
    0
    Репутация:
    0
    Оффлайн
    Хочу обратиться к тем писателям шахматных движков, кто выпал в осадок из-за Рыбки.
    У кого-то, возможно, опустились руки - мол, Рыбку уже не догнать.
    Другие стали искать новые подходы, основанные на "знаниях", а не на тупом переборе.
    Мол, Рыбка так сильно играет из-за каких-то особых "знаний", и безо всякого
    перебора видит то, что другие программы видят только после перебора.
    Друзья, не ищите того,чего нет в природе.
    По крайней мере, в Рыбке ничего этого точно нет.
    Я не поленился, взял самую первую и самую простую Рыбку 1.0 beta 32 bit
    и дизассемблировал ее, а потом еще и переписал с ассемблера на нормальный Си.
    Конечно, я не собираюсь раскрывать все секреты, а то Васик может обидеться -
    зачем же обижать хорошего человека. Но из желания сберечь ваши нервные клетки
    скажу пару слов.

    Никаких "знаний" в Рыбке нет. И вообще - ничего сверхоригинального.
    Тот же тупой перебор, причем очень шустрый - на Pentium 2.66 GGz истинная
    скорость ( а не та, которую нам показывает Васик) - что-то около миллиона
    узлов дерева в секунду. Плюс простая, но хорошо сбалансированная оценка позиции.
    Учитывается много факторов, но работает быстро.

    Так что, догнать Рыбку можно. Два простых рецепта из рыбной кулинарии:

    1. Оптимизируйте скорость перебора - это решает всё.
    Битборды - вот что вам поможет. Но только не списывайте с Crafty -
    там реализация битовых операций очень плохая. Васик в этом вопросе ушел далеко вперед.
    2. Работайте над оценкой позиции - она должна быть простой, но гармоничной.
    Здесь дело случая - получится или нет, но возможно вам повезет,
    и вы добавите то, чего ни у кого нет. А для начала - Fruit, функция eval.
    У Васика отличия от фрукта можно по пальцам пересчитать.

    Те же выводы подтверждает и Fritz. Когда-то я проделал с ним ту же хирургическую
    операцию - сделал исходник на Си. И результат тот же - всё в угоду скорости.
    А оценка позиций такая, что проще трудно придумать, но веса подобраны со вкусом.
    А видели бы вы генератор ходов Fritza - это просто песня.
    Генерится всегда ровно один ход, который без всякой оценки сразу пускается в перебор.
    И если случается отсечка по альфа-бета, то следующие ходы и генерить не надо -
    опять та же экономия в скорости.

    Кстати, что сказал бы Ф.Морш, увидев исходники своего Fritza на Си - сам-то он
    писал его на ассемблере. И ассемблер дал ему прибавку в быстроте примерно раза
    в полтора (по сравнению с "моей" Си-версией).
  2. NS Нефёдов Сергей

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

    Есть Си версия? Немного измени её, и в качестве доказательства того что она у тебя есть дай откомпилированный вариант. Например поменяй стоимость Ферзя, и только его.

    Как-то немного дастало слушать полный бред...
  3. WildCat Коршунов Игорь

    • Команда форума
    Рег.:
    04.05.2006
    Сообщения:
    3.599
    Симпатии:
    3
    Репутация:
    0
    Адрес:
    Гомель
    Оффлайн
    Аффтар жжот :lol:
  4. TopicStarter Overlay

    Рыбкин Зарегистрирован

    Рег.:
    14.03.2007
    Сообщения:
    9
    Симпатии:
    0
    Репутация:
    0
    Оффлайн
    По поводу якобы "паттернов" в Рыбке - их нет!
    Раскрою небольшой секрет:
    Если помните, у фрукта для оценки позиции используются две хэш-таблицы,
    под которые динамически распределяется память : таблица пешечной
    структуры и таблица материала. Во время перебора эти таблицы заполняются
    оценками и разными флажками, и доступ к нужной записи
    выполняется с помощью хэш-кодов pawn_key и material_key (см. функции
    pawn_get_info и material_get_info).
    Так вот, у Рыбки тоже используется хэш-таблица пешечной структуры,
    почти точно так же, как у фрукта. А вот таблица материала посчитана один раз
    для всех случаев жизни, и результат сложен в таблицу констант размером 2 Mb.
    В любой позиции посчитали сумму всех фигурок, по полученному числу залезли
    в эту таблицу и взяли в ней довесок к оценке и поле флажков для кое-каких
    дополнительных проверок и вычисления значения Phase (стадии партии).
    Если это называть паттернами, то почему Фабьен их так не назвал?
    А Васику это нужно было всё для того же - экономии времени, хотя экономия
    здесь и копеечная.
  5. NS Нефёдов Сергей

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

    Судя по тому что вы путаете Хеш Таблицы и паттерны - с пониманием у вас совсем всё хорошо...
  6. WildCat Коршунов Игорь

    • Команда форума
    Рег.:
    04.05.2006
    Сообщения:
    3.599
    Симпатии:
    3
    Репутация:
    0
    Адрес:
    Гомель
    Оффлайн
    Не. Тут у него все хорошо. Зря придираешься. Что-то такое может быть во Фрукте.
  7. NS Нефёдов Сергей

    • Заслуженный
    • Ветеран
    Рег.:
    02.05.2006
    Сообщения:
    6.811
    Симпатии:
    96
    Репутация:
    3
    Адрес:
    Санкт-Петербург
    Оффлайн
    Это про новый Фрукт?
  8. TopicStarter Overlay

    Рыбкин Зарегистрирован

    Рег.:
    14.03.2007
    Сообщения:
    9
    Симпатии:
    0
    Репутация:
    0
    Оффлайн
    Еще раз для совсем непонятливых:
    У Фрукта таблица материала - это хэш-таблица, и доступ к ней - по хэш-коду
    board->material_key.
    В Рыбке аналог таблицы материала - массив констант, хранящийся в программе,
    и доступ к ней - не по хэш-коду, а по суммарному числу фигур на доске,
    которое вычисляется совсем по-другому, нежели хэш-код.
    Всего разных случаев наличия материала у Васика 256*1024.
    У себя я это объявил так:
    struct material_t Material[256*1024] = {
    {0x0400000, 0}, {0x0350000, -1482}, ....};

    Каждый entry этой таблицы содержит всего два поля:
    unsigned int flags (4 байта) и int value (тоже 4 байта) - смысл должен быть понятен.
    Итого получаем: 256*1024*8 = 2 Mb.
    А получена эта таблица функцией - аналогом material_comp_info из Фрукта,
    которая поработала один раз, все посчитала и сложила в готовую для употребления кучу.
    Так что все очень просто - и без всяких паттернов.
  9. NS Нефёдов Сергей

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

    • Команда форума
    Рег.:
    04.05.2006
    Сообщения:
    3.599
    Симпатии:
    3
    Репутация:
    0
    Адрес:
    Гомель
    Оффлайн
    Рыбкин
    Если бы все так было, то Рыбка считала бы эту таблицу во время инициализации. Никаких причин хранить эту ерунду в исполняемом файле.
  11. WildCat Коршунов Игорь

    • Команда форума
    Рег.:
    04.05.2006
    Сообщения:
    3.599
    Симпатии:
    3
    Репутация:
    0
    Адрес:
    Гомель
    Оффлайн
    NS
    Тут нет речи о хеш-таблице перестановок. Тут другое.
  12. NS Нефёдов Сергей

    • Заслуженный
    • Ветеран
    Рег.:
    02.05.2006
    Сообщения:
    6.811
    Симпатии:
    96
    Репутация:
    3
    Адрес:
    Санкт-Петербург
    Оффлайн
    Это же Зобрист позиции! Я вообще не понимаю что он хочет сказать. Что Васик хранит? Что он посчитал? Конкретные оценки для некоторых позиций? Фиксированный миттельшпильный самообуч? :)
  13. NS Нефёдов Сергей

    • Заслуженный
    • Ветеран
    Рег.:
    02.05.2006
    Сообщения:
    6.811
    Симпатии:
    96
    Репутация:
    3
    Адрес:
    Санкт-Петербург
    Оффлайн
    А что тут? Посчитанные двух-трехфигурные сочетания? Если да, то это паттерны. Фрукт считает их на лету? Не верю. Полный бред.
    Если board->material_key это Зобрист позиции - то
    это таблица перестановок. Если нет - То что Это?

    Аналог пешечных структур? Какой аналог? Двух-трехфигурные сочетания?
    Опять вернулись к тому-же. Паттерны, и Фрукт их считает "на лету"?
  14. WildCat Коршунов Игорь

    • Команда форума
    Рег.:
    04.05.2006
    Сообщения:
    3.599
    Симпатии:
    3
    Репутация:
    0
    Адрес:
    Гомель
    Оффлайн
    Попробуй сформултровать свою мысль еще раз. Иначе тебя никак не понять.
  15. NS Нефёдов Сергей

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

    Только при наличии сортировок, и для битбоардов - кажется полной утопией.
  16. WildCat Коршунов Игорь

    • Команда форума
    Рег.:
    04.05.2006
    Сообщения:
    3.599
    Симпатии:
    3
    Репутация:
    0
    Адрес:
    Гомель
    Оффлайн
    Не верю, что есть люди, которые в это верят :)
    Рыбкин, неужели ты такой :/
  17. bankuss Александр

    • Заслуженный
    • Участник
    Рег.:
    23.05.2006
    Сообщения:
    1.040
    Симпатии:
    26
    Репутация:
    0
    Оффлайн
    скорость скорость... вон юниор по 5 млн поз в секунду шлепает и что? (на quad и того больше)
    скорость это не самое главное.
  18. TopicStarter Overlay

    Рыбкин Зарегистрирован

    Рег.:
    14.03.2007
    Сообщения:
    9
    Симпатии:
    0
    Репутация:
    0
    Оффлайн
    1. По поводу генерации ходов по одному - это только у Fritza. В Рыбке генерятся списки.

    2. В Рыбке в таблице Material (размером 2 Mb) хранятся оценки ТОЛЬКО для разных случаев
    общего количества материала на доске, и никакого взаимного расположения фигур и их
    взаимодействие никак не учитываются. Зачем Васик загнал этот массив оценок в программу -
    надо у него спросить. Может быть, для того, чтобы все решили, что это пресловутые паттерны,
    или как-то по особому организованные "знания". И чтобы все лихорадочно занялись поиском
    этих самых знаний. Очень советую еще раз - не ищите! Нет их там!
  19. NS Нефёдов Сергей

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

    Но нужно хоть немного более реально фантазировать.
    "Читабельный Си код" :)
  20. WildCat Коршунов Игорь

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

    Рыбкин Зарегистрирован

    Рег.:
    14.03.2007
    Сообщения:
    9
    Симпатии:
    0
    Репутация:
    0
    Оффлайн
    И вообще, эта дискуссия, едва начавшись, уже начала утомлять.
    Неужели трудно понять такие простые вещи, как таблица Material.
    Если что-то непонятно - посмотрите исходники Fruit. Они должны быть у всех.
    Конкретно - файл material.c, в них - функции material_get_info и material_comp_info.
    В Рыбке почти то же самое, только уже посчитано и лежит в программе,
    и соответственно функции material_get_info и material_comp_info отстутствуют:
    они уже сделали всю свою работу и больше не нужны - могут отдыхать.
    Ну а я тоже иду отдыхать - до понедельника.
  22. WildCat Коршунов Игорь

    • Команда форума
    Рег.:
    04.05.2006
    Сообщения:
    3.599
    Симпатии:
    3
    Репутация:
    0
    Адрес:
    Гомель
    Оффлайн
    В самом первом посте нет ни одной здравой мысли. О чем тут может быть дискуссия?
  23. слесарь Учаcтник

    • Участник
    Рег.:
    16.03.2007
    Сообщения:
    13
    Симпатии:
    0
    Репутация:
    0
    Оффлайн
    раньше был такой фильм:чтобы у ученых появился стимул изобрести антигравитатор,специально сделали монтажфильм о якобы уже изобретенном устройстве антигравитации одним ученым,но который взорвался вместе с изобретением.эта мысль о возможности его создания(антигравитатора)так подхлестнула ученых что они через некоторое время изобрели уже настоящий.очень похоже что наш Рыбкин преследует эту же цель.:)
  24. bankuss Александр

    • Заслуженный
    • Участник
    Рег.:
    23.05.2006
    Сообщения:
    1.040
    Симпатии:
    26
    Репутация:
    0
    Оффлайн
    исходник в студию (хотя бы тот кусок с eval)... а то иначе все это разговоры ни о чем.
  25. Guest

    Рег.:
    Сообщения:
    0
    Симпатии:
    0
    Репутация:
    0
    Оффлайн
    Не надо исходника в студию. Действия Рыбкина на грани нарушения авторских прав (а может и уже за гранью). Публикация декомпилированого источника в моих глазах точно будет нарушением и я его немедленно удалю.
  26. NS Нефёдов Сергей

    • Заслуженный
    • Ветеран
    Рег.:
    02.05.2006
    Сообщения:
    6.811
    Симпатии:
    96
    Репутация:
    3
    Адрес:
    Санкт-Петербург
    Оффлайн
    Он не сможет его продемонстрировать.
    Физически невозможно привести к нормальному Сишному виду такой объемный текст.
  27. Мастер Икс Василий Щепетнев

    • Команда форума
    Рег.:
    11.02.2006
    Сообщения:
    3.545
    Симпатии:
    193
    Репутация:
    16
    Адрес:
    Деревня Великая Гвазда
    Оффлайн
  28. NS Нефёдов Сергей

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

    Только простое хеширование дополнительно с стандартному Хешу (Хеш пешечных структур и т.д) Особо не ускорит и не усилит программу.
    Да и все извращения с генератором тоже.

    И считается это не описанным в ветке способом.
  29. WinPooh В.М.

    • Команда форума
    Рег.:
    13.02.2006
    Сообщения:
    8.721
    Симпатии:
    1.961
    Репутация:
    83
    Адрес:
    Москва
    Онлайн
    Не забывайте про агрессивную оптимизацию, которую обычно делает компилятор. Дизассемблированный C-код может очень сильно отличаться от оригинала, написанного Васиком.
  30. WildCat Коршунов Игорь

    • Команда форума
    Рег.:
    04.05.2006
    Сообщения:
    3.599
    Симпатии:
    3
    Репутация:
    0
    Адрес:
    Гомель
    Оффлайн
    Не стоит быть таким наивным :)
  31. TopicStarter Overlay

    Рыбкин Зарегистрирован

    Рег.:
    14.03.2007
    Сообщения:
    9
    Симпатии:
    0
    Репутация:
    0
    Оффлайн
    Администратору от Рыбкина.

    Никакого выкладывания исходников Рыбки для всеобщего обозрения не будет.
    На такие предложения даже не стану реагировать.
    Не будет и выкладывания модифицированного компилированного варианта.
    Хотя поначалу такая мысль у меня была. Хотелось показать людям
    "честную" Рыбку, которая выдает правильные результаты своей работы.
    Правильную глубину поиска, а не уменьшенную на 2. Варианты правильной длины,
    а не обрезанные на 6 полуходов, и с отрезанными форсированными вариантами.
    И правильное количество узлов дерева.
    Но надеюсь, что Васик одумается и сам это сделает. А может быть, он уже
    это сделал - я, к сожалению, не видел последних версий Рыбки. Тогда беру
    свои слова обратно.

    Кстати, по поводу нехорошего поведения.
    Я, возможно, переступил какую-то грань дозволенного. Но как относиться
    к действиям Васика? Можно отнестись к ним как к невинному розыгрышу.
    Можно - как к удачному маркетинговому ходу. А можно и как к откровеннму
    мошенничеству, направленному на введение людей в заблуждение и искажение
    истинных потребительских качеств своего продукта. А продукт, между прочим,
    продается.

    По поводу сложностей декомпиляции.
    Если вы знаете два языка - ассемблер и Си, и видите перед собой цепочку
    команд на ассемблере, то в конце концов сообразите, как те же действия
    записать на Си. Это не сложнее, чеме перевод с английского на французский,
    при условии, что вы хорошо знаете оба языка.
    Если поначалу это кажется сложным, можно начать с простого подстрочника.
    Увидели команду mov eax, ebx - заведите две локальных переменных
    int r_eax и int r_ebx и напишите: r_eax = r_ebx;
    Увидели jmp ... - замените на goto ...
    Увидели test eax, eax и затем jnz ... - напишите: if (r_eax != ) goto ...
    Конечно, вы получите нечто малосъедобное. Но уже с этим можно работать
    и постепенно приводить в божеский вид. Например, последний if (r_eax != 0) goto...
    можно заменить на if (r_eax == 0) и открыть фигурную скобочку.
    В конце концов, придет умение, и вы начнете понимать логику работы компилятора.
    Вы увидите, что есть типовые конструкции, которые будете переводить почти
    не задумываясь. Вы познаете много других секретов, и получите от этого
    удовольствие. В какой-то момент вы придете к нехорошей мысли о том, что
    все это вы написали сами, и не было никакого Васика.
    А потом вы начнете понимать и логику написанного. Вы поймете, где начинаются
    массивы, и какова их размерность. Поймете, как описать структуры со всеми их
    полями. Поймете, что если подряд идут две команды: xor eax, ebx и xor edx, ecx,
    то вы имеете дело с 64-битным значением, которое определите как unsigned __int64.
    И что это значение - вероятно, хэш-код (если это операция xor), или какой-то
    bitboard, если это операция OR или AND. Если предположили, что это bitboard -
    распечатайте его в виде квадратика размером 8х8, состоящего из нулей и единичек
    и сравните с расположением фигур на доске. И поймете, что это такое, и как
    могло бы называться.
    Только не нужно забывать все тщательно тестировать. Сделать ошибку легко,
    а найти ее потом - очень трудно. Поэтому - сразу компилируйте и запускайте тест.
    Пусть часть будет пока на ассемблере, а часть на Си - слинкуется.

    Может кто-то сочтет это сложным, но я с такими людьми не дружу.
    И поверьте - жизнь устроена много проще, чем мы о ней думаем. Поверьте
    старому аксакалу, который помнит еще машины БЭСМ и перфокарты с перфолентами.
  32. bankuss Александр

    • Заслуженный
    • Участник
    Рег.:
    23.05.2006
    Сообщения:
    1.040
    Симпатии:
    26
    Репутация:
    0
    Оффлайн
    ну ладно с 2 мб все типа понятно... а что есть остальные 4 мб? в exe
  33. NS Нефёдов Сергей

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

    А вот с таблицами опять не понял.
    Даже если предположени верно, и у Васика действительно таблица материальной оценки в зависимости от сочетания материала на доске/стадии партии...

    В чем меркетенговый ход???
    Я пытаюсь сосчитать нечто похожее. Принцип тот-же что и расчет паттернов.
    Чем он ввел в заблуждение?
  34. Guest

    Рег.:
    Сообщения:
    0
    Симпатии:
    0
    Репутация:
    0
    Оффлайн
    Не понял я претензий к Васику. Свои потребительские качества Рыбка успешно демонстрирует в рейтинг листах. Или Вы обвиняете его в том, что он у Фрукта идеи позаимствовал? Так это не криминал. Если бы код целиком сдирал без разрешения автора, тогда был бы непорядочно.
  35. Guest

    Рег.:
    Сообщения:
    0
    Симпатии:
    0
    Репутация:
    0
    Оффлайн

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