1 ضمیمه
پیاده سازی بازی Reversi با الگوریتم Minimax
سلام به همه دوستان
من پروژه ای رو که پیاده سازی بازی ریورسی با الگوریتم جستجوی حریصانه آلفا-بتا بود از لینک زیر دانلود کردم
http://aminsharifi67.blogspot.com/20...-sharp_13.html
حالا می خواسم همین پروژه رو با الگوریتم Minimax بدون بهینه سازی با جستجوی حریصانه آلفا-بتا پیاده سازی کنم. متد مربوط به پیاده سازی این الگوریتم به شکل کد زیر هست
private ComputerMove GetBestMove(Board board, int color, int depth, int alpha, int beta)
{
// Initialize the best move.
ComputerMove bestMove = new ComputerMove(-1, -1);
bestMove.rank = -color * Reversi.maxRank;
// Find out how many valid moves we have so we can initialize the
// mobility score.
int validMoves = movement.GetValidMoveCount(color);
// Start at a random position on the board. This way, if two or
// more moves are equally good, we'll take one of them at random.
Random random = new Random();
int rowStart = random.Next(8);
int colStart = random.Next(8);
// Check all valid moves.
int i, j;
for (i = 0; i < 8; i++)
for (j = 0; j < 8; j++)
{
// Get the row and column.
int row = (rowStart + i) % 8;
int col = (colStart + j) % 8;
if (movement.IsValidMove(color, row, col))
{
// Make the move.
ComputerMove testMove = new ComputerMove(row, col);
Board testBoard = new Board(board);
Movement testMovement=new Movement(testBoard);
testMovement.MakeMove(color, testMove.row, testMove.col);
int score = testBoard.WhiteCount - testBoard.BlackCount;
// Check the board.
int nextColor = -color;
int forfeit = 0;
bool isEndGame = false;
int opponentValidMoves = testMovement.GetValidMoveCount(nextColor);
if (opponentValidMoves == 0)
{
// The opponent cannot move, count the forfeit.
forfeit = color;
// Switch back to the original color.
nextColor = -nextColor;
// If that player cannot make a move either, the
// game is over.
if (testMovement.GetValidMoveCount(nextColor)==0)
isEndGame = true;
}
// If we reached the end of the look ahead (end game or
// max depth), evaluate the board and set the move
// rank.
if (isEndGame || depth == this.lookAheadDepth)
{
// For an end game, max the ranking and add on the
// final score.
if (isEndGame)
{
// Negative value for black win.
if (score < 0)
testMove.rank = -Reversi.maxRank + score;
// Positive value for white win.
else if (score > 0)
testMove.rank = Reversi.maxRank + score;
// Zero for a draw.
else
testMove.rank = 0;
}
// It's not an end game so calculate the move rank.
else
testMove.rank =
this.forfeitWeight * forfeit +
this.frontierWeight * (testBoard.BlackFrontierCount - testBoard.WhiteFrontierCount) +
this.mobilityWeight * color * (validMoves - opponentValidMoves) +
this.stabilityWeight * (testBoard.WhiteSafeCount - testBoard.BlackSafeCount) +
score;
}
// Otherwise, perform a look ahead.
else
{
ComputerMove nextMove = this.GetBestMove(testBoard, nextColor, depth + 1, alpha, beta);
// Pull up the rank.
testMove.rank = nextMove.rank;
// Forfeits are cumulative, so if the move did not
// result in an end game, add any current forfeit
// value to the rank.
if (forfeit != 0 && Math.Abs(testMove.rank) < Reversi.maxRank)
testMove.rank += forfeitWeight * forfeit;
// Adjust the alpha and beta values, if necessary.
//computer is white
if (color == Board.White && testMove.rank > beta)
beta = testMove.rank;
if (color == Board.Black && testMove.rank < alpha)
alpha = testMove.rank;
}
// Perform a cutoff if the rank is outside tha alpha-beta range.
if (color == Board.White && testMove.rank > alpha)
{
testMove.rank = alpha;
return testMove;
}
if (color == Board.Black && testMove.rank < beta)
{
testMove.rank = beta;
return testMove;
}
// If this is the first move tested, assume it is the
// best for now.
if (bestMove.row < 0)
bestMove = testMove;
// Otherwise, compare the test move to the current
// best move and take the one that is better for this
// color.
else if (color * testMove.rank > color * bestMove.rank)
bestMove = testMove;
}
}
// Return the best move found.
return bestMove;
}
حالا چه تغییراتی رو باید در این کد اعمال کنم تا تبدیل به Minimax استاندارد بشه :متفکر:
اگر کمکم کنید ممنون می شم :خجالت:
