Генерация дебютной библиотеки

Принято дебютные библиотеки делать так:

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

Здесь мне хотелось бы обсудить 3-ий подход.
Может у кого есть особо ценные идеи?
Коротко мои собственные:
На любой ход противника находим один лучший ответ (перебор на пару минут). Варианты в которых у нас оценка больше пороговой обрываем т.к. считаем, что получили позу с перевесом. Процедуру запускаем два раза: за белых и за черных.
Запоминаем оценку не только лучшего, но и всех остальных. Т.к. при продлении варианта может оказаться, что оценка лучшего упадет и лучшим станет другой ход. Тогда придется разрабатывать вариант с этим ходом.

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

Немного о том, зачем все это нужно.
Мне предстоит играть матч-реванш против Cake (одна из лучших чекерсных программ) в чекерсные поддавки (29.05 в 23:45 по Москве на www.kurnik.org). Первый матч закончился месяц назад 3-0 (http://www.fierz.ch/checkers.htm). Теперь я ожидаю, что сопротивление будет более серьезным. И мне тоже хочется получше подготовитсья.

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

Все оценки сохраняются. Зачем загонять в хэш не понял.

Когда с мыслями соберешься? А то понять твою идею без второго пункта затруднительно. Я так понял, что второй пункт это самый основной.

Я хочу не так. Чтобы добавить один лист к дереву хочу запускать перебор минут на 5.

Вроде бы получилось сделать что-то работающее:

Code:

#include <map>
#include <fstream.h>
#include <windows.h>
#include <string.h>

#include "GenBook.h"
#include "Hash.h"
#include "MoveGeneration.h"
#include "Moves.h"
#include "Random.h"
#include "Search.h"

int MissCnt;
std::map <unsigned __int64, BookEntry> BookMap;

bool OpeningsGenerating = false; // чтобы перебор знал, что идет генерация дебютов

void OpenBook()
{
    int i;

    cout << "\nReading book...\n";

    ifstream book;
    book.open(BOOK_NAME, ios::in | ios::binary);
    book.seekg(0, ios::end);
    int size = book.tellg();
    book.seekg(0, ios::beg);
    BookMap.clear();
    for (i = 0; i < size / sizeof BookEntry; i++)
    {
        BookEntry b;
        book.read((char *)&b, sizeof BookEntry);
        BookMap[b.key] = b;
    }
    cout << BookMap.size() << " positions in book" << endl;

    // создаем случайность
    int cnt = GetTickCount() % 100000;
    for (i = 0; i < cnt; i++) random(1);
}

void InitBook()
{
    MissCnt = 0;
}

int GetBookScore()
{
    std::map <unsigned __int64, BookEntry> :: iterator i = BookMap.find(HashKey);
    if (i != BookMap.end()) return i->second.score;
    return BOOK_POS_NOT_FOUND;
}

Move *BookProbe(Move *first)
{
    if (MissCnt > 3) return 0;
    int best_score = -100000;
    int best_cnt = 0;
    for (Move *m = first; m != PML; m++)
    {
        if (wtm) MakeWhiteMove(m);
        else MakeBlackMove(m);
        m->score = GetBookScore();
        if (m->score != BOOK_POS_NOT_FOUND)
        {
            PrintMove(m);
            cout << '\t' << m->score << endl;
            if (m->score > best_score)
            {
                best_score = m->score;
                best_cnt = 1;
            }
            else if (m->score == best_score) best_cnt++;
        }
        if (wtm) UndoWhiteMove(m);
        else UndoBlackMove(m);
    }
    if (!best_cnt)
    {
        MissCnt++;
        return 0;
    }
    MissCnt = 0;
    unsigned int random_number = random(best_cnt);
    int n = 0;
    for (m = first; m != PML; m++)
    {
        if (m->score == best_score)
        {
            if (n++ == random_number) return m;
        }
    }
    // сюда попадать не должны
    return 0;
}

/***************************\
*      Book generator       *
\***************************/

#ifndef _USRDLL // только для консольной версии движка

extern int LastScore; // возвращаемая перебором оценка

#define BOOK_MARGIN 10 // насколько хорошие позы отсекаются

void SaveBook()
{
    cout << "\nstore book...\n";
    ofstream fout(BOOK_NAME, ios::out | ios::binary);
    for (std::map <unsigned __int64, BookEntry> :: const_iterator i = BookMap.begin(); i != BookMap.end(); i++) {
        fout.write((const char *)&i->second, sizeof(BookEntry));
    }
    cout << "stored " << BookMap.size() << " positions" << endl;
}

char genbookline[1024]; // строковое представление текущего варианта (для отладки)

// Оцениваем конечную позицию, вызывая перебор

int GenBookScoreLeaf()
{
    std::map <unsigned __int64, BookEntry> :: iterator p = BookMap.find(HashKey);
    if (p != BookMap.end()) return p->second.score;
    SaveBook();
    cout << genbookline << endl;
    if (wtm) BlackRootSearch();
    else
    {
        WhiteRootSearch();
        LastScore = -LastScore;
    }
    BookEntry b;
    b.key = HashKey;
    b.depth = 0;
    b.score = LastScore;
    BookMap[HashKey] = b;
    cout << endl << "!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!" << endl;
    cout << "GenBookScoreLeaf - " << genbookline << " - " << b.score << endl;
    cout << "!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!" << endl << endl;

    return b.score;
}

int GenBookAllOpponentMoves(int depth);

// оцениваем все наши ходы и продлеваем лучшие
// варианты в которых имеем большой перевес (>= BOOK_MARGIN) обрезаются

int GenBookOurBestMove(int depth)
{
    int pos = strlen(genbookline);

    depth--;
    Move *first = PML;
    if (wtm)
    {
        GenerateWhiteCaps();
        if (first == PML) GenerateWhiteMoves();
    }
    else
    {
        GenerateBlackCaps();
        if (first == PML) GenerateBlackMoves();
    }
    if (first == PML){
        cout << endl << "!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!" << endl;
        cout << "GenBookOurBestMove: no moves - " << genbookline << " - " << -10000 << endl;
        cout << "!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!" << endl << endl;
        return -10000;
    }
    int size = BookMap.size();
    bool changed = true;
    int best_score;
    while (changed)
    {
        changed = false;

        // ищем лучшие ходы
        best_score = -10000;
        Move *m;
        for (m = first; m < PML; m++) {
            if (wtm) MakeWhiteMove(m);
            else MakeBlackMove(m);
            Move2Str(m, genbookline + pos);
            strcat(genbookline, " ");
            int tmp = GenBookScoreLeaf();
            size = BookMap.size();
            if (tmp > best_score) best_score = tmp;
            if (wtm) UndoWhiteMove(m);
            else UndoBlackMove(m);
            genbookline[pos] = 0;
        }
        if (depth == 0) break;
        if (best_score >= BOOK_MARGIN) break; // имеем уже слишком хорошую позу

        // продлеваем лучшие варианты
        for (m = first; m < PML; m++) {
            if (wtm) MakeWhiteMove(m);
            else MakeBlackMove(m);
            BookEntry b = BookMap[HashKey];
            if (b.score == best_score && b.depth < depth)
            {
                Move2Str(m, genbookline + pos);
                strcat(genbookline, " ");
                wtm = !wtm;
                b.score = GenBookAllOpponentMoves(depth);
                b.depth = depth;
                BookMap[HashKey] = b;
                wtm = !wtm;
                if (b.score > best_score)
                {
                    best_score = b.score;
                }
                if (b.score < best_score)
                {
                    // оценка лучшего упала
                    // возможно теперь лучшим будет другой ход
                    // повторяем все сначала
                    changed = true;
                }
            }
            if (wtm) UndoWhiteMove(m);
            else UndoBlackMove(m);
            genbookline[pos] = 0;
            if (changed) break;
        }
    }
    cout << endl << "!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!" << endl;
    cout << "GenBookOurBestMove - " << genbookline << " - " << best_score << endl;
    cout << "!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!" << endl << endl;
    PML = first;
    return best_score;
}

// для всех ходов соперника вызываем GenBookOurBestMove

int GenBookAllOpponentMoves(int depth)
{
    int pos = strlen(genbookline);

    int score = 10000;

    Move *first = PML;
    if (wtm)
    {
        GenerateWhiteCaps();
        if (first == PML) GenerateWhiteMoves();
    }
    else
    {
        GenerateBlackCaps();
        if (first == PML) GenerateBlackMoves();
    }
    if (first == PML)
    {
        cout << endl << "!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!" << endl;
        cout << "GenBookAllOpponentMoves: no moves - " << genbookline << " - " << score << endl;
        cout << "!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!" << endl << endl;
        return score;
    }

    for (Move *m = first; m < PML; m++)
    {
        if (wtm) MakeWhiteMove(m);
        else MakeBlackMove(m);
        Move2Str(m, genbookline + pos);
        wtm = !wtm;
        strcat(genbookline, " ");
        int tmp = GenBookOurBestMove(depth);
        if (tmp < score) score = tmp;
        wtm = !wtm;
        if (wtm) UndoWhiteMove(m);
        else UndoBlackMove(m);
        genbookline[pos] = 0;
    }
    PML = first;
    cout << endl << "!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!" << endl;
    cout << "GenBookAllOpponentMoves - " << genbookline << " - " << score << endl;
    cout << "!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!" << endl << endl;
    return score;
}

void CreateBook(char *s)
{
    OpenBook();

    OpeningsGenerating = true;

    strcpy(genbookline, "");
    int max_depth = atoi(s);
    for (int depth = 1; depth <= max_depth; depth++)
    {
        if (depth % 2) GenBookOurBestMove(depth / 2 + 1); // варианты за белых
        else GenBookAllOpponentMoves(depth / 2); // варианты за черных
    }

    OpeningsGenerating = false;

    SaveBook();
}

#endif

Определение BookEntry:

Code:

struct BookEntry
{
    unsigned __int64 key;
    int score;
    int depth;
};

Предлагайте как сделать лучше!

претензий нет разве что как преподаватель могу к стилю прикопаться

давай

ну, во-первых, пользоваться библиотеками языка С совсем не обязательно, когда программируешь на С++. поэтому вместо fstream.h можно использовать fstream, вместо string.h - string, или даже cstring (кстати, разницы между cstring и string.h нет. это одна и та же библиотека). кстати, использование библиотеки С++ string может немного упростить код. а еще, для приведения типов настоятельно рекомендуется использовать модификатор static_cast
и было бы лучше реализовать все в виде класса.
но по большому счету притензии не существенны - я сам, когда тороплюсь, не забочусь о таких вещах (то есть, мне тоже пока еще удобней использовать string.h, например). это все дело привычки

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

fstream.h - это библиотека С++. Есть только одно реальное отличие: если использовать <fstream>, нужно пользоваться std::
Считаю, что алгоритмически обе реализованы подобным образом, если не одинаковым.

string.h - это любовь с первого раза. Не могу ее бросить

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

Классами есть смысл пользоваться только, если будут использоваться несколько объектов этого класса. В моем случае вполне достаточно модульного подхода. Имена постарался давать так, чтобы не было конфликтов. В крайнем случае можно использовать пространства имен.

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

Вообще, ко мне уже более пяти лет по стилю не придирались
Обычно, наоборот, обращаются за советами по этому вопросу.

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

Результат матча реванша: +2 -1 =1.

Похоже проигрыш был из-за маленькой дебютной библиотеки. Не успел досчитать 6-ply.

Вот здесь есть статья о автоматической генерации дебютов: http://www.fierz.ch/strategy4.htm

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

Приоритет(поза) = -СуммаОтклонений(ветка_до_позы) - коэфициент * Глубина(поза)

Так это просто замечательно
а я классами пользуюсь, даже если объект будет только один.
и ПОЗДРАВЛЯЮ С ПОБЕДОЙ В МАТЧ-РЕВАНШЕ!