Hi I just finish making Othello using MaxMin alogritem. But I have one problem I don't know of any good procedure. I use this one now. (Black-White)/(Black+White). So I always win. Can any of you help me?
Printable View
Hi I just finish making Othello using MaxMin alogritem. But I have one problem I don't know of any good procedure. I use this one now. (Black-White)/(Black+White). So I always win. Can any of you help me?
Do a search online, theres a TON of sites out there that will tell you how to evaluate the board.
A simple way is to give each square on the board a point value, corner squares are worth a lot, side squares worth medium, some even have negative point value since its undesirable to hold them, etc. Then your min/max algorithm just adds up one players score and subtracts the other players score and you have your min/max number.
The fastest way I've found to implement othello is recursively. Check all directions for the same color piece - much like you would with a paint by pixel program or a flood-fill algo. Since the board is not that large you will never, or should never, get a stack overflow. To track the pieces is as simple as tracking 2 variables - one for the white and one for the black. When the black is zero or the white is zero - you know who won. Each person starts out with the same number of pieces and you simply add to that as soon as flipping is done.
There is no need to search the entire board when all pieces being flipped are relative to the piece being played - perfect for recursion, but I've also done this with a for loop as well.
Your choice.
Then you simply track how many pieces were flipped, add that to the current player piece value, subtract from the opposing player piece value.Code:void Flip(int row, int col, int piece_color,int &pieces_flipped)
{
static int pieces_flipped=0;
if (board(row,col)!=piece_color) return;
//Current piece is opposite color
pieces_flipped++;
Board(row,col)=piece_color;
//Find neighbors and exit if out of bounds
if (row<0 || row>max_row) return;
if (col<0 || col>max_col) return;
//NW
Flip(row-1,col-1,piece_color,pieces_flipped);
//N
Flip(row-1,col,piece_color,pieces_flipped);
//NE
Flip(row-1,col+1,piece_color,pieces_flipped);
//W
Flip(row,col-1,piece_color,pieces_flipped);
//E
Flip(row,col+1,piece_color,pieces_flipped);
//SW
Flip(row+1,col-1,piece_color,pieces_flipped);
//S
Flip(row+1,col,piece_color,pieces_flipped);
//SE
Flip(row+1,col+1,piece_color,pieces_flipped);
}
All you really have to do now is draw the board, implement the turns and test for a loser.
Notice this code does not even have to check each row for the same color piece. If it encounters a piece of the same color it returns.
There is a serious problem here though but I leave it to you to figure out. This will flip pieces everywhere and will not properly follow othello rules for only flipping on one axis at a time from the current piece. This will check all neighbors of all pieces. You need to limit the checks to the current axis. Easy to do with some alteration to the code.
Umm Bubba, I think he was talking about AI. :confused:
Probably right. AI would simply be a measure of pieces gained per axis. Pick the best axis. If no axis then place a piece on the board based on another evaluation - one I cannot come up with at this time.
He hade apparently tried MinMax, which I thought would work great -- just use the number of own pieces as the evaluation function, along with an extra bonus for pieces in the corners.Quote:
Originally Posted by Bubba
Here's an example of Othello/Reversi using minimax. It's AI seems decent.
http://www.skyhunter.com/marcs/rever...es/reversi.htm
Thanks.
This is the first time I do this, and the I'm not used to program in C++. But can any of you se if my maxmin is ok?
this is the max. The min is the same just beta and temp2<beta. :rolleyes:Code:while(temp<numOfC && alfa < beta)
{
temp2 = barn[temp]->AlfaBeta(alfa,beta,!maxMin,count);
if(count > 1)
{
delete barn[temp];
}
if(temp2>alfa)
{
alfa = temp2;
}
temp++;
}
return alfa;
The origianl MiniMax algorithm has nothing to do with Alpha-beta. The alpha-beta search is an optimization for Minimax.
Try implementing a working MiniMax first.