Othello procedure

This is a discussion on Othello procedure within the Game Programming forums, part of the General Programming Boards category; Hi I just finish making Othello using MaxMin alogritem. But I have one problem I don't know of any good ...

  1. #1
    Registered User
    Join Date
    Aug 2004
    Posts
    6

    Question Othello procedure

    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?

  2. #2
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728
    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.

  3. #3
    Super Moderator VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,590
    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.

    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);
    }
    Then you simply track how many pieces were flipped, add that to the current player piece value, subtract from the opposing player piece value.

    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.
    Last edited by VirtualAce; 10-04-2004 at 10:26 AM.

  4. #4
    S Sang-drax's Avatar
    Join Date
    May 2002
    Location
    Göteborg, Sweden
    Posts
    2,072
    Umm Bubba, I think he was talking about AI.
    Last edited by Sang-drax : Tomorrow at 02:21 AM. Reason: Time travelling

  5. #5
    Super Moderator VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,590
    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.

  6. #6
    S Sang-drax's Avatar
    Join Date
    May 2002
    Location
    Göteborg, Sweden
    Posts
    2,072
    Quote Originally Posted by Bubba
    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.

    Here's an example of Othello/Reversi using minimax. It's AI seems decent.
    http://www.skyhunter.com/marcs/rever...es/reversi.htm
    Last edited by Sang-drax; 10-04-2004 at 01:06 PM.
    Last edited by Sang-drax : Tomorrow at 02:21 AM. Reason: Time travelling

  7. #7
    Registered User
    Join Date
    Aug 2004
    Posts
    6
    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?

    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;
    this is the max. The min is the same just beta and temp2<beta.

  8. #8
    S Sang-drax's Avatar
    Join Date
    May 2002
    Location
    Göteborg, Sweden
    Posts
    2,072
    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.
    Last edited by Sang-drax : Tomorrow at 02:21 AM. Reason: Time travelling

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Hooked Procedure Early Return In/External Trigger
    By n00b3 in forum Windows Programming
    Replies: 4
    Last Post: 06-29-2008, 05:37 PM
  2. Replies: 9
    Last Post: 02-13-2008, 01:59 PM
  3. Replies: 0
    Last Post: 04-21-2006, 01:41 PM
  4. Procedure
    By Brandy22 in forum C Programming
    Replies: 6
    Last Post: 11-01-2005, 03:52 PM
  5. Collision with quads?
    By SyntaxBubble in forum Game Programming
    Replies: 6
    Last Post: 01-18-2002, 05:17 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21