Генератор ходов

Вот решил написать шахматный движок , но мой генератор получился ОЧЕНЬ тормозным
[1500 kN/s] , так что он отправился в Recycler Bin ...
Как я делал : __int8 board [144] - доска
board movegen (board old, nm &nextmove) - генерирует board с одной перемещенной фигурой
struct nm
{
__int8 num;// номер фигуры которая должна ходить
__int8 dir;// направление
__int8 step;// для дальнобойных
bool use;//movegen рекурсивная и может в конце концов вернуть 0, т.е. board old;
}
Главная проблема думаю , что нет UNMAKE - MAKE_MOVE
Я не любитель изучать исходники Crafty и Fruit , но как я понимаю там
AddCaptures () генерирует все ходы в нек позиции и заносит в нек массив , а MAKE_MOVE и UNMAKE -
исполняют их .... Но я так и не понял в каком виде AddCaptures сохраняет ходы ...
Кстати какой должна быть чистая скорость генератора , что-то около 2000 - 2500 kN/s на моём Athlon 3000 ?

А как тестировал скорость генератора?

объявил глобальную переменную int PositionsTotal и вместо оценочной ф-ции которой нет написал
PositionsTotal++; )
в начале и в конце вызвал GetLocalTime

правильно что AddCaptures () генерирует сразу все ходы , или только один ход за вызов ?

Fruit :
static void add_captures(list_t * list, const board_t * board)
кусок ф-ции :
...
case Knight64:

to = from - 33;
if (FLAG_IS(board->square[to],opp_flag)) LIST_ADD(list,MOVE_MAKE(from,to));

to = from - 31;
if (FLAG_IS(board->square[to],opp_flag)) LIST_ADD(list,MOVE_MAKE(from,to));

to = from - 18;
if (FLAG_IS(board->square[to],opp_flag)) LIST_ADD(list,MOVE_MAKE(from,to));
...
Получается ,что если мне нужно просчитать на несколько полуходов, я должен сохранить всю историю ходов...
т.е. я в начале должен объявит некую " Move AllMoves[max_depth] ", в кэш такая бандура влезет ?
ведь max_depth может быть и 100...

неохото потом код заново переколбашивать ...

может кто-нибудь знает где взять такие исходники , чтоб я сразу въехал ...
во Fruit -овых макрос на макросе ... в crafty много объяснений но сами функции от этого только хуже воспринимаются

сейчас попросим гугля помочь

итак готово ...
TSCP 181 ... смотрю архив .... отлично файлов не много ... ногу не сломаешь
приступим к изучению

readme меня порадовал :

TSCP is intended for people who want to learn about chess programming. Its
source code is designed to be very easy to understand.

кстати исходники действительно хорошие ... всё понятно ... таких бы побольше

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

я тоже так думаю ...
хочу лишь почерпнуть хорошие идеи ... одна голова хорошо, а две лучше

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

В шашках написал первый генератор - получился очень похожий на генератор из открытых исходников Коршунова... Второй генератор скорей всего не похож ни на что существующее, весьма заморочный но очень быстрый. Вот и что-то новое! Осталось только довести его до ума - раз уж иду на рекорд, значит нужно поставить рекорд!

Надо немного отвлечься от шахмат

В русских, но метод быстрой генерации простых ходов с одновременной проверкой на взятия (позиции в которых нет взятий встречаются в 4-5 раз чаще, чем те, в которых взятия есть) применим и в международных... Правило большинства особо не усложняет генератор (просто из рекурсивной процедуры возвращаем "максимальное взятие") То есть фактически усложнения нет.

???? При обчном способе записи взятий, если не записывать взятия "меньшие" уже найденного - и так все взятия окажутся отсортированными... Только в обратном порядке (каждое следующее записанное не меньше предыдущего.)

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

atoku да так.. времени мало было на анализ вот и результат

Код:

КолВзятий=0;
колЛегальныхВзятий=0;
МаксВзятие=0;
Процедура ДобавлениеВзятия(Взятие)
  колЛегальныхВзятий=колЛегальныхВзятий+1;
  колВзятий=колВзятий+1;
  СписокВзятий[колВзятий]=Взятие;
КонецПроцедуры;
Процедура ДобавлениеЛегальногоВзятия(количествоСъеденныхШашек, Взятие)
  Если КоличествоСъеденныхШашек<МаксВзятие Тогда
    Возврат;
  Иначе
      Если количествоСъеденныхШашек>МаксВзятие Тогда
          МаксВзятие=КоличествоСъеденныхШашек;
          колЛегальныхВзятий=0;
      КонецЕсли;
     ДобавлениеВзятия(Взятие);
  КонецЕсли;
КонецПроцедуры;

Всего легальных взятий - колЛегальныхВзятий...
Извлечение I-го легального взятия СписокВзятий[колВзятий+1-I]

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

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

atoku ну можно сказать что у нас динамическое равновесие но у тебя чуть лучше за счет развития, все зависит от твоей активности