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

Вот у меня Perft(6) в начальной позиции 33 секунды работает. на Pentium-M 1.7 (генератор на битбордах), пробовал на C++ переписать стал за 20 секунд работать.

NS, а ты время Perft мерял? Может у тебя не генератор медленный, а что-нибудь еще.

У меня достаточно быстрый генератор
Скорость я теряю на проверке на шах и проверке на легальность в ФВ (постоянно забывал убрать), и на том что в структуре позиции при взятии не уменьшаю материал - в итоге в проверке на шах проверяет на шах дальнобойными фигурами даже в пешечных эндшпилях, и перед оценкой (и Null Move) я сначала пробегаюсь по доске чтоб определить стадию партии.

Исправить это можно очень быстро - нужно только дописать Move/UnMove и убрать две лишних проверки в ФВ, но мне честно говоря влом всё-равно пишу новую версию "с нуля"

Я всегда проверяю позицию на легальность (и в ФВ и не в ФВ). Скорость надо, конечно, профайлером смотреть. У меня 20% всего времени работает функция int PopFirstOne(ref UInt64 value), которая очищает первый ненулевой бит и возвращает его позицию. На C++ со вставкой на ассемблере работает побыстрее.

А "с нуля" пишешь снова под 0x88 или решил другое представление попробовать?

10x12, у меня и в шашках аналог этого представления.
Ну и списки фигур сделаю...

Насчет проверки возможности хода (не попадает ли наш король под шах при ходе).
В частном случае, когда ход не королем и мы ходим не королем (это чаще всего и происходит) я делаю следующее:

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


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

Code:

    INT_64 m_Candidats = 0;
    INT_64 our_pieces_without_king = our_board->Pieces^our_board->King;
    INT_64 lvector;
    INT_64 threats;

    threats = enemy_board->QueenRook;
    if (threats) { 
        if (RookAttacks[king] & threats) {
            for (int i = FIRST_DIRECTION - 1; i <= FORTH_DIRECTION - 1; i ++) {
                lvector = Vectors[king][i];
                if (lvector & threats) 
                    m_Candidats |= (lvector & our_pieces_without_king);
            }
        }
    }

    threats = enemy_board->QueenBishop;
    if (threats) {
        if (BishopAttacks[king] & threats) {
            for (int i = FIFTH_DIRECTION - 1; i <= EIGHTH_DIRECTION - 1; i ++) {
                lvector = Vectors[king][i];
                if (lvector & threats)
                    m_Candidats |= (lvector & our_pieces_without_king);
            }
        }
    }

RookAttacks, BishopAttacks, Vectors - просчитываются при загрузке.
Таким образом m_Candidats содержит фигуры, которые надо по полной программе проверять. Остальные не проверяются.

<В частном случае, когда ход не королем и мы ходим не королем
Зарапортавался!
Должно быть "В частном случае, когда ход не королем и мы не под шахом..."

Народ, я в шоке. Добавил проверку на шах - скорость генератора упала в 4 раза

Добил кажись генератор. Уже и все проверки на все шахи, и копирование позиции, и выполнение очередного хода на копии. В результате на моём 950 целероне имею чуть более 1 миллиона ходов в секунду. Что скажете?

Ну как же не копировать? Когда нужно передавать позицию в глубину на следующий полуход. Я же замахаюсь туда сюда откатывать. Или не замахаюсь? При проверке на шах я на рабочей доске делаю ход а потом откатываю. Но при передаче позиции на следующий полуход ИМХО нужно копировать.

Точно не нужно.
У тебя будет две функции в одной прямой ход
а в другой возврат.
Это хорошо и для скорости и для кеша.

Скорость оценить невозможно пока не напишешь
какой у тебя оценщик.

P.S. ProstoTak зайди на мой сайт почитай дневники

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

Знатная лошадь

ProstoTak
тебя понял
надо будет посмотреть.
я всегда рад замечаниям и конструктивной критике.

WinPooh
давно хотел сказать:
Спасибо за ссылки!
они здорово помогают.

Провёл оптимизацию проверки на шах, скорость возросла с 1 млн.ходов/сек до 1,4 млн.ходов/сек. Потом ещё и отказался от копирования позиции, скорость возросла до 2,4 млн.ходов/сек. Это всё на 950 целероне.

Шо, очередная волна неверия?
Во первых буду считать законченным когда перебор сделаю, а во вторых сильно ещё подумаю стоит ли открывать исходники

Сделал перебор и начал перебирать начальную позицию. Докопал до шести полуходов на своём 950 целероне. Вот что получилось.
[c]
(4) 0.11 сек, 206587 ходов, 197265 оценок, 1880 тыс. ходов/сек
(5) 3.63 сек, 5071194 ходов, 4864615 оценок, 1398 тыс. ходов/сек
(6) 87.53 сек, 124084889 ходов, 119014050 оценок, 1418 тыс. ходов/сек
[/c]

Кто больше?

Первых три полухода по цифрам совпадают с твоими. А дальше расхождение. Будем искать

Так это он двуядерный? И если да то ты используешь двуядерность?

Как считаешь на какой коэфициент нужно домножить мой проц чтобы с твоим сравняться? Если в 2 раза у тебя круче проц то ты меня в 1,5 обходишь по генератору.

Очень часто ошибки в генераторах ходов бывают с правилом взятия на проходе и рокировкой

Вот мои результаты
Athlon XP 3200+
2.01 GHz

Из начальной позиции:

perft 4
Nodes: 197281
Time: 7

perft 5
Nodes: 4865609
Time: 101

perft 6
Nodes: 119060324
Time: 2493

Время в миллисекундах

Генератор и исполнитель ходов - те же самые, что в основном поиске, т.е. с инкрементальным обновлением хэша и материала, сохранением информации для детектора повторений и т.д.

Нет, хэш не используется