Шахматы, а именно алгоритм alpha-beta, где же лучший ход ?

Тема в разделе "Машинное отделение", создана пользователем sensey_alex, 28 янв 2008.

  1. TopicStarter Overlay

    sensey_alex Учаcтник

    • Участник
    Рег.:
    28.01.2008
    Сообщения:
    12
    Симпатии:
    0
    Репутация:
    0
    Оффлайн
    Я новичек
    Как не смешно: вроде идею понял, а где фомируется имеено лучший ход??? Кто поможет?

    Вот мой следующий алгоритм:

    [c]float CChessEngine::Search(const bool isWhite, float alpha, float beta, int depth, const int ply)
    {
    // Глубина закончилась
    if(depth == 0)
    {
    return Evaluate(isWhite);
    }

    --depth;
    // Генерация перемещений
    std::vector<CMove *> vecMove;
    Generate(isWhite, vecMove);

    const bool bOpColor = !isWhite; // цвет опонента
    float fScore = -INFINITY;

    for(size_t i(0); i < vecMove.size(); ++i)
    {
    // Типа отсечка
    if(alpha > beta) break;

    Move(isWhite, *vecMove); // Делаем ход
    const float fTemp = -Search(bOpColor, -beta, -alpha, depth, ply + 1);
    UnMove(isWhite, *vecMove); // Возвращаем ход назад
    const size_t sizeWhiteFig2 = m_vecWhiteFigure.size();

    if(fTemp > alpha)
    {
    if(isWhite && ply == 0)
    m_GlMove = vecMove; // Я так понимаю лучший ход тута :)
    alpha = fTemp;
    }
    } // for(size_t i(0); i < vecMove.size(); ++i)

    return fScore;
    }
    [/c]
    /////////////////////////////////////////////////////////////////////////////////
    /////////////////////////////////////////////////////////////////////////////////

    Пояснения по коду:

    m_GlMove - тут должен быть лучший ход!
    метод Evaluate - эторасчет текуще позиции;
    Generate - метод ,который формирует ходы для анализа;
    все остальное я думаю понятно :)))

    Жду допомоги :))))
  2. bankuss Александр

    • Заслуженный
    • Участник
    • Старожил
    Рег.:
    23.05.2006
    Сообщения:
    1.072
    Симпатии:
    33
    Репутация:
    1
    Оффлайн
    Может так проще?
    Код:
    int             Search(int alpha, int beta, int depth, MOVE * pBestMove)
    {
        int             i,
                        value,
                        havemove,
                        movecnt;
        MOVE            moveBuf[200],
                        tmpMove;
        
        nodes++; /* visiting a node, count it */
        havemove = 0;
        pBestMove->type = MOVE_TYPE_NONE;
        movecnt = Gen(side, moveBuf); /* generate all moves for current position */
        /* loop through the moves */
        for (i = 0; i < movecnt; ++i) {
            if (!MakeMove(moveBuf[i])) {
                TakeBack();
                continue;
            }
            havemove = 1;
            if (depth - 1 > 0) /* If depth is still, continue to search deeper */
                value = -Search(-beta, -alpha, depth - 1, &tmpMove);
            else /* If no depth left (leaf node), go to evalute that position */
                value = Eval(); 
            TakeBack();
            if (value > alpha) {
                /* This move is so good and caused a cutoff */
                if (value >= beta)
                    return beta;
                alpha = value;
                *pBestMove = moveBuf[i]; /* so far, current move is the best reaction
                                          * for current position */
            }
        }
        if (!havemove) {            /* If no legal moves, that is checkmate or
                                     * stalemate */
            if (IsInCheck(side))
                return -MATE + ply; /* add ply to find the longest path to lose or shortest path to win */
            else
                return 0;
        }
        return alpha;
    }
  3. WildCat Коршунов Игорь

    • Команда форума
    Рег.:
    04.05.2006
    Сообщения:
    3.599
    Симпатии:
    3
    Репутация:
    0
    Адрес:
    Гомель
    Оффлайн
    Я не понял о чем ты спрашиваешь.
  4. TopicStarter Overlay

    sensey_alex Учаcтник

    • Участник
    Рег.:
    28.01.2008
    Сообщения:
    12
    Симпатии:
    0
    Репутация:
    0
    Оффлайн
    Где в самом алгоритме из всего вектора std::vector<CMove *> vecMove; лучший ход ?

    Это когда if(fTemp > alpha) ???? я Прав
  5. WildCat Коршунов Игорь

    • Команда форума
    Рег.:
    04.05.2006
    Сообщения:
    3.599
    Симпатии:
    3
    Репутация:
    0
    Адрес:
    Гомель
    Оффлайн
    i-ый ход лучше альфы и лучший среди уже рассмотренных.

    А тут isWhite лишнее.
  6. TopicStarter Overlay

    sensey_alex Учаcтник

    • Участник
    Рег.:
    28.01.2008
    Сообщения:
    12
    Симпатии:
    0
    Репутация:
    0
    Оффлайн
    Спасибки, будем пробовать!
  7. WildCat Коршунов Игорь

    • Команда форума
    Рег.:
    04.05.2006
    Сообщения:
    3.599
    Симпатии:
    3
    Репутация:
    0
    Адрес:
    Гомель
    Оффлайн
    Только без ФВ будет играть криво.
  8. WinPooh В.М.

    • Команда форума
    Рег.:
    13.02.2006
    Сообщения:
    9.220
    Симпатии:
    2.523
    Репутация:
    90
    Адрес:
    Москва
    Оффлайн
    Немного не по теме вопроса: рекомендую избавиться от генерации ходов в локальный вектор. Это очень сильно просаживает производительность (аллокация-деаллокация памяти по 30-40 раз в каждом узле - по разу на каждый push_back). Стоит завести глобальный пул векторов с ходами.
  9. TopicStarter Overlay

    sensey_alex Учаcтник

    • Участник
    Рег.:
    28.01.2008
    Сообщения:
    12
    Симпатии:
    0
    Репутация:
    0
    Оффлайн
    Что такое ФВ ????
  10. TopicStarter Overlay

    sensey_alex Учаcтник

    • Участник
    Рег.:
    28.01.2008
    Сообщения:
    12
    Симпатии:
    0
    Репутация:
    0
    Оффлайн
    Как же мона сделать глобальный, если это процедура в стеке должна лежать и ... данные тоже должны быть локальными для каждой
  11. bankuss Александр

    • Заслуженный
    • Участник
    • Старожил
    Рег.:
    23.05.2006
    Сообщения:
    1.072
    Симпатии:
    33
    Репутация:
    1
    Оффлайн
    Да и без векторов все прекрасно и шустро работает :)
  12. ProstoTak Ветеран

    • Ветеран
    Рег.:
    11.02.2006
    Сообщения:
    5.487
    Симпатии:
    123
    Репутация:
    1
    Оффлайн
    sensey_alex "Машина играет в шахматы" Адельсон-Вельский Г.М., Арлазаров В.Л., Битман А.Р., Донской М.В.
    Для начала найди эту книгу. И почитай, естественно :)
  13. WildCat Коршунов Игорь

    • Команда форума
    Рег.:
    04.05.2006
    Сообщения:
    3.599
    Симпатии:
    3
    Репутация:
    0
    Адрес:
    Гомель
    Оффлайн
    Вместо простого вызова оценки вызывается функция перебора, которая рассматривает только взятия.

    Например, твой перебор на глубину 3 такой вариант 1. e4 a6 2. Bxa6 оценит как выигрывающий пешку. А если рассмотреть взятия дальше, то видно, что теряется слон.
  14. WinPooh В.М.

    • Команда форума
    Рег.:
    13.02.2006
    Сообщения:
    9.220
    Симпатии:
    2.523
    Репутация:
    90
    Адрес:
    Москва
    Оффлайн
    Передавай текущую глубину от корня в качестве параметра функции.
    Что-то вроде этого:
    Код:
    const int MAX_PLY = 128;
    vector<Move> g_pool[MAX_PLY];
    
    int AlphaBeta(int alpha, int beta, int ply, int depth)
    {
       vector<Move>& mvvector = g_pool[ply];
       mvvector.clear();
       ...
       GenMoves(mvvector);
       for (...)
       {
          ...
          ... = - AlphaBeta(-beta, -alpha, ply + 1, depth - 1);
       }
    }
    Фишка в том, что память вектором выделится один раз, а потом после clear() библиотека STL оставит некий буфер, величину которого можно узнать через функцию capacity(). И повторного выделения при новой генерации ходов в тот же вектор, скорее всего, не будет.
  15. WinPooh В.М.

    • Команда форума
    Рег.:
    13.02.2006
    Сообщения:
    9.220
    Симпатии:
    2.523
    Репутация:
    90
    Адрес:
    Москва
    Оффлайн
    Да, так. Но с векторами шустрее работают мозги разработчика :)
  16. TopicStarter Overlay

    sensey_alex Учаcтник

    • Участник
    Рег.:
    28.01.2008
    Сообщения:
    12
    Симпатии:
    0
    Репутация:
    0
    Оффлайн
    Так а если взятий нет, или они ни к чему не приводят?
  17. TopicStarter Overlay

    sensey_alex Учаcтник

    • Участник
    Рег.:
    28.01.2008
    Сообщения:
    12
    Симпатии:
    0
    Репутация:
    0
    Оффлайн
    ХОРОШАЯ ИДЕЯ, ВОЗЬМЕМ НА ВООРУЖЕНИЕ
  18. WildCat Коршунов Игорь

    • Команда форума
    Рег.:
    04.05.2006
    Сообщения:
    3.599
    Симпатии:
    3
    Репутация:
    0
    Адрес:
    Гомель
    Оффлайн
    Тем лучше. :)
  19. WinPooh В.М.

    • Команда форума
    Рег.:
    13.02.2006
    Сообщения:
    9.220
    Симпатии:
    2.523
    Репутация:
    90
    Адрес:
    Москва
    Оффлайн
  20. TopicStarter Overlay

    sensey_alex Учаcтник

    • Участник
    Рег.:
    28.01.2008
    Сообщения:
    12
    Симпатии:
    0
    Репутация:
    0
    Оффлайн
    А такое же, но только с перламутровыми пуг ..., тьфу ты, такое же но на русском нету? ну может случайно
  21. WinPooh В.М.

    • Команда форума
    Рег.:
    13.02.2006
    Сообщения:
    9.220
    Симпатии:
    2.523
    Репутация:
    90
    Адрес:
    Москва
    Оффлайн
    Даже не знаю. Попробуй глянуть на Booot и Стрелку. Там комментарии на русском. Правда, уровень подробности разъяснений может отличаться.
  22. Осипов Юрий Учаcтник

    • Участник
    Рег.:
    18.06.2007
    Сообщения:
    388
    Симпатии:
    389
    Репутация:
    11
    Адрес:
    Правда
    Оффлайн
    Booot, однако, на Паскале.
    А в Стрелке search вообще без комментариев. Да и на битбордах с непривычки можно голову сломать. Хотя, многие говорят, что Стрелка очень просто написана - даже Ури Бласс почти все понял.
  23. WinPooh В.М.

    • Команда форума
    Рег.:
    13.02.2006
    Сообщения:
    9.220
    Симпатии:
    2.523
    Репутация:
    90
    Адрес:
    Москва
    Оффлайн
  24. WildCat Коршунов Игорь

    • Команда форума
    Рег.:
    04.05.2006
    Сообщения:
    3.599
    Симпатии:
    3
    Репутация:
    0
    Адрес:
    Гомель
    Оффлайн
    Стрелку лучше не смотри пока. Это не для новичков.

    Программа Корнилова: О.Бендер (исходники открыты). http://www.sbor.net/~e_k/
    Еще можно глянуть программу ChessTerminator75 - Ифрит. http://andchess2006.narod.ru/

    А вообще, по поводу русских движков лучше сходить сюда: http://sdchess.ru
  25. ProstoTak Ветеран

    • Ветеран
    Рег.:
    11.02.2006
    Сообщения:
    5.487
    Симпатии:
    123
    Репутация:
    1
    Оффлайн
    15 382 руб. Это что её цена или я чего то не понимаю в этой жизни?
  26. chitatelj Заслуженный

    • Заслуженный
    Рег.:
    01.04.2006
    Сообщения:
    100
    Симпатии:
    0
    Репутация:
    0
    Оффлайн
    Это белорусский сайт, рубли тоже.

Поделиться этой страницей