SoltreePolina

#include <QtWidgets>
#include <QtDebug>


//Поменять местами два значения
void swap(SolutionTree::CellType &a, SolutionTree::CellType &b)
{
    SolutionTree::CellType tmp;
    tmp = a;
    a = b;
    b = tmp;
}

//Конструктор дерева решения
SolutionTree::SolutionTree(int size, Color color, bool moveOfAI, int numberOfCheckers)
{
    this->color = color;
    //Создание начального состояния
    QVector< QVector < SolutionTree::CellType > > startField(size, QVector< SolutionTree::CellType > (size, None));

    for (int i = 0; i < numberOfCheckers; ++i)
    {
        startField[size - i / 3 - 1][i % 3] = color == White ? Own : Enemy;
        startField[i / 3][size - i % 3 - 1] = color == White ? Enemy : Own;
    }
    //Инициализирование корня дерева
    root = new State(startField, moveOfAI);
    //Srand()
    srand(NULL);

    //Построить первые ветви с состояниями
    makeSolutionTree(root, this->TREE_SIZE);
}

//Проверка-можем ли мы идти в  [i][j]
bool SolutionTree::canGoTo(State* state, int i, int j)
{
   if (i >= 0 && i < state->field.size() && j >= 0 && j < state->field.size())
   {
       return true;
   }
   else
   {
       return false;
   }
}
// Возвращает все возможные ходы
QSet<SolutionTree::Move> SolutionTree::getPossibleMoves(State *state, int i, int j)
{
    QSet<Move> result;

    Color checkerColor = this->color;

    if (state->field[i][j] ==  Enemy)
    {
        checkerColor = this->color == White ? Black : White;
    }

    if (checkerColor == White)
    {
        if (canGoTo(state, i - 1, j) && state->field[i - 1][j] == None) result.insert(Move(i, j, i - 1, j));
        if (canGoTo(state, i, j + 1) && state->field[i][j + 1] == None) result.insert(Move(i, j, i, j + 1));
    }
    else
    {
        if (canGoTo(state, i, j - 1) && state->field[i][j - 1] == None) result.insert(Move(i, j, i, j - 1));
        if (canGoTo(state, i + 1, j) && state->field[i + 1][j] == None) result.insert(Move(i, j, i + 1, j));
    }

// Делаем стоимость состояния
int SolutionTree::moveCost(State* state)
{

    CellType type = !state->moveOfAI ? Own : Enemy;
    Color color = this->color;
    if (type == Enemy) color = color == Black ? White : Black;

    // Проверка потери вариантов (cost == 0):
         // Если состояние приходит в тупик
    int deltaRow = 0;
    int deltaCol = 0;
    for (int k = 0; k < 3; ++k)
    {
        int checkerAtRowCount = 0;
        int checkerAtColCount = 0;
        int allCount = 0;
        if ((color == White && state->field[k][state->field.size() - k - 1] == type) || (color == Black && state->field[state->field.size() - k - 1][k] == type)) allCount--;

        for (int i = k; i < state->field.size(); ++i)
        {
            if ((color == White && state->field[k][state->field.size() - 1 - i] == type) || (color == Black && state->field[state->field.size() - 1 - k][i] == type)) checkerAtRowCount++;
            if ((color == White && state->field[i][state->field.size() - 1 - k] == type) || (color == Black && state->field[state->field.size() - 1 - i][k] == type)) checkerAtColCount++;
        }

        allCount += checkerAtColCount + checkerAtRowCount;
        if (checkerAtColCount <= 3 - k && checkerAtRowCount <= 3 - k && allCount <= 5 - 2 * k)
        {
                deltaRow += 3 - k - checkerAtRowCount;
                deltaCol += 3 - k - checkerAtColCount;
        }
        else
        {
            return 0;
        }
    }

    int cost = 0;

    // Создание ненулевой стоимости хода
        cost = rand() % (MAX_COST / 5) + 1;
    // Сделать дерево, чтобы выйти из позиции в первую очередь
    if (state->turnNumber <= 55)
    {
        if (color == White)
        {
            //Если шашка на позиции
            if (state->field.size() - 3 <= state->move.fromI && state->move.fromI < state->field.size() && 0 <= state->move.fromJ && state->move.fromJ < 3)
            {
                cost = MAX_COST - 1;
                if (state->move.toI < state->field.size() - 3 || state->move.toJ >= 3) cost++;
            }
            //Если другая блокирует её
            if ((state->move.fromI == state->field.size() - 4 && state->field[state->move.fromI + 1][state->move.fromJ] == type) || (state->move.fromJ == 3 && state->field[state->move.fromI][state->move.fromJ - 1] == type))
            {
                cost = MAX_COST;
            }
        }
        else
        {
            //Если шашка на позиции
            if (state->field.size() - 3 <= state->move.fromJ && state->move.fromJ < state->field.size() && 0 <= state->move.fromI && state->move.fromI < 3)
            {
                cost = MAX_COST - 1;
                if (state->move.toI >= 3 || state->move.toJ < state->field.size() - 3) cost++;
            }
            //если другая блокирует её
            if ((state->move.fromI == 3 && state->field[state->move.fromI - 1][state->move.fromJ] == type) || (state->move.fromJ == state->field.size() - 4 && state->field[state->move.fromI][state->move.fromJ + 1] == type))
            {
                cost = MAX_COST;
            }
        }
    }

    return cost;
}

//Рекурсивная функция строит дерево для корневого состояния
void SolutionTree::makeSolutionTree(State *state, int count)
{
    if (count == 0) return;

    QSet<Move> moves;

    //получение хода
    for (int i = 0; i < state->field.size(); ++i)
    {
        for (int j = 0; j < state->field.size(); ++j)
        {
            if ((state->moveOfAI && state->field[i][j] == Own) || (!state->moveOfAI && state->field[i][j] == Enemy))
            {
                moves += getPossibleMoves(state, i, j);
            }
        }
    }

    //Создание потомков
    for (QSet<Move>::iterator it = moves.begin(); it != moves.end(); ++it)
    {
        swap(state->field[it->fromI][it->fromJ], state->field[it->toI][it->toJ]);

        state->child.push_back(new State(state->field, !state->moveOfAI, *it, state->turnNumber + 1));
        state->child.last()->cost = moveCost(state->child.last());      //Создаёт стоимость хода
        makeSolutionTree(state->child.last(), count - 1);
        //Заявление минимакса
        if (state->cost < MAX_COST - 2 && state->cost != 0)
        {
            for (int i = 0; i < state->child.size(); ++i)
            {
                if (i == 0) state->cost = 1;
                if (state->child[i]->cost == 0) continue;
                if (state->moveOfAI) state->cost = qMax(state->cost, state->child[i]->cost);
                else state->cost = qMin(state->cost, state->child[i]->cost);
            }
        }

        swap(state->field[it->fromI][it->fromJ], state->field[it->toI][it->toJ]);
    }

}

//Удаление всех потомков
void SolutionTree::deleteBranch(State *state)
{
    if (state == NULL) return;

    for (int i = 0; i < state->child.size(); ++i)
    {
        deleteBranch(state->child[i]);
    }
    delete state;
}

//Возвращает ход
SolutionTree::Move SolutionTree::getMove(State *state)
{
    if (root == NULL)
    {
        root = state;
        root->moveOfAI = true;
        makeSolutionTree(root, TREE_SIZE);
    }

    if (root->child.size() == 0)
    {
        makeSolutionTree(root, TREE_SIZE);
    }

    //Перемещение состояния на экране
    State* newState = root;

    //Найти состояние из поля в дереве и удалить другие
    if (!root->moveOfAI)
    {
        for (int i = 0; i < root->child.size(); ++i)
        {
            if (state->field == root->child[i]->field)
            {
                newState = root->child[i];
            }
            else
            {
                deleteBranch(root->child[i]);
            }
        }
        delete root;
    }

    root = newState;

    if (root->child.size() == 0)
    {
        makeSolutionTree(root, TREE_SIZE);
    }
    //Сделать ход с большей стоимостью
    int cost = - 1;
    int index = 0;
    for (int i = 0; i < root->child.size(); ++i)
    {
        if (root->child[i]->cost > cost || (root->child[i]->cost == cost && rand() % 2))
        {
            cost = root->child[i]->cost;
            index = i;
        }
    }

    Move move = root->child[index]->move;
    newState = root->child[index];

    //Удалить остальные
    for (int i = 0; i < root->child.size(); ++i)
    {
        if (root->child[i] != newState) deleteBranch(root->child[i]);
    }
    delete root;

    root = newState;

    return move;

}