Основные принципы генератора ходов (Bitboard и 0x88)

Shark, у меня вопрос про SSE2. Каковы результаты тестов версии без SSE2 по сравнению с версией с SSE2 на твоём компе?

 

Разницы - не заметил, все в пределах погрешности.
Хотя в коде видел копирование порциями по 8байт [quad word] через mmx регистер.

 

sse2 в принципе не должно влиять на скорость. это потоковые команды для мультимедиа.

 

Возможной мой код не совсем разборчив, и неправильно понят, Моя идея заключается не в оптимизации функции IsUnderCheck() , а в том чтоб ее вообще практически не вызывать, только в самых подозрительных случаях

 

Смысл моего IsRentgenWK тоже в этом. Если король не под рентгеном то ход любой фигуры кроме самого короля можно не проверять на шах от дальнобойных фигур.

 

Остается вам померить скорость без валидации у себя, и сравнить данные с моими.
Тогда будет понятно насколько эффективная валидация получилась у Вас.
Напомню у меня 11.19 и 14.48, и результат = 23% на валидацию.
Все это имеет смысл, конечно для MailSlot движков.

PS.
И пусть рубит короля, и немного глючит с его ходами, для наших замеров это не принципиально.

 

Уже похоже.
У меня хранится и возможность убрать шах и возможность получить шах, отдельно, и собственно направление линии. А начинал тоже с boolean значения, но это дало только половину экономии.

 

хм...интересно...если на рабочем П4-3000 тест performance_s.exe Shark`a был быстрей моего, то на домашнем коре2дуо - на равных. а всего лишь разные процы! т.е. мой алгоритм лучше живет на коротко-конвеертых процах.
кстати результат - perft 6 = 9.6 сек. Shark`a, у моего 8,9 сек.
забавно! :/

 

Ну и? Привел ход к вскрытому шаху, не проверили легальность, ответом соперник съел короля, поняли что ход нелегален. Не вижу никаких проблем.

 

Пусть
время генерации ходов / Время проверки на легальность = K
Тогда выгодно отказаться от проверки на легальность когда
Общее число ходов / Число нелегальных ходов > K
Это соотношение больше К, но в любом случае нам нужно делать проверку на шах (Для продления на шахах) И так как в позициях где король под шахом нелегальных ходов много, то в ответ на шах либо сразу генерируем только легальные ходы (генератор легальных ходов), либо делаем проверку на легальность после исполнения хода. (у меня в ответ на шах запускается генератор легальных ходов, так как есть продление на единственном ответе на шах)
В быстродействии выигрываем в любом случае, правда выигрыш весьма мал. Ну и немного усложняется код.

 

Тесты на домашнем компе (950 целерон) показали

WildCat 32 секунды
Shark 34 секунды
Мой генератор 35 секунд

НАРОД, ПОСОВЕТУЙТЕ КАК 4 СЕКУНДЫ СКОСТИТЬ ЧТОБЫ КОШАКА ОБОГНАТЬ

 

Обясни, зачем? У тебя и так уже скорость генератора на общей производительности практически не скажется.

 

Как зачем??? Я обещал Кoшаку задницу надрать - значит надо надрать

 

это в 0х88 используется? или и при других представлениях имеет смысл?

 

Ну если вопрос в соревновании с WildCat, то я сбросил еще пару секунд.
Теперь должно быть быстрее Кошки. [изменение 14.48 -> 12.41 ]
http://dev.enterra-inc.com/perft/performance_new.exe

 

По следам всех моих экспериментов могу сказать, что современные процессоры весьма нетривиально откликаются на все изменения.
Например, убираешь 2ва присваивания, а время работы не уменьшается а возрастает!!
Или вот еще, попробовал заменить используемый у меня 64битный счетчик - 32битным. Саму генерацию - не трогал. В результате время без валидации - уменьшилось, а время с валидацией - возросло. [Это точно не погрешность измерения, разница весьма существенна и постоянна на всех запусках]
Где логика? спрашивается

 

Задачу минимум (надрать Кошаку задницу) я тоже выполнил. А вот насчёт Акулы не уверен. Вечером протестирую последнюю свою версию и выложу результаты.

 

Интересно, какой perft(6) у Стрелки?
Можно было бы добавить такую команду в новую версию движка (если Юрий Осипов читает эту ветку.)

 

Результаты вечерних тестов:
Shark 30.42 сек.
Мой генератор 30.64 сек
WildCat 32.68 сек

http://www.extrabrain.kiev.ua/001/Chess.zip

 

Да, следует признать, что в реальных программах, do/undo move срастаются с инкрементальной оценкой позиции.
Единственное что остается это сделать perft(6), но с оценкой каждой позиции (не только конечных).
Ну и назовем его скажем perfv(6). Эта скорость уже будет близка к скорости перебора узлов.

По себе могу сказать что моя оценочная функция пока в зародыше. (Материл, Положение фигур, пешки) нет мобильности и king safe пока. Вычисление хеша для позиции в do/undo move проводятся.

при perft(6) = 12.4, perfv(6)=19.2
что-то около 6млн узлов в сек.

Дальше будет медленнее

А соревноваться считаю, нужно. Это неплохо стимуллирует фантазию. Я вот генератор в 4 раза ускорил, а ведь даже не собирался . Может кого еще вдохновит.

 

Видимо твой генератор тоже лучше работает на процессорах с коротким конвеером.
На моем рабочем компе Pentium 4-3Gz:
Shark: 12.20
ProstoTak: 14.53
WildCat: 13.7

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

 

Так давай сюда его. У меня будет стимул надрать и ему задницу.

 

Shark, по поводу оценочных функций. Я считаю что это отдельный этап. И ускорение генератора ходов, как такового, полезно само по себе и у меня есть ещё пара идей по ускорению именно генератора. А оценочную функцию можно наворотить такую что одна позиция будет 1 секунду оцениваться.

 

Ну добавь стадию партии как размерность в psq-таблице, а стадию - храни в Undo информации для хода.
У меня так же есть идея как инкрементально считать мобильность фигур, А это у меня самая трудоемкая операция в оценке получается.

PS. Может новую тему про инкрементальную оценку заведем?

 

Интересно услышать мнение специалистов.

В во всех современных программах генерятся списки ходов или есть реализации без списков?
Например может можно в битбоард генераторах генерировать сразу позиции?
Другими словами строить дерево перебора посредством позиций а не списков.
Кстати а может дерево перебора можно строить еще как нибудь?

 

В хороших программах используются Эвристики для сортировки ходов, которым необходимо знать сам ход а не получившуюся позицию. Это киллеры, сортировка по истории. Так же при записи в хеш достаточно накладно писать получившуюся позицию вместо лучшего хода.

 

Звучит очень разумно.

Получается что все известные программы используют списки?
Даже те у которых битбоард генератор?

 

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

 

ChessTerminator75 в битборд генераторе реализовать саму генерацию ходов\взятий проще. ну и конечно детектор атак и шахов проще получается. к спискам ходов генератор имеет слабое отношение -т.е. генератор просто этот список заполняет и все (как и все другие генераторы). а без списков невозможно сделать сортировку и прочие полезности (продления\отсечения).

какой же это список?
u64 whitepawn =
00000000
00000000
00000000
00000000
00001000
00010000
11100111
00000000

это просто 64 разрядное число с битами, обозначающими фигуры на доске (в данном примере-пешки)

 

Ну и чего? Нормальный список белых пешек.

 

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

 

дуп и чего здесь нормального? какую информацию кроме наличия\отсутствия этих самих пешек тут можно почерпнуть? списки куда более интересно устроены