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

Я вроде писал об отличии.
Отличается только проверка выхода за границы.
В 0x88 проверка при генерации хода:
if (Kuda and 136)=0 then
if Pole[Kuda]=0 then

А в МэйлБокс:
if Pole[Kuda]=0 then


Вот и все отличия. В 0x88 меньше обращений к памяти, а в МэйлБокс меньше проверок (условий)
На современных компах быстрее МэйлБокс, на совсем старых быстрее 0x88

Точнее еще одно отличие. Проверка на фигуру соперника в 0x88
if Kto<0 Then
А в МэйлБокс
if (Kto and BP)<>0 Then

Пух, я тебя догнал и перегнал аж на целых 2 секунды. Теперь perft 6 я считаю за 70 секунд а Грека за 72. Это я только порядки в коде понаводил и ещё не все. А шо будет если я возьмусь за списки фигур? Если, как сегодня, буду в день сбрасывать по 20 секунд то скоро йду в минус бесконечность.

Пух, постепенно ухожу в отрыв. Ещё 5 секунд долой. Теперь я Греку опережаю на 7 секунд (65 против 72).

ProstoTak прогресс пошел!

За ночь удалось сбросить ещё 2 секунды. Теперь perft 6 считаю за 63 секунды (Кошка за 32).

bankuss, кстати твой ALChess1.5b на моём компе считает perft 6 за 164 секунды. Так что есть над чем работать

ProstoTak у тебя нет той версии которая за 9.9 секунд считает! я же все на С++ перенес, а та версия на freebasic как говорится разница налицо.
у меня 1.5b считает за 28 секунд. переписанная за 9.9 :rolleyes:
алгоритмы те же остались.

WinPooh это что, новая мода в шахматном программировании?

Ну так получается, что скорость возросла в 3 раза. Значит на моём компе должна считать за 164/3=54 секунды. Ну ничего, осталось чуток и догоню.
P.S. А может дашь новую версию чтобы я на своём компе потестил?

Почему mailbox? Откуда взялось такое название?

ProstoTak оки, пришлю, тока она урезанная

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

ProstoTak личку читаешь?

Вообще то нет потому, что её тут нихрен не видно. Но ради тебя прочитал и даже ответил.

Я вообще то свой генератор с помощью Борланд СРР компилирую для DOS. А про интеловский только слышал. Может зашлёшь с описанием настроек?

Пух, прогнал тест. У меня 50 секунд у Греки 58 на perft 4, все цифири в нодах совпадают.

Пух, а какой ещё есть компилер кроме борландовского досовского? Чем обычно под винду надо компилить? И ещё, так ты мне дай греку откомпиленного самым лучшим способом какой у тебя есть, я его сравню со своим генератором.

1.a4 b5 2.a5 b4 3.a6 Bb7 4.axb7 Nc6 5.b8Q Nd4 6.c4 Nb5 7.cxb5 Nf6 8.b6 Nd5 9.Qb7 Nf4 10.Qd5 Rc8 11.b7 a5 12.b8Q a4 13.Ra3 e6 14.Rd3 a3 15.Rd4 a2 16.Rd3 a1Q 17.Rb3 c5 18.d4 c4 19.Qdb5 Rc5 20.dxc5 Nd5 21.c6 Nb6 22.c7 Nd5 23.c8Q f5 24.e4 Nf6 25.e5 Ng4 26.Qd2 Be7 27.Qe2 Bf6 28.exf6 Kf7 29.h3 Kg6 30.f7 Re8 31.f8Q Ne3 32.g4 Re7 33.g5 Rf7 34.f3 Rf6 35.gxf6 Ng4 36.f7 Qf6 37.Qfd6 Nh6 38.f8Q Ng4 39.Qfd8 Qe7 40.Qd8b6 Qa7 41.Q5a5 Qc7 42.Qa2 Kf7 43.h4 g5 44.h5 Ne5 45.Nd2 Ng6 46.hxg6+ Kf6 47.g7 Qf7 48.g8Q Qd8 49.Qbe3 Qde7 50.Qda6 Qg7 51.Ra3 bxa3 52.b4 c3 53.Qb3 a2 54.b5 a1Q 55.b6 Qa4 56.b7 Qc6 57.Qcc7 d6 58.Qba8 d5 59.b8Q f4 60.Rh3 c2 61.Rg3 fxg3 62.f4 Qcd7 63.f5 g4 64.Qe3d3 Kg5 65.f6 h5 66.f7 h4 67.f8Q h3 68.Ngf3+ gxf3 69.Nc4+ Kh5 70.Bg2 hxg2 71.Bg5 Kxg5 72.Qed2+ Kh5 73.Qb2 c1Q+ 74.Qd1 Qxc4 75.Qf2 g1Q+ 76.Kd2 g2 77.Q1c2 Qh2 78.Kc1 g1Q+ 79.Qff1 f2 80.Qdd2 Q1g6 81.Qf3+ Qgg4 82.Q3e2 Qcf4 83.Qaa2 Qff7 84.Qg2 f1Q+ 85.Qcd1 e5 86.Qca5 e4 87.Qgc8 Q1f4 88.Qcc2 Qfc7 89.Qbb2 Qff4 90.Qac5 Kh6 91.Qcf2 Kh7 92.Qed3 Qhh6 93.Q8a6 Kg8 94.Qdh3 e3 95.Qhh2 e2 96.Q6c4 e1Q 97.Q4d3 Q1e6 98.Q3e2 d4 99.Kb1 d3 100.Qee3 Kf8 101.Qd2e2 Ke8 102.Qde1 d2 103.Qec1 d1Q 104.Qec3 Q1d6 105.Q1e3 Qff7 106.Kc1 Qdb6 107.Qc3d2 Qbb7 108.Kd1 Qea6 109.Qee4 Qhh7 110.Q4e3 Qge6 111.Qee1 Qaa7 112.Ke2 Qdd8 113.Qed1 Q6d7 114.Ke1 Qhg6 115.Qee2 Q6h7

Кто быстрее?

Себе что ли под винду скомпилить?

Самый быстрый код выдает конечно-же Интеловский компилятор.

Перекомпилил под винду (VC++ 6.0). Время уменьшилось до 39 секунд (против 63). Уже, можно сказать, держу Кошака за хвост (32 секунды), ещё 7 секунд и порву ему задницу на британский флаг.

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

Некоторы результаты - интересны:
На моем AMD64 2Gz

Генерируются у меня ходы - как узлы для построения дерева, пергруженными операторами new/delete
(есть идея использовать частично сохраненное дерево). Это конечно не самый быстрый вариант.
Я имел уже опыт написания простенькой шахматной программы на ассемлере в студенческие годы, и писал сразу достаточно оптимальный вариант. Кстати, посмотрев, исходники Greko пришеел к выводу что BitBoard точно не быстрее MailSlot метода.

Итак первая версия perft(6) показала где-то 49с
(Замечание: я считаю что в perft(6) нужно не только сгенерировать шестой полуход но и выполнить его при переборе)

Начал оптимизировать:
Развернул пару циклов, разбил условия на исключающие ветки чтоб не проверялись заведомо неистенные.
Результат: 41с

Переставил условия местами чтоб наиболее вероятные отсечения срабатывали раньше.
Результат: 37с

Самая популярная проверка в генерации: поиск шахующей фигуры на линии.
Изменение в цикле этой процедуры (прверки поменялись местами и условие поменялось наобратное) дали неполохой результат 31с

Еще раз прощелся по ветвлениям, добавил предусловия перед группой проверок
Результат: 29с.

Все из кода больше было не выжать. Нужно смотреть алгоритмы.
Львиную долю времени занимает проверка валидноси хода, типа
doMove( m )
if( kingUnderCheck() ) remove( m )
undoMove();

Придумал очень простую идею как значительно ускорить это место
Реализовал, получилось 21c. Круто думаю.
И это на простом переборе доски без списков фигур. Ну думаю, сделаю списки, раз пошла такая пьянка.
Сделал практически аналогичные тем что у WildCat. И что вы думаете?
Результат: 24с

Вот так-то: Возня со списками по времени перекрывает перебор пустых ячеек.!! Проверенный факт. (при переборе ячеек доски switch исполняется не сравнением по списку а созданием таблицы переходов, т.е. выбор ветки происходит за 1 такт [хвала оптимизаору] )

Но так как у списка фигур есть и другие преемущества при оценке позиции решил оставить все таки его.
Да и по мере уменьшения фигур на доске он будет отыгрываться.

В общем помучал еще несколько часов генератор.
Результат: 22с.

На этом и решил остановиться.

Решил сравнить со своим компом.
Если разделить частоты 2000/950=2.1 а потом умножить на время 2.1*22=46.
У меня 39 у Кота 32. Значит это где то близко к истине. Достигнут физический предел.

Я тут такую фигню заметил. Что в текущей позиции и в позиции возникающей после 2 полуходов очень много одинаковых возможных ходов. Как бы их сразу видеть и не генерировать повторно? Ну хотя бы определить, что ходы такой то фигуры не изменились, тогда можно для этой фигуры ходы не генерировать а брать из предыдущей позиции. Что скажете?

Берем фигуру. Придется для каждого валидного хода проверять не стал ли он ошибочным. И для каждого ошибочного проверить не стал ли он валидным.

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

IMHO: будет медленнее и отлаживаь сложнее.

Вот еще инересный параметр.
Попробуйте генерацию ходов без валидации
(Не проверять остался ли король под шахом)
И сравните perft(6) с обычной версией по времени.
Таким образом сможете посмотреть эффекивнось валидации

У меня.
perft(6) всех ходов = 12с
perft(6) валидных ходов = 22с
Валидация съедает 45%

Попробуйте померять у себя если >60% - могу подсказать способ который примерно уполовинивает время на валидацию.

Есть ещё одна безумная идея. А что если сделать для каждого поля доски свой генератор?. Например, ладья в начальной позиции пойти не может, но мы проверяем 4 попытки хода, по всем лучам. А если будет генератор для поля а1 свой, то будем проверять только 2 луча. Как вам?

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

Такие идеи работают до тех пор пока размер данных и кода не превысит размер кэша процессора.
Можно пробовать, но по моему это уже фанатизм [возможно здравый, так как процесс, очевидно, доставляет удовольствие ]
Да и на общую силу программы эти пару секунд, как отмечалось ранее, слабо повлияют.

Perft не показатель быстродействия программы. В Perft большую часть времени работают MakeMove/UnmakeMove. Но в реальном переборе MakeMove/UnmakeMove вызываются не каждый раз как в Perft. Списки фигур замедляют именно MakeMove/UnmakeMove, что для реальной программы не так существенно.