Hash позиции

кстати в TSCP я не видел не одного сбоя хеша ... причем компилил я сам:/
так что где-то я видимо напортачил ... весь геморрой заключается в сложности
отладки этого дела ... метод отладки WildCat я еще не пробовал , но ,чувствую,
не все там так просто

Не знаю, для кого как - но Зобрист, и контроль повторения - самое простое в шахматной программе.
Если в программе при расчете Зобриста не задействуется право рокировки - значит оно не используется, и коллизии будут всяко.

да рокировки там ,похоже, действительно нет ...
в TSCP есть глобальная переменная fifty /// она обнуляется при взятиях и движениях пешки

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

кстати , вопрос разработчикам :
используете ли вы техники экономии места в hash ( и следует ли это делать )

напр. технику кодирования Хаффмена

НЕ смеши!!! Есть теорема, что невозможно сжать рандомную последовательность.
Зорбист Кей - и есть пример случайного числа ))

вот еще вопросик : как представить позицию для transposition tables ?
в тоге видел вроде 64-битное число , вот только как оттуда считать данные типа оценки , глубины поиска ,
очереди хода (вроде больше ничего не надо :/ )
я вот думаю забадяжить union - думаю union будет в самый раз

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

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

На самом деле - обыкновенный массив. Элементами являются например struct, в Делфи - Record - на самом деле абсолютно всё-равно что. В общем виде хранится Зобрист, тип оценки, оценка, Depth оценки, опровергающий ход, счетчик для очистки хеша. Может хранится несколько оценок, несколько опровергающих ходов, информации о применении Null Move, у меня хранится информация о угрозе мата - короче целое поле для творчества.

Код:

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

Практически у всех 64-битное число. Конечно преценденты есть, но на силу игры программы они не влияют
В Фрукте была добавлена проверка на легальность хода в хеше - иначе случалась неприятность где-то в одной из 1000 партий (вылет программы)

в тоге нашел вроде как рандомизатор

Код:

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 - макрос похоже ... но в сорцах его что-то нет

В шашечной программе - нужно всего 72 бита на быстрорасчитываемый полностью уникальный ключ

нашел в Crafty unsigned int Random32(void) - называется
по алгоритму великого и ужасного Кнута - точно стоящая вещь

так я сейчас и сделал - как ты и предсказывал , ЕСТЬ БАГИ , спасибо за идею
теперь только б найти где ...
у меня в проге был баг , связанный пропаданием короля из списка фигур , я поставил "затычку"
опытным путем , но саму причину бага до сих пор не понял , хотя бага больше нет

нет ... не то ... увы

заменил твой код на

Код:

       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-х повторных вызовов результат должен быть различным

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

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

интересный мультфиль получается
причем позиции получаются самый разные - всего типов так 5-10
так что попробую заменить int на int64

Ансишные генераторы хорошие.
a=1664525; c=1013904223; m=4294967296;
либо
1103515245,12345, 2^31
и т.д.
Проверено временем
Чтоб не было таких мучений, я самого начала в шахматах сделал 96-битный ключ...

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

Опять двадцать пять!
Говорят-же. Не может хешировать правильно, если в расчет Хеша не включить право рокировки

Так баг ведь найден!?!
Чего можно ожидать от 32 битного хеша?!?
Тут никакой генратор СЧ не поможет.

А вот код контроля повторения позиции - хоть убей не понимаю, я там задавал вопрос про отрицательное начальное значение i

Тогда было другое быстродействие.
А на контроле повторения - тут сочетание ужасного генератора СЧ и 32-битного ключа.
Возможно и еще ошибки есть (то есть наверняка есть )

Я погу посчитать вероятности коллизий на идеальном 32-битном Хеше.
Но не сейчас - вообще ничего не соображаю... Совсем плохо...

При 32-ух битном хеше.
При количестве позиций в Хеше 100000
После 100000 попыток обращения к хешу, вероятность что будет хоть одна коллизия 90,3%
При увеличении количества позиций в хеше до миллиона, либо количества обращений до миллиона - вероятность коллизии 100%

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

Насчет вопроса в первом посте.

Что должен содержать в себе ключ (полная информация о позиции):
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. То же самое с комбинацией из трех, и если есть время , то из четырех.

У меня с проверкой всё хорошо (изначально 96 бит, почитал про ошибку Фабиена, и решил что доп. геммор мне не нужен ), была только одна ошибка с хешем - в первом варианте пробегал всю доску начиная с координаты 1, а нумерация полей с нуля... В итоге иногда (на самом деле очень редко) программа без зазрений совести отдавала Ладью a1...
Использую стандартный random() из Делфи.

Еще одна проверка наверно не помешает - поиск взаимосвязанных разрядов.
По каждой паре разрядов (например 64 и 32) по массиву СЧ -Частота 01,00,10,11 должна быть примерно одинакова, и равна примерно 25%.

переделал 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()

Да уж....
А что - должно было быть повторение?
Попробуй четыре вложенных цикла - получишь повторение.
Только есно нужно между всеми сделать XOR, а потом сравнить с нулем, и -1 (все единицы)
32-битный Хеш такое вытянуть в принципе не может...
//
Насчет ошибки в make/unmake - perft проверял?

Код:

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