• Create Account

Awesome job so far everyone! Please give us your feedback on how our article efforts are going. We still need more finished articles for our May contest theme: Remake the Classics

### #ActualAticAtac

Posted 26 September 2012 - 09:03 AM

I rewrote my code a little and use now Negmax. I guess i can to reduce the problem to
- is MinMax is suited for this kind of board game?
- is my Negmax-code correct
- is my Evaluate-Code correct

My new code (without source-tag, since its not working correct):

int cBoard::NegMax(tBoard& board, int depth, bool left, int alpha, int beta)
{
cEvaluation eval;
int best = -INFINITY;
int check_win = CheckWin(board, eval, left);
if (check_win != 0)
return check_win;
if (depth <= 0)
return Evaluate(board, left, eval);
std::vector<tMove> movelist;
GenerateMoves(&board, left, movelist);
if (movelist.size() == 0)
throw "No more moves!"; // how to handle?
int max = -INFINITY;
for (unsigned int i = 0; i<movelist.size(); ++i)
{
tBoard board2;
memcpy(&board2, &board, sizeof(tBoard));
ExecuteMove(&board2, left, movelist[i], eval);
int val = -NegMax(board2, depth-1, !left, -beta, -alpha);
if (val > max)
max = val;
if (val > alpha)
alpha = val;
if (alpha >= beta)
return alpha;
}

return max;
}

tMove cBoard::AlphaBetaStart(bool left, int maxdepth)
{
cEvaluation eval;
tMove bestmove;
bestmove.rating = -INFINITY;
int currentscore;
_bestmoves.clear();
_cpuleft = left;

std::vector<tMove> movelist;
GenerateMoves(&m_fields, left, movelist);
for (unsigned int i=0; i<movelist.size(); ++i)
{
tBoard board2;
memcpy(&board2, &m_fields, sizeof(tBoard));
ExecuteMove(&board2, left, movelist[i], eval);
currentscore = -NegMax(board2, maxdepth, !left, -INFINITY, +INFINITY);
if (currentscore > bestmove.rating)
{
bestmove.rating = currentscore;
bestmove.move = movelist[i].move;
}
tMove move;
move.move = movelist[i].move;
move.rating = currentscore;
_bestmoves.push_back(move);
}
return bestmove;
}

int cBoard::Evaluate(const tBoard& b, bool left, cEvaluation& eval)
{
int score = eval.pirates_base * 5 + eval.pirates_outside * 4;
if (left != _cpuleft)
score = -score;
return score;
}

Evaluate just returns the number of pieces on the board for the given player (pieces in the base are slightly prefered).
The result right now is not satisfactory. One reason could be the simple Evaluation function or maybe some bugs in my NegMax (with alpha beta) code?

### #4AticAtac

Posted 26 September 2012 - 09:01 AM

I rewrote my code a little and use now Negmax. I guess i can to reduce the problem to
- is MinMax is suited for this kind of board game?
- is my Negmax-code correct
- is my Evaluate-Code correct

My new code:

[source lang="cpp"]int cBoard::NegMax(tBoard& board, int depth, bool left, int alpha, int beta){    cEvaluation eval;    int best = -INFINITY;    int check_win = CheckWin(board, eval, left);    if (check_win != 0)        return check_win;    if (depth <= 0)        return Evaluate(board, left, eval);    std::vector<tMove> movelist;    GenerateMoves(&board, left, movelist);    if (movelist.size() == 0)        throw "No more moves!"; // how to handle?    int max = -INFINITY;    for (unsigned int i = 0; i<movelist.size(); ++i)    {        tBoard board2;        memcpy(&board2, &board, sizeof(tBoard));        ExecuteMove(&board2, left, movelist[i], eval);          int val = -NegMax(board2, depth-1, !left, -beta, -alpha);        if (val > max)            max = val;        if (val > alpha)            alpha = val;        if (alpha >= beta)            return alpha;    }    return max;}tMove cBoard::AlphaBetaStart(bool left, int maxdepth){    cEvaluation eval;    tMove bestmove;    bestmove.rating = -INFINITY;    int currentscore;    _bestmoves.clear();    _cpuleft = left;    std::vector<tMove> movelist;    GenerateMoves(&m_fields, left, movelist);    for (unsigned int i=0; i<movelist.size(); ++i)    {            tBoard board2;        memcpy(&board2, &m_fields, sizeof(tBoard));        ExecuteMove(&board2, left, movelist[i], eval);        currentscore = -NegMax(board2, maxdepth, !left, -INFINITY, +INFINITY);        if (currentscore > bestmove.rating)        {            bestmove.rating = currentscore;            bestmove.move = movelist[i].move;                    }        tMove move;        move.move = movelist[i].move;                move.rating = currentscore;        _bestmoves.push_back(move);            }    return bestmove;}[/source]

Evaluate just returns the number of pieces on the board for the given player. The result right now is not satisfactory. One reason could be the simple Evaluation function or maybe some bugs in my NegMax (with alpha beta) code?

### #3AticAtac

Posted 26 September 2012 - 09:00 AM

I rewrote my code a little and use now Negmax. I guess i can to reduce the problem to
- is MinMax is suited for this kind of board game?
- is my Negmax-code correct
- is my Evaluate-Code correct

My new code:

[source lang="cpp"]//--------------------------------------------------------------------------------int cBoard::NegMax(tBoard& board, int depth, bool left, int alpha, int beta){ cEvaluation eval; int best = -INFINITY; int check_win = CheckWin(board, eval, left); if (check_win != 0) return check_win; if (depth <= 0) return Evaluate(board, left, eval); std::vector<tMove> movelist; GenerateMoves(&board, left, movelist); if (movelist.size() == 0) throw "No more moves!"; // how to handle? int max = -INFINITY; for (unsigned int i = 0; i<movelist.size(); ++i) { tBoard board2; memcpy(&board2, &board, sizeof(tBoard)); ExecuteMove(&board2, left, movelist[i], eval);   int val = -NegMax(board2, depth-1, !left, -beta, -alpha); if (val > max) max = val; if (val > alpha) alpha = val; if (alpha >= beta) return alpha; } return max;}//--------------------------------------------------------------------------------tMove cBoard::AlphaBetaStart(bool left, int maxdepth){ cEvaluation eval; tMove bestmove; bestmove.rating = -INFINITY; int currentscore; _bestmoves.clear(); _cpuleft = left; std::vector<tMove> movelist; GenerateMoves(&m_fields, left, movelist); for (unsigned int i=0; i<movelist.size(); ++i) { tBoard board2; memcpy(&board2, &m_fields, sizeof(tBoard)); ExecuteMove(&board2, left, movelist[i], eval); currentscore = -NegMax(board2, maxdepth, !left, -INFINITY, +INFINITY); if (currentscore > bestmove.rating) { bestmove.rating = currentscore; bestmove.move = movelist[i].move; } tMove move; move.move = movelist[i].move; move.rating = currentscore; _bestmoves.push_back(move); } return bestmove;}[/source]

Evaluate just returns the number of pieces on the board for the given player. The result right now is not satisfactory. One reason could be the simple Evaluation function or maybe some bugs in my NegMax (with alpha beta) code?

### #2AticAtac

Posted 26 September 2012 - 08:59 AM

I rewrote my code a little and use now Negmax. I guess i can to reduce the problem to
- is MinMax is suited for this kind of board game?
- is my Negmax-code correct
- is my Evaluate-Code correct

My new code:

[source lang="java"]//--------------------------------------------------------------------------------int cBoard::NegMax(tBoard& board, int depth, bool left, int alpha, int beta){ cEvaluation eval; int best = -INFINITY; int check_win = CheckWin(board, eval, left); if (check_win != 0) return check_win; if (depth <= 0) return Evaluate(board, left, eval); std::vector<tMove> movelist; GenerateMoves(&board, left, movelist); if (movelist.size() == 0) throw "No more moves!"; // how to handle? int max = -INFINITY; for (unsigned int i = 0; i<movelist.size(); ++i) { tBoard board2; memcpy(&board2, &board, sizeof(tBoard)); ExecuteMove(&board2, left, movelist[i], eval);   int val = -NegMax(board2, depth-1, !left, -beta, -alpha); if (val > max) max = val; if (val > alpha) alpha = val; if (alpha >= beta) return alpha; } return max;}//--------------------------------------------------------------------------------tMove cBoard::AlphaBetaStart(bool left, int maxdepth){ cEvaluation eval; tMove bestmove; bestmove.rating = -INFINITY; int currentscore; _bestmoves.clear(); _cpuleft = left; std::vector<tMove> movelist; GenerateMoves(&m_fields, left, movelist); for (unsigned int i=0; i<movelist.size(); ++i) {     tBoard board2; memcpy(&board2, &m_fields, sizeof(tBoard)); ExecuteMove(&board2, left, movelist[i], eval); currentscore = -NegMax(board2, maxdepth, !left, -INFINITY, +INFINITY); if (currentscore > bestmove.rating) { bestmove.rating = currentscore; bestmove.move = movelist[i].move; } tMove move; move.move = movelist[i].move; move.rating = currentscore; _bestmoves.push_back(move); } return bestmove;}[/source]

Evaluate just returns the number of pieces on the board for the given player. The result right now is not satisfactory. One reason could be the simple Evaluation function or maybe some bugs in my NegMax (with alpha beta) code?

### #1AticAtac

Posted 26 September 2012 - 08:57 AM

I rewrote my code a little and use now Negmax. I guess i can to reduce the problem to
- is MinMax is suited for this kind of board game?
- is my Negmax-code correct
- is my Evaluate-Code correct

My new code:

[source lang="java"]//--------------------------------------------------------------------------------int cBoard::NegMax(tBoard& board, int depth, bool left, int alpha, int beta){ cEvaluation eval; int best = -INFINITY; int check_win = CheckWin(board, eval, left); if (check_win != 0) return check_win; if (depth <= 0) return Evaluate(board, left, eval); std::vector<tMove> movelist; GenerateMoves(&board, left, movelist); if (movelist.size() == 0) throw "No more moves!"; // how to handle? int max = -INFINITY; for (unsigned int i = 0; i<movelist.size(); ++i) { //Show(&board); tBoard board2; memcpy(&board2, &board, sizeof(tBoard)); ExecuteMove(&board2, left, movelist[i], eval); //Show(&board2); int val = -NegMax(board2, depth-1, !left, -beta, -alpha); if (val > max) max = val; if (val > alpha) alpha = val; if (alpha >= beta) return alpha; } return max;}//--------------------------------------------------------------------------------tMove cBoard::AlphaBetaStart(bool left, int maxdepth){ cEvaluation eval; tMove bestmove; bestmove.rating = -INFINITY; int currentscore; _bestmoves.clear(); _cpuleft = left; std::vector<tMove> movelist; GenerateMoves(&m_fields, left, movelist); for (unsigned int i=0; i<movelist.size(); ++i) { //Show(&m_fields); tBoard board2; memcpy(&board2, &m_fields, sizeof(tBoard)); ExecuteMove(&board2, left, movelist[i], eval); //Show(&board2); //currentscore = AlphaBeta(board2, maxdepth, -INFINITY, +INFINITY, !left); currentscore = -NegMax(board2, maxdepth, !left, -INFINITY, +INFINITY); if (currentscore > bestmove.rating) { bestmove.rating = currentscore; bestmove.move = movelist[i].move; } tMove move; move.move = movelist[i].move; move.rating = currentscore; _bestmoves.push_back(move); } return bestmove;}[/source]
Evaluate just returns the number of pieces on the board for the given player. The result right now is not satisfactory. One reason could be the simple Evaluation function or maybe some bugs in my NegMax (with alpha beta) code?

PARTNERS