vendredi 3 août 2018

Min max alpha beta

I did an IA for Connect 4 with min max algorithme.

It's works well until a deep of 7.

To get this IA stronger, I want to implement alpha beta pruning heuristique.

This is the source code :

int const                   MinMax::START_MAX = -10000;
int const                   MinMax::START_MIN = 10000;

int                         MinMax::min(const int deep, int const last_x,
        int const last_y, int &alpha, int &beta)
{
    bool                    win;
    int                     tmp;
    int                     y, x;
    int                     min = START_MIN;

    if ((win = this->win(ColorCell::get_c(ColorCell::PLAYER2), last_x, last_y)) == true
            || deep <= 0)//end of max
        return (this->eval(1, deep, win));
    for (x = 0; x < m_x_max; x++)
    {
        if ((y = this->start_column(x)) < 0)
            continue ;
        m_grid[y][x]->set_val(ColorCell::get_c(ColorCell::PLAYER1));
        if ((tmp = this->max(deep - 1, x, y, alpha, beta)) < min)
            min = tmp;
        m_grid[y][x]->set_val(ColorCell::get_c(ColorCell::EMPTY));
//      if (min <= alpha)
//          break ;
//      if (min < beta)
//          beta = tmp;
    }
    return (min);
}

int                         MinMax::max(const int deep, int const last_x,
        int const last_y, int &alpha, int &beta)
{
    bool                    win;
    int                     tmp;
    int                     y, x;
    int                     max = START_MAX;

    if ((win = this->win(ColorCell::get_c(ColorCell::PLAYER1), last_x, last_y)) == true
            || deep <= 0) //end of min
        return (this->eval(-1, deep, win));
    for (x = 0; x < m_x_max; x++)
    {
        if ((y = this->start_column(x)) < 0)
            continue ;
        m_grid[y][x]->set_val(ColorCell::get_c(ColorCell::PLAYER2));
        if ((tmp = this->min(deep - 1, x, y, alpha, beta)) > max)
            max = tmp;
        m_grid[y][x]->set_val(ColorCell::get_c(ColorCell::EMPTY));
//      if (max >= beta)
//          break ;
//      if (max > alpha)
//          alpha = max;
    }
    return (max);
}

If I uncomment lines at the end of loops, I live functions to early.

I don't understand what I did wrong, It's look like easy to implement alpha beta when you read tuto ...

This the start function of the minmax

void                        MinMax::run(void)
{
    int                     x, y, tmp;
    int                     alpha = 0;
    int                     beta = 0;

    m_max = START_MAX;
    m_y = -1;
    m_x = -1;
    for (x = 0; x < m_x_max; x++)
    {
        if ((y = this->start_column(x)) < 0)
            continue ;
        m_grid[y][x]->set_val(ColorCell::get_c(ColorCell::PLAYER2));
        if ((tmp = this->min(m_deep - 1, x, y, alpha, beta)) > m_max)
        {
            m_x = x;
            m_y = y;
            m_max = tmp;
        }
        m_grid[y][x]->set_val(ColorCell::get_c(ColorCell::EMPTY));
    }
}

Thank you for your help

Aucun commentaire:

Enregistrer un commentaire