Hash позиции

Тема в разделе "Машинное отделение", создана пользователем Binary, 17 окт 2006.

  1. TopicStarter Overlay

    Binary Учаcтник

    • Участник
    Рег.:
    27.08.2006
    Сообщения:
    135
    Симпатии:
    0
    Репутация:
    0
    Адрес:
    Мытищи
    Оффлайн
    кстати в TSCP я не видел не одного сбоя хеша ... причем компилил я сам:/
    так что где-то я видимо напортачил ... весь геморрой заключается в сложности
    отладки этого дела ... метод отладки WildCat я еще не пробовал , но ,чувствую,
    не все там так просто
  2. NS Нефёдов Сергей

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

    Binary Учаcтник

    • Участник
    Рег.:
    27.08.2006
    Сообщения:
    135
    Симпатии:
    0
    Репутация:
    0
    Адрес:
    Мытищи
    Оффлайн
    да рокировки там ,похоже, действительно нет ...
    в TSCP есть глобальная переменная fifty /// она обнуляется при взятиях и движениях пешки

    в reps() я от безнадеги поэкспериментировал с параметрами i , hply
    - безрезультатно ...
    более менее было , когда я
    в search() заменил
    if( ply && reps() ) на if( ply && reps() > 1 /*кажется так ... может быть и > 2 - не помню*/ )
    прога ждала двух повторений и потом обламывала TSCP с ничьёй :)
    ... но после того , как она в один ход отдала ладью (так даже 4-разрядник не сделает :rolleyes: )
    я понял , что это не то
  4. TopicStarter Overlay

    Binary Учаcтник

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

    напр. технику кодирования Хаффмена
  5. NS Нефёдов Сергей

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

    Binary Учаcтник

    • Участник
    Рег.:
    27.08.2006
    Сообщения:
    135
    Симпатии:
    0
    Репутация:
    0
    Адрес:
    Мытищи
    Оффлайн
    вот еще вопросик : как представить позицию для transposition tables ?
    в тоге видел вроде 64-битное число , вот только как оттуда считать данные типа оценки , глубины поиска ,
    очереди хода (вроде больше ничего не надо :/ )
    я вот думаю забадяжить union - думаю union будет в самый раз
  7. TopicStarter Overlay

    Binary Учаcтник

    • Участник
    Рег.:
    27.08.2006
    Сообщения:
    135
    Симпатии:
    0
    Репутация:
    0
    Адрес:
    Мытищи
    Оффлайн
    Очевидно, что на кодирование начальной позиции (то есть самой худшей в плане оптимального кодирования позиции) потребуется 164 бита (32 пустых поля по 1 биту; 16 пешек по 3 бита; 4 слона, 4 коня и 4 ладьи по 5 бит; 2 короля и 2 ферзя по 6 бит - итого 164 бита). Еще несколько бит понадобится для представления возможностей рокировок и стороны, которой предстоит ход.

    в тоге 64-битное число = 64 бита (хм ... даже меньше) ... т.е. получается ,
    что существует минимальная возможность коллизии ... интересно , были ли прецеденты?
  8. NS Нефёдов Сергей

    • Заслуженный
    • Ветеран
    Рег.:
    02.05.2006
    Сообщения:
    6.811
    Симпатии:
    96
    Репутация:
    3
    Адрес:
    Санкт-Петербург
    Оффлайн
    На самом деле - обыкновенный массив. Элементами являются например struct, в Делфи - Record - на самом деле абсолютно всё-равно что. В общем виде хранится Зобрист, тип оценки, оценка, Depth оценки, опровергающий ход, счетчик для очистки хеша. Может хранится несколько оценок, несколько опровергающих ходов, информации о применении Null Move, у меня хранится информация о угрозе мата - короче целое поле для творчества. :)
  9. NS Нефёдов Сергей

    • Заслуженный
    • Ветеран
    Рег.:
    02.05.2006
    Сообщения:
    6.811
    Симпатии:
    96
    Репутация:
    3
    Адрес:
    Санкт-Петербург
    Оффлайн
    Код:
    в тоге 64-битное число = 64 бита (хм ... даже меньше) ... т.е. получается , 
    что существует минимальная возможность коллизии ... интересно , были ли прецеденты?
    Практически у всех 64-битное число. Конечно преценденты есть, но на силу игры программы они не влияют :)
    В Фрукте была добавлена проверка на легальность хода в хеше - иначе случалась неприятность где-то в одной из 1000 партий (вылет программы)
  10. TopicStarter Overlay

    Binary Учаcтник

    • Участник
    Рег.:
    27.08.2006
    Сообщения:
    135
    Симпатии:
    0
    Репутация:
    0
    Адрес:
    Мытищи
    Оффлайн
    в тоге нашел вроде как рандомизатор
    Код:
    int my_random(int n) {
       double r;
       ASSERT(n>0);
       r = double(rand()) / (double(RAND_MAX) + 1.0);
       return int(floor(r*double(n)));
    }
    RAND_MAX - макрос похоже ... но в сорцах его что-то нет
  11. WildCat Коршунов Игорь

    • Команда форума
    Рег.:
    04.05.2006
    Сообщения:
    3.599
    Симпатии:
    3
    Репутация:
    0
    Адрес:
    Гомель
    Оффлайн
    Это сишный макрос. Но мне это тоже не нравится. Возьми лучше из Крафти.
    На самом деле, когда я перешел с rand() на генератор из Крафти сила игры увелич. примерно на 10 пунктов. В шашечной программе rand() уже был заметно критичен. Коллизии случались регулярно.
  12. NS Нефёдов Сергей

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

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

    Еще поставь проверку в начале этой функции:
    HashType hash_old = hash;
    set_hash();
    if (hash_old != hash) глюки

    Помню у меня как-то портился хеш-ключ. Еле нашел где :)
  14. TopicStarter Overlay

    Binary Учаcтник

    • Участник
    Рег.:
    27.08.2006
    Сообщения:
    135
    Симпатии:
    0
    Репутация:
    0
    Адрес:
    Мытищи
    Оффлайн
    нашел в Crafty unsigned int Random32(void) - называется
    по алгоритму великого и ужасного Кнута :) - точно стоящая вещь
  15. TopicStarter Overlay

    Binary Учаcтник

    • Участник
    Рег.:
    27.08.2006
    Сообщения:
    135
    Симпатии:
    0
    Репутация:
    0
    Адрес:
    Мытищи
    Оффлайн
    так я сейчас и сделал - как ты и предсказывал , ЕСТЬ БАГИ , спасибо за идею
    теперь только б найти где ...
    у меня в проге был баг , связанный пропаданием короля из списка фигур , я поставил "затычку"
    опытным путем , но саму причину бага до сих пор не понял :) , хотя бага больше нет
  16. TopicStarter Overlay

    Binary Учаcтник

    • Участник
    Рег.:
    27.08.2006
    Сообщения:
    135
    Симпатии:
    0
    Репутация:
    0
    Адрес:
    Мытищи
    Оффлайн
    нет ... не то ... увы

    заменил твой код на
    Код:
           int old_hash = hash;
        set_hash();
        int hash_buf = hash;
        hash = old_hash;
        set_hash();
        if(hash != hash_buf)
            printf("ERROR ");
    и ERROR не появлялся :
    дело в том , что в set_hash() => hash ^= hash_piece[...]
    т.е. после 2-х повторных вызовов результат должен быть различным
  17. WildCat Коршунов Игорь

    • Команда форума
    Рег.:
    04.05.2006
    Сообщения:
    3.599
    Симпатии:
    3
    Репутация:
    0
    Адрес:
    Гомель
    Оффлайн
    Что-то я не понял как повторный вызов set_hash() может влиять на hash. Там же очередь хода учитывается.
    Кстати int маловато для хеш-ключа будет.
  18. TopicStarter Overlay

    Binary Учаcтник

    • Участник
    Рег.:
    27.08.2006
    Сообщения:
    135
    Симпатии:
    0
    Репутация:
    0
    Адрес:
    Мытищи
    Оффлайн
    я вызывал в одну очередь.... я так понял ты имеешь ввиду проверку одинаковости генерации хеша для одинаковых позиций - тогда ,скажу, что хеширует он правильно...

    я нашел некоторое число, при котором проиходит коллизия и сделал вставку типа
    if( hash == 943856284 /*это число*/ )
    print_board(); // ф-ция из TSCP

    интересный мультфиль получается :)
    причем позиции получаются самый разные - всего типов так 5-10
    так что попробую заменить int на int64
  19. NS Нефёдов Сергей

    • Заслуженный
    • Ветеран
    Рег.:
    02.05.2006
    Сообщения:
    6.811
    Симпатии:
    96
    Репутация:
    3
    Адрес:
    Санкт-Петербург
    Оффлайн
    Ансишные генераторы хорошие.
    a=1664525; c=1013904223; m=4294967296;
    либо
    1103515245,12345, 2^31
    и т.д.
    Проверено временем :)
    Чтоб не было таких мучений, я самого начала в шахматах сделал 96-битный ключ... :)

    А каким образом смогла прийти в голову идея сделать 32-битный ключ????
  20. NS Нефёдов Сергей

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

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

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

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

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

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

    • Команда форума
    Рег.:
    04.05.2006
    Сообщения:
    3.599
    Симпатии:
    3
    Репутация:
    0
    Адрес:
    Гомель
    Оффлайн
    Да, тогда у меня было 50 kNPS было.
  27. NS Нефёдов Сергей

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

    • Заслуженный
    • Ветеран
    Рег.:
    02.05.2006
    Сообщения:
    6.811
    Симпатии:
    96
    Репутация:
    3
    Адрес:
    Санкт-Петербург
    Оффлайн
    При 32-ух битном хеше.
    При количестве позиций в Хеше 100000
    После 100000 попыток обращения к хешу, вероятность что будет хоть одна коллизия 90,3%
    При увеличении количества позиций в хеше до миллиона, либо количества обращений до миллиона - вероятность коллизии 100% :)

    Для повторения позиции, если всё-время идет ровно 50 сравнений,
    То при наличии в дереве перебора 10 000 000 позиций - вероятность коллизии 11%,
    При 100 000 000 позиций в дереве - вероятность коллизии (неправильного ничейного результата) 69%
    При 1 000 000 000 позиций в дереве - вероятность коллизии 100%
    Это всё при идеальном 32-битном ключе.
  29. NS Нефёдов Сергей

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

    Что должен содержать в себе ключ (полная информация о позиции):
    1. Положение всех фигур.
    2. Очередь хода.
    3. Право взятия на проходе, и поле взятия на проходе.
    4.Право рокировок (по четыре варианта за каждую сторону)

    Как минимизировать количество проверок (для повторения позиции):
    (Для случая отслеживания двухкратного повторения)

    1. Проверяются позиции только с одной очередью хода.
    2. Предыдущая позиция с той-же очередью хода не может быть повторена.
    3. Как только нашли повторение проверку прекращаем.
    4. Перебираем в обратном порядке (начиная с текущие позиции, исходя из пунтка 2 начиная с Ply-4)
    5. Как только встретилась позиция из которой был сделан тактический (безвозвратно меняющий позицию) ход - проверку прекращаем (с этой позицией не сравниваем)
    6. Как только сработало правило 50 ходов - проверку прекращаем.

    Какие ходы являются безвозратно меняющими позицию:
    1. Взятие
    2. Ход пешки
    3. Ход изменяющий право рокировки
    4. Ход меняющий возможность взятия на проходе (любой ход при возможности взятия на проходе)
    5. NULL MOVE, пустой ход.
    6. Начальная позиция возникла в результате тактического хода :)

    Как выполнить проверку качества генератора СЧ, и полученных данных в массиве для расчета Зобриста:

    Пусть очередь хода всегда -1 (все единицы)

    1. По массиву СЧ для расчета зобриста вероятность (количество) 0 и 1 в каждом разряде должно быть примерно равно 50% (нечеткий критерий, но проверяет качество генератора СЧ)
    2. Ни одно значение в массиве не должно быть равно 0 или -1
    3. Никакая комбинация (XOR) двух разных элементов в массиве не должна быть равна 0 или -1
    4. То же самое с комбинацией из трех, и если есть время :) , то из четырех.
  30. WildCat Коршунов Игорь

    • Команда форума
    Рег.:
    04.05.2006
    Сообщения:
    3.599
    Симпатии:
    3
    Репутация:
    0
    Адрес:
    Гомель
    Оффлайн
    Я проверял на четырех. Стандартный rand(), давал много совпадений.
  31. NS Нефёдов Сергей

    • Заслуженный
    • Ветеран
    Рег.:
    02.05.2006
    Сообщения:
    6.811
    Симпатии:
    96
    Репутация:
    3
    Адрес:
    Санкт-Петербург
    Оффлайн
    У меня с проверкой всё хорошо (изначально 96 бит, почитал про ошибку Фабиена, и решил что доп. геммор мне не нужен :) ), была только одна ошибка с хешем - в первом варианте пробегал всю доску начиная с координаты 1, а нумерация полей с нуля... В итоге иногда (на самом деле очень редко) программа без зазрений совести отдавала Ладью a1...
    Использую стандартный random() из Делфи.
  32. NS Нефёдов Сергей

    • Заслуженный
    • Ветеран
    Рег.:
    02.05.2006
    Сообщения:
    6.811
    Симпатии:
    96
    Репутация:
    3
    Адрес:
    Санкт-Петербург
    Оффлайн
    Еще одна проверка наверно не помешает - поиск взаимосвязанных разрядов.
    По каждой паре разрядов (например 64 и 32) по массиву СЧ -Частота 01,00,10,11 должна быть примерно одинакова, и равна примерно 25%.
  33. TopicStarter Overlay

    Binary Учаcтник

    • Участник
    Рег.:
    27.08.2006
    Сообщения:
    135
    Симпатии:
    0
    Репутация:
    0
    Адрес:
    Мытищи
    Оффлайн
    переделал int в __int64
    поставил ГСЧ из Крафти - ошибка увы никуда не делась
    проверил ГСЧ след. образом : (притом это был 32-битный ГСЧ)
    Код:
    int set[1000];
    int trans;
    int total = 0;
    for(int iter = 0 ; iter < 1000 ; iter++)
    {
        for(int i = 0 ; i < 1000 ; i++)    
            set[i] = Random32();
    
        for(int i = 0 ; i < 1000 ; i++)    
        {
            trans = set[i];
            for(int k = i + 1 ; k < 1000 ; k++)
                if(set[k] == trans) 
                    total++;
        }
    }
        printf("total = %d", total);
    ни одного совпадения
    я полагаю ошибка либо в set_hash() , либо в search()- с другой стороны search вcегда нормально пахал...
    может в makemove()/unmake()
  34. NS Нефёдов Сергей

    • Заслуженный
    • Ветеран
    Рег.:
    02.05.2006
    Сообщения:
    6.811
    Симпатии:
    96
    Репутация:
    3
    Адрес:
    Санкт-Петербург
    Оффлайн
    Да уж....
    А что - должно было быть повторение?
    Попробуй четыре вложенных цикла - получишь повторение.
    Только есно нужно между всеми сделать XOR, а потом сравнить с нулем, и -1 (все единицы)
    32-битный Хеш такое вытянуть в принципе не может...
    //
    Насчет ошибки в make/unmake - perft проверял?
  35. TopicStarter Overlay

    Binary Учаcтник

    • Участник
    Рег.:
    27.08.2006
    Сообщения:
    135
    Симпатии:
    0
    Репутация:
    0
    Адрес:
    Мытищи
    Оффлайн
    Код:
    int set[1000];
    int trans;
    int total = 0;
    for(int iter = 0 ; iter < 100000 ; iter++)
    {
        for(int i = 0 ; i < 1000 ; i++)    
            set[i] = Random32();
    
        for(int i = 0 ; i < 1000 ; i++)    
        {
            trans = set[i];
            for(int k = i + 1 ; k < 1000 ; k++)
                if(set[k] == trans) 
                    total++;
        }
        printf(" iter = %d  total = %d\r", iter , total);
    }
    исправленный вариант - в итоге получилось 15 ... даже не знаю , много это или мало
    а теперь , ВНИМАНИЕ : ГСЧ из TSCP вернул total = 11
    пожалуй , замерю время выполнения для ГСЧ Крафти и TSCP

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