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