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

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

Для перебора вообще пофиг порядок генерации, так как всё-равно потом все ходы сортируются по истории и т.п.

NS а крайние узлы? там сортировать еще не почему или это не влияет на перебор?

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

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

Можно как Greko Валидировать в конце make_move( ... )

Любой ход может привести к вскрытому шаху. Валидировать надо все.

Согласен. Именно по этому их и оставил.
Я просто хотел указать на ошибочность вот этого высказывания
http://kasparovchess.crestbook.com/viewtopic.php?pid=81320#p81320
(по моему мнению).

Вторая серия.
Не выдержал, придумал как еще оптимизировать валидацию.
В Результате неплохое ускорение
Все ходы perft(6): 11.19c
Валидные ходы: 14.48c (Валидация 23% машинного времени)

Для сравнения собрал Greko 5.3 на моем VS 2005 с анологичной оптимизацией. perft(6) он выдал 17.72с
Закомментировал валидацию в make_move. Без нее Greko выдал 15.94
Сразу чувствуется BitBoard движок, где проверка на шах делается наложением нескольких масок.
По моим ощущениям, если плотно занятся Грекой, из него можно выжать время около 10с.

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

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

Спасибо за идею. Я ещё так не оптимизировал

Нифига себе "не очень большой". Очень даже хороший процент!

Чтоб оценить эффекивность валидации ходов по шаху. (свой король после хода под шахом)
убрал эту проверку в конце make_move, а именно вот этот блок
if (is_attacked(pos, pos->King[side], opp))
{
unmake_move(pos);
return 0;
}

Время уменьшилось на 1.78с
Таким образом в Greko Валидация по шаху занимает 10% от всей генерации.
В MailSlot движке - Генерировать ходы - быстрее, но проверять на шах - дольше. Если без оптимизаций, то где-то 65% времени занимает валидация. Мне удалось время валидации сократить примерно в 5 раз. (с 15с до 3с в моем случае)

http://dev.enterra-inc.com/perft/performance.exe (40K)

На твоем компе думаю можно ожидать в районе 40с.
Сначала выдает perft без валидации, потом с ней.
Как запустишь - делись результатами.

Библиотека DLL MSVCP80.dll не найдена

Кстати нашел в одном месте полезные данные для проверки генерации, мне - очень пригодились

Код:

Perft tests:

Initial position: rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq -

1                20 
2               400
3              8902 
4            197281 
5           4865609 
6         119060324 
7        3195901860
8       84998978956
9     2439530234167

mixed test: r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R w KQkq -

1                48
2              2039     
3             97862 
4           4085603 
5         193690690
6        8031647685


castle test:   r3k2r/3q4/2n1b3/7n/1bB5/2N2N2/1B2Q3/R3K2R w KQkq - 0 1

1                47
2              2409
3            111695
4           5664262
5         269506799
6       13523904666
  
ep test:  rnbq1bnr/1pppkp1p/4p3/2P1P3/p5p1/8/PP1PKPPP/RNBQ1BNR w - - 0 1

1                22 
2               491 
3             12571 
4            295376 
5           8296614 
6         205958173
  
promotion test:  rn1q1bnr/1bP1kp1P/1p2p3/p7/8/8/PP1pKPpP/RNBQ1BNR w - - 0 1

1                37
2              1492
3             48572
4           2010006
5          67867493
6        2847190653
  
No nothing test: r6r/3qk3/2n1b3/7n/1bB5/2N2N2/1B2QK2/R6R w - - 0 1

1                62 
2              3225
3            176531
4           8773247
5         461252378

Шарк, скомпиль так шоб она ничего не требовала

Слинковал Runtime статически
http://dev.enterra-inc.com/perft/performance_s.exe 155К
Кстати cтала быстрее на пол секунды!!!
Запускай несколько раз чтоб получить истинные результаты, первый раз - обычно хуже.

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

Теперь выдает:
Исключение unknown software exeption(0x000001d) в приложении по адресу 0x0040679d

У меня целерон и 2000 винда. Может ты под 64 разрядную компилишь?

у меня на П4-3000 сгенерил за 14.2 сек. мой тест выдает за 18 сек. не так уж и далеко

Напиши мне на ksharenkov собака yandex точка ру. Чтоб не засорять форум.
А модератор пусть потом почистит нашу эпопею с экзешником.

Написал

Яндекса, блин, не дождешься
http://dev.enterra-inc.com/perft/performance_s_nosse2.exe (без SSE2)

Empty function:
Time: 0.271 Counter: 30000000 Speed: 110701107

perftClear(4)=197742
Time: 0.05 Counter: 1 Speed: 20

perftClear(5)=4897256
Time: 1.142 Counter: 1 Speed: 0.8756567426

perftClear(6)=120922167
Time: 28.3 Counter: 1 Speed: 0.03533568905

perftValid(4)=197281
Time: 0.07 Counter: 1 Speed: 14.28571429

perftValid(5)=4865609
Time: 1.472 Counter: 1 Speed: 0.6793478261

perftValid(6)=119060324
Time: 35.722 Counter: 1 Speed: 0.02799395331


Это ещё круче чем у Кошака, потому что у меня сейчас 900 целерон, а дома 950. Так шо дома будет меньше чем 32 секунды

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

если оригинал выглядел так

Код:

void Board::generateWhiteValidMoves( MovesChunk& chunk )
{
    generateWhitePossibleMoves( chunk );
    
    int i=0;
    while( i<chunk.m_count )
    {
        MoveNode* move = chunk.m_nodes[i];
            
        doWhiteMove( move );
        if( isWhiteUnderCheck() ) // not removes check
            chunk.remove( i );
        else
            i++;
        undoWhiteMove();
     }
 }

То для оптимизации мы делаем следующие изменения:

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

Код:

//——————————————————————————————————————-
// вспомогательные массивы
int arKnightOffsets[8] = 
{
    -FIELD_WIDTH*2+1, 
    -FIELD_WIDTH+2, 
    +FIELD_WIDTH+2, 
    +FIELD_WIDTH*2+1, 
    +FIELD_WIDTH*2-1, 
    +FIELD_WIDTH-2, 
    -FIELD_WIDTH-2, 
    -FIELD_WIDTH*2-1
};

//——————————————————————————————————————-
int arKingOffsets[8] = 
{
    -FIELD_WIDTH+0, 
    -FIELD_WIDTH+1, 
    +0+1, 
    +FIELD_WIDTH+1, 
    +FIELD_WIDTH+0, 
    +FIELD_WIDTH-1, 
    +0-1, 
    -FIELD_WIDTH-1
};

// собственно массив и его заполнение
unsigned char arHitZone[FIELD_SIZE][ 128 /*FIELD_SIZE*/];
const unsigned char FL_MAY_REMOVE_LINE_CHECK = 0x20;
const unsigned char FL_MAY_REMOVE_KNIGHT_CHECK = 0x40;
const unsigned char FL_MAY_REMOVE_CHECK = FL_MAY_REMOVE_KNIGHT_CHECK | FL_MAY_REMOVE_LINE_CHECK;
const unsigned char FL_MAY_ADD_CHECK = 0x80;

//——————————————————————————————————————-
void addLineZone( unsigned char* zone, int idx, int offset, int lineNum )
{
    int idx2=idx;
    for( ;; ) 
    {
        idx2 += offset;
        if( arEmptyPosition[idx2]==CELL_EMPTY )
        {
            zone[idx2] |= lineNum; // Внимание! сохраням линию с которой может быть атакован король
            zone[idx2] |= FL_MAY_REMOVE_LINE_CHECK;
            
            // Ходы с края доски которые не могут вскрыть шах
            if( arIdxToRow[idx2]!=0 && arIdxToRow[idx2]!=7 && arIdxToCol[idx2]!=0 && arIdxToCol[idx2]!=7)
                    zone[idx2] |= FL_MAY_ADD_CHECK;
            
            if( arIdxToRow[idx]==0 && arIdxToRow[idx2]==0 )
                    zone[idx2] |= FL_MAY_ADD_CHECK;
            if( arIdxToRow[idx]==7 && arIdxToRow[idx2]==7 )
                    zone[idx2] |= FL_MAY_ADD_CHECK;
            
            if( arIdxToCol[idx]==0 && arIdxToCol[idx2]==0 )
                    zone[idx2] |= FL_MAY_ADD_CHECK;
            if( arIdxToCol[idx]==7 && arIdxToCol[idx2]==7 )
                    zone[idx2] |= FL_MAY_ADD_CHECK;
        }
        else
            break;
    }
}

//——————————————————————————————————————-
void initHitZone( int idx )
{
    unsigned char* zone = arHitZone[ idx ];

    for( int i=0; i<8; i++ )
        addLineZone( zone, idx, arKingOffsets[i], i );

    for( int i=0; i<8; i++ )
        zone[ idx + arKnightOffsets[i] ] |= FL_MAY_REMOVE_KNIGHT_CHECK;
}

//——————————————————————————————————————-
void initHitZones()
{
    for( int i=0; i<FIELD_SIZE; i++ )
        for( int j=0; j<FIELD_SIZE; j++ )
            arHitZone[i][j] = 0;
 
    for( int i=0; i<64; i++ )
    {
        int idx = arBoardIndexes[i];
        initHitZone( idx );
    }
}

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

Код:

//——————————————————————————————————————-
bool Board::isBlackFigOrQueenOrPawnOnLine( idx_t idx, int offset, cell_t figure1 ) const
{
    int idx2 = idx;
    
    // первая ячейка с проверкой пешки - вне цикла
    idx2 += offset;
    cell_t dst = m_cells[ idx2 ].m_cell;

    if( dst==CELL_FILL )
        return false;

    if( dst==CELL_BLACK_PAWN )
        return true;

    if( dst==CELL_BLACK_QUEEN || dst==figure1 )
         return true;

    for(;;)
    {
        idx2 += offset;
        dst = m_cells[ idx2 ].m_cell;

        if( dst==CELL_FILL )
            return false;

        if( dst==CELL_BLACK_QUEEN || dst==figure1 )
            return true;
    }
}

Ну и в конце нам нужен массив атакующих фигур по линиям за исключением ферзя

Код:

//——————————————————————————————————————-
cell_t arBlackOffsetsFigures[8] = 
{
    CELL_BLACK_ROOK,
    CELL_BLACK_BISHOP,
    CELL_BLACK_ROOK,
    CELL_BLACK_BISHOP,
    CELL_BLACK_ROOK,
    CELL_BLACK_BISHOP,
    CELL_BLACK_ROOK,
    CELL_BLACK_BISHOP
};

И наконец сама процедура становится такой

Код:

//——————————————————————————————————————-
void Board::generateWhiteValidMoves( MovesChunk& chunk )
{
    generateWhitePossibleMoves( chunk );
    
    bool wasUnderCheck = isWhiteUnderCheck();
    if( wasUnderCheck )
    {
        int i=0;
        while( i<chunk.m_count )
        {
            MoveNode* move = chunk.m_nodes[i];
            
            bool mayRemoveCheck = move->m_from==whiteKingIdx() || move->m_flags & FL_PAWN_PASS_CAPTURE;
            if( mayRemoveCheck )
            {
                doWhiteMove( move );
                if( isWhiteUnderCheck() ) // not removes check
                    chunk.remove( i );
                else
                    i++;
                undoWhiteMove();
            }
            else
            {
                unsigned char hit = arHitZone[whiteKingIdx()][ move->m_to ];
                int line = hit & 0xF;

                if( (hit & FL_MAY_REMOVE_KNIGHT_CHECK) || (hit & FL_MAY_REMOVE_LINE_CHECK) &&
                    isBlackFigOrQueenOrPawnOnLine( whiteKingIdx(), arKingOffsets[line], arBlackOffsetsFigures[line]) )
                {
                    doWhiteMove( move );
                    if( isWhiteUnderCheck() ) // not removes check
                        chunk.remove( i );
                    else
                        i++;
                    undoWhiteMove();
                }
                else
                {
                    chunk.remove( i );
                }
            }
        }
    }
    else
    {
        int i=0;
        while( i<chunk.m_count )
        {
            MoveNode* move = chunk.m_nodes[i];
            bool mayAddCheck = move->m_from==whiteKingIdx() || move->m_flags & FL_PAWN_PASS_CAPTURE;
            if( mayAddCheck )
            {
                doWhiteMove( move );
                if( isWhiteUnderCheck() ) // not removes check
                    chunk.remove( i );
                else
                    i++;
                undoWhiteMove();
            }
            else
            {
                unsigned char hit = arHitZone[whiteKingIdx()][ move->m_from ];
                int line = hit & 0xF;

                if( (hit & FL_MAY_ADD_CHECK) &&  
                    isBlackFigOrQueenOrPawnOnLine( whiteKingIdx(), arKingOffsets[line], arBlackOffsetsFigures[line] ) )
                {
                    doWhiteMove( move );
                    if( isWhiteUnderCheck() ) // not removes check
                        chunk.remove( i );
                    else
                        i++;
                    undoWhiteMove();
                }
                else
                {
                    i++;
                }
            }
        }
    }
}

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

Дерзайте.
Если кому пригодится упомените меня в списке Asknowledgements

Если есть вопросы - отвечу.
Поверял на корректность - списком тестов которые выложил здесь выше.

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

Ну не знаю, не знаю. У меня та же идея умещается в 10 строк
Нет вру в 20

Код:

char IsRentgenWK(char *table) {
char L,p2,f,sb,sw;

  for(L=0;L<4;L++){
     sb=sw=0;
     f=table[p2=WKP+LB[L]];
     while(f != -1) {
       if(f>=WP && f<=WQ) sw++;
       if(f>=BP && f<=BK) sb++;
       if(f==BB || f==BQ) return 1;
       if(sb==1) break; // По этому лучу нет рентгена
       if(sw==2) break; // По этому лучу нет рентгена
       f=table[p2+=LB[L]];
     }
  }
  for(L=0;L<4;L++){
     sb=sw=0;
     f=table[p2=WKP+LR[L]];
     while(f != -1) {
       if(f>=WP && f<=WQ) sw++;
       if(f>=BP && f<=BK) sb++;
       if(f==BR || f==BQ) return 1;
       if(sb==1) break; // По этому лучу нет рентгена
       if(sw==2) break; // По этому лучу нет рентгена
       f=table[p2+=LR[L]];
     }
  }
  return 0;
}

да вобщем все просто... зачем проверять фигуру если она не на линии короля? (для слайд), а кони и пешки и так шустро секутся.

У меня как раз пляс идёт от короля. WKP - это позиция белого (в данном случае) короля.

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

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

сравнение сделать можно через предрасчитанный массив к примеру - mass [king_sq] [slide_piece_sq] - ну и там хранить 1 и 0, к примеру [a1] [h8] = 1 (проверяем линию) , [a1] [h7] = 0.
если ноль то просто идем к следующей фигуре, проверять нефик.

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

Не рекомендую совмещать.
Тут дело как раз в мелочах, при частичной реализации, эффект получается гораздо хуже.
Например, известно что ход с края доски не может вскрыть шах если король не стоит на том же краю доски.
Вроде мелочь, На нескольких клеточках меньше флажков. А из 12ти отыгранных секунд, 3 приходятся именно на этот фокус !!! (25%)