Hash позиции

что за perft ?

 

время :
у TSCP-шного = 26.110 с
у ГСЧ из крафти = 14.750 c
при iter = 10000

 

perft - количество позиций в дереве при заданной глубине перебора.
Если оно соответствует правильному - значит с огромной вероятностью генератор и Make/unmake не имеют ошибок.

Скорость генератора СЧ тебе зачем? Генератор считает один раз при запуске программы, дальше в расчетах Зобриста не участвует.

 

прикинул грубо : с ГСЧ из крафти за 260 с партии ( а это не сплошное обращение к памяти как у меня в тесте )
произойдет менее 15 коллизий при хеш ключе 32 бит ... т.е. где-то каждые 17с ... в крафти ключ = 64 бита =>
коллизии в среднем будут происходить не чаще , чем каждые 17*17 = 300 с

 

Неправильно считаешь вероятности

 

нигде я ничего не нагнал в моих матем. расчетах?

 

Нагнал, причем нехило.
Скорость крафти Миллион позиций в секунду, в Хеше - (Допустим 128Мбайт, 128 бит (16 байт) на запись) 8 миллионов позиций.
За ход (120) секунд где-то миллиард обращений к хешу. (на самом деле конечно меньше, причем не все уникальные - то есть такой позиции еще нет в хеше, но возьмем 100 000 000 обращений)
На идеальном 32-битном хеше - просто захлебнешься от коллизий...

 

При идеальных 32-бит, при каждом уникальном обращении, вероятность коллизии 8000000/2^32
За 100 000 000 уникальных обращений, в среднем будет 100 000 000*8000000/2^32 примерно 200 000 колизий.
Это не на генераторе Крафти, а на идеальном ключе

Больше тысячи в скунду на идеальном ключе.
Генератор Крафти не может быть лучше идеального

 

молодец ... тебе 5! ... стирай с доски

 

*

 

Два бита, четыре варианта?
За каждую сторону - либо возможны обе рокировки, либо обе невозможны, либо возможна только в короткую, либо только в длинную.
Как ни считай - 2 бита - это четыре варианта.

 

perft я давно еще тестировал :
для этого использовал перебор minimax (просто в alpha_beta закомментировал if(value >= beta) return 0; )
и то же самое в сорцах TSCP : до глубины 9/10 (точно не помню) совпадало 1:1 , дальше слишком долго ждать надо было ... позиция была собственная (не начальная) с ep!=0 рокировками и всеми типами фигур ...

но я имел ввиду несколько другое : может быть есть моменты , когда переиенная fifty не обнуляется или
unmake ее неправильно восстанавливает ... мои тесты говорят , что все там в порядке , но тестировать надо больше

 

рокировки , конечно , я добавлю ... но вот баг точно не там ... в TSCP проверки тоже нет ...
однако подобных выходок я за ней не замечал ... хотя порядком насмотрелся на ее партии

 

perft не бывает до глубины 9/10 ))))

 

блин ... что ты называешь этим перфтом ... - число позиций , рассмотренных при поиске на глубину х ?...
или какую-то другую хрень ?!

думаю мой тест вполне объективно подтвердил правильность работы генератора

 

Ты сумел перебрать 69352859712417 позиций? А именно этому значению равен perft 10 в начальной позиции...
При скорости 1000000 узлов в секунду - это больше 2 лет расчета...

 

http://www.research.att.com/projects/OEIS?Anum=A048987

 

ну значит я вру , когда не помню точные цифры , такой вот я ... тогда значит depth был наверное 5-7
(может хоть здесь я прав )

 

NS - ты просто мистер - ссылка! где ты раскапываешь всю эту бадягу ?

 

Ты попробуй, и проверь

 

http://www.google.ru/search?hl=ru&q=perft+chess&btnG=Поиск&lr=

 

здорово ... а я мутил что-то с сорцама TSCP :rolleyes: - вот я баклан!

 

неплохой ресурс нашел по твоей google - ссылке
http://www.chessbox.de/Compu/schachstart_e.html

 

perft 11 2097651003696806 - там наверху есть ссылка.
Кстати - чистый минимакс параллелится на любое число процов/машин, причем скорость прямо пропорциональна количеству процессоров.
Так что понятно как они считали...

 

нашел я ошибку - тупая до жути

Код:

void set_hash()
{
    int i;
    hash = 0;    
    for (i = 0; i < 64; ++i)
        if (color[i] != EMPTY)
            hash ^= hash_piece[color[i]][piece[i]][i];
    if (side == DARK)
        hash ^= hash_side;
    if (ep != -1)
        hash ^= hash_ep[ep];
}

при копировании из TSCP в свой код я где - то потерял hash = 0
в итоге одна и та же позиция имела разные хеши в зависимости от путей ее достижения
обртное тоже ,разумеется , имело место

 

правильно - это кусок кода из TSCP !

 

По моему не очень хорошая идея копировать код из чужих (причем не очень хороших) программ...
Ничего хорошего из этого не выйдет.

 

вряд ли вы разобрали суть среди отладочного мусора , закомментированного среди кода (да и не закомментированного тоже ) ...
а приводить в порядок влом было

 

Зря сомневаешься
Просто не представляешь какой код иногда приходится разбирать...

 

А как правильно считать размер хэш таблицы? Пусть утверждается, что, например, размер хэш-таблицы равен (допустим) 64 МБ? Пусть одна запись в хэше занимает 16 байт: 8 байт для хранения ключа и 8 байт для хранения сопутствующей информации. Означает ли это, что количество записей в хэш таблице равно 64х1024х1024=67108864 записей. Или это означает, что кол-во равно 67108864/16=4194304 записей?

 

Если на запись 128 бит (16 байт), то 64Мб Хеша это 67108864/16=4194304 позиций в Хеше.