Списки фигур

все таки заведу эту тему
какие реализации? (Си интересует), что лучше там хранить.
связка с исполнителем\возвращателем хода.

если можно примеры

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

WildCat а если без color ? в типе и цвет прописать. а n это что?

typedef struct tagPI {
int pc; // тип фигуры
int co; // цвет
BOOL fDead; // было ли съедено
int isq; // индекс поля на доске
int val; // материальная оценка
} PI, * PPI;

typedef struct tagSQ {
PPI ppi; //указатель на фигуру, или NULL.
int isq; // индекс на внутренней доске.
} SQ, * PSQ;

вот такое нашел

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

У меня списки такие:

Код:

struct FigureList
{
    int m_count;
    idx_t m_indexes[10];
};

struct Cell
{
    cell_t m_cell;
    int    m_listIdx;
};

class Board
{
...
    Cell           m_cells[FIELD_SIZE];
    FigureList     m_lists[MAX_FIGURE_VALUE+1];
...
};

С выравниванием данных пока не заморачиваюсь

Самое простое - это добавление (естевственно все inline)

Код:

    void setFigure( idx_t idx, cell_t figure )
    {
        FigureList& list = m_lists[figure];
        list.m_indexes[ list.m_count ] = idx;
        m_cells[idx].m_cell = figure;
        m_cells[idx].m_listIdx = list.m_count;
        list.m_count++;
        ...
    }

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

Код:

    void clearFigure( idx_t idx, cell_t figure )
    {
        FigureList& list = m_lists[figure];
        list.m_count--;
        idx_t movedCellIdx = list.m_indexes[ list.m_count ];
        int deletedListIdx = m_cells[idx].m_listIdx;
        m_cells[ movedCellIdx ].m_listIdx = deletedListIdx;
        list.m_indexes[ deletedListIdx ] = movedCellIdx;
        m_cells[idx].m_cell = CELL_EMPTY;
#ifdef _DEBUG
        list.m_indexes[ list.m_count ] = 0;
        m_cells[idx].m_listIdx = -1;
#endif
        ...
    }

Есть еще перемещение, просто это быстрее чем удалить и поставить

Ктати выравнял размер FigureList до кратного степени двойки.
Это дало выигрыш 0.2с или 1% в perft(6)

Параметр cell_t figure в clearFigure() не обязательный, но с ним оптимизатор лучше работает, так как фигура уже обычно есть в каком либо регистре (функция инлайнится в do/undo move), и не надо повторно читать ее с доски. Разница - ощутима.

Ну пока всю свою работу делать OpenSource - не планирую
Да и версионный контроль у меня не налажен,
Версия без списков - не сохранилась.

Но перебор 32 пустых ячеек сводился к 32 безусловным переходам (табица переходов switch оператора)
А без списков трудно проверять наличие 2х слонов, например (разве что инкрементально).

Без списков легко проверяется наличие двух слонов.
Например у меня В структуре позиции хранится количество фигур каждого вида (без списка)

Я бы назвал это кастрированными списками
Это вариант може оказаться, кстати, самым выгодным в плане быстродействия.

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

В шашках доска сканируется дважды и соотношение время_на добавление_ходов(проверки возможности хода)/время_поиска_шашки - значительно меньше чем в шахматах.
Хотя ведь можно не хранить списки, а формировать их при первом сканировании. (при проверке на возможность взятия)

Ну вот смотри

Код:

void f( int v )
{
    switch( v )
    {
    case 10:  g_v = 101; break;
    case 12:  g_v = 102; break;
    case 1:   g_v = 103; break;
    case 22:  g_v = 104; break;
    default:  g_v = 105; break;
    }
}

компилируется в

Код:

f:
00401000  add         eax,0FFFFFFFFh 
00401003  cmp         eax,15h 
00401006  ja          $LN2+0Bh (401042h) 
00401008  movzx       eax,byte ptr  (401064h)[eax] 
0040100F  jmp         dword ptr  (401050h)[eax*4] 
$LN5:
00401016  mov         dword ptr [g_v (403378h)],65h 
00401020  ret              
$LN4:
00401021  mov         dword ptr [g_v (403378h)],66h 
0040102B  ret              
$LN3:
0040102C  mov         dword ptr [g_v (403378h)],67h 
00401036  ret              
$LN2:
00401037  mov         dword ptr [g_v (403378h)],68h 
00401041  ret              
00401042  mov         dword ptr [g_v (403378h)],69h 
0040104C  ret              
0040104D  lea         ecx,[ecx] 
00401050  db          2ch  
00401051  db          10h  
00401052  db          40h  
00401053  db          00h  
00401054  db          16h  
00401055  db          10h  
00401056  db          40h  
00401057  db          00h  
00401058  db          21h  
00401059  db          10h  
0040105A  db          40h  
0040105B  db          00h  
0040105C  db          37h  
0040105D  db          10h  
0040105E  db          40h  
0040105F  db          00h  
00401060  db          42h  
00401061  db          10h  
00401062  db          40h  
00401063  db          00h  
00401064  db          00h  
00401065  db          04h  
00401066  db          04h  
00401067  db          04h  
00401068  db          04h  
00401069  db          04h  
0040106A  db          04h  
0040106B  db          04h  
0040106C  db          04h  
0040106D  db          01h  
0040106E  db          04h  
0040106F  db          02h  
00401070  db          04h  
00401071  db          04h  
00401072  db          04h  
00401073  db          04h  
00401074  db          04h  
00401075  db          04h  
00401076  db          04h  
00401077  db          04h  
00401078  db          04h  
00401079  db          03h

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

Современные компиляторы MS с оптимизацией switch по целому числу справляются блестяще.

я у себя if then else использовал. switch не пробовал.