Archived

This topic is now archived and is closed to further replies.

calling class member functions recursively?? (kinda advanced)

This topic is 5506 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hello, I''m having a little difficulty with some AI for a Reversi (Othello) game I''m making in C++. I have a Player class, and in that player class, there is a findBestMove(...) method that (go figure) finds the best move to perform, and the parameters it takes are an instance of a Board class and some other things. Basically, the function makes a list of possible moves and for each move, creates an instance of a Board that is the same as the one that was passed to the function, but with that move done to it. Then it goes on to evaluate all the possible moves that can be done to those boards by the opposite player, etc etc etc. All that stuff is just preamble. The important thing is that every move is evaluated the same way, and I''ve gone through and tested everything and nailed the problem down to the fact that either the new Board that is getting created for each move doesn''t look any different than the original one (though I''ve checked through, and it definitely should look different), OR when I call findBestMove again with the new board, the Board it "receives" doesn''t look any different than the original one (I am passing pointers, so there should be no issue there) So I guess my question is, is there something with C++ classes that only allows one instance of a member function on the stack at one time, (so the function would be static, in a way)? This would explain all the boards "looking alike" but it would also mean that the function would run forever, because the "depth" parameter (how many more moves deep to look) would never reach zero. Thanks in advance, and I hope I''ve explained the problem well. I''ve had my head buried in this problem for a couple of days so I might be missing the big picture in terms of my explanation. Reid Howard

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
i''ve never had a problem w/recursive calls to class member functions, but then again, i don''t use them that much.

if i may ask, why recursion? it sounds like what you''re doing is expensive. why not just copy the current board once and then reuse that object in a loop "depth" number of times? or am i missing something?

anyway, never any problems for me. you have code to show?

Share this post


Link to post
Share on other sites
Actually, it only deals with one move at a time, so there aren't thousands of Board instances floating around. It evaluates one move as deep as it can before moving onto the next one, and the same Board pointer gets used every time. I should probably put some better garbage collection in the method but I'm going to worry about that once it works. Here is the code for the method (with some stuff commented out that I used for testing, you can ignore that):

    
//finds the best move that the calling player can perform on a Board b1

Move* Player::findBestMove(Board* bNow, Player* other, int depth)
{
Move* bestMove=NULL; //move to return

MoveList* allMoves=new MoveList(); //list of possible moves on current board state


Move* currMove; //potential move that we are dealing with right now

Board* bNext; //board with the current potential move performed on it



//we've looked as far as we're supposed to; return the scores on the board as it is

if (depth==0)
bestMove=new Move(0,0,bNow->scores[WHITE],bNow->scores[BLACK]);

//the current player can perform the next move

else if (this->hasLegalMoves(bNow))
{
//try all spaces on the board for possible moves

for (int i=0; i<bNow->xSize; i++) {
for (int j=0; j<bNow->ySize; j++)
if (this->tryMove(bNow,i,j))
{
//make board with this potential move done to it

bNext=new Board(bNow);
this->doMove(bNext,i,j);

//find the other player's best move on this augmented board

//(we will return the move for which the other

//player's BEST next move is the WORST

currMove = other->findBestMove(bNext,this,depth-1);

//add this move to the list of all potential moves

allMoves->addNew(i,j,currMove->scores[WHITE],currMove->scores[BLACK]);
}
}

bestMove=allMoves->findBest(this->colour);
}

//the current player can't perform the next move; it's the other player's turn instead

else if (other->hasLegalMoves(bNow))
{
//try all spaces on the board for possible moves

for (int i=0; i<bNow->xSize; i++) {
for (int j=0; j<bNow->ySize; j++)
if (other->tryMove(bNow,i,j))
{
//make board with this potential move done to it

bNext=new Board(bNow);
other->doMove(bNext,i,j);

currMove = this->findBestMove(bNext,other,depth-1);

//add this move to the list of all potential moves

allMoves->addNew(i,j,currMove->scores[WHITE],currMove->scores[BLACK]);
}
}

bestMove=allMoves->findBest(other->colour);
}

//neither player has any move; return the scores on the board as it is

else
bestMove=new Move(0,0,bNow->scores[WHITE],bNow->scores[BLACK]);

return bestMove;
}


I tried rewriting the function from scratch, and the code above is now the new code. The variable names are a little more representative of what the variables are, and the code is better commented. Hopefully this helps you folks out there a little more.

[edited by - Reidonius on November 19, 2002 6:50:49 PM]

[edited by - Stoffel on November 19, 2002 7:36:08 PM]

[edited by - Reidonius on November 20, 2002 1:12:37 AM]

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
well i finally got back to the computer and i plugged that function into a small test app and i''m not seeing recursion problems. i also stepped through the function at the statements that you thought might be causing the problem but the new Board objects it builds are being kept and passed along during the "depth" recursive calls.

Share this post


Link to post
Share on other sites
hmm. My debugger causes problems with Win32 apps (using VC++6), but I know that the recursive calls are working, because I tried changing the return value for (depth==0) and it changed the final return value. However, I did some other debugging involving that handy MessageBox(...) function and found that after I create the new Board and perform the move on it, it has the same number of black and white stones as the initial board did. This leads me to believe that these two lines:

this->doMove(bNext,i,j);
other->doMove(bNext,i,j);

are not working. (They do the same thing, but performing the move with a different player, and in different control paths). It is a pointer that I''m passing, so the Board that bNext points to SHOULD be changed by the doMove(...) function. Apparently either that is not true, or doMove(...) doesn''t update the values in the scores[] array properly. This frustrates me, because neither of those two things seem reasonable, but I''ll have to look through doMove(...) a little bit more carefully and make sure that everything gets changed the way it should.

At least I seem to have isolated the problem. Any further suggestions (possibly involving pointers, pass by reference, things not being changed where they should, etc) would be welcome.

Reid Howard

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
well, except for adding object deletes and some var name changes like you did for clarity, i used your code as is. it follows an algorithm which makes sense, afaik othello.

when i tested, i only did so with depths of 1 & 2, but they were definitely passing the test game boards onto the called functions.

fwiw, here''s the doMove(s) i threw together for testing. i did tryMove(s) about the same way logic-wise (just no scoring and a few additional tests for game board boundary conditions). i hard coded the board size at the standard 8x8.


  
void Player::doMove( Board* b, int x, int y )
{
// u u d d d u u = up, d = down

// r r r l l l r = right, l = left

// 0 1 2 3 4 5 6 7 8 directions of movements

static int xd[] = { 0, +1, +1, +1, 0, -1, -1, -1};
static int yd[] = {-1, -1, 0, +1, +1, +1, 0, -1};

int p = tryMove(b, x, y);

b->grid[x][y] = colour;
b->scores[colour] += 1;

if( p > 0 ) {
for( int d = 0; d < 8; d++ ) {
if( tryMove(b, x, y, xd[d], yd[d]) ) {
doMove(b, x, y, xd[d], yd[d]);
}
}
}
}

void Player::doMove( Board* b, int x, int y, int xd, int yd )
{
int opponent = (colour == BLACK) ? WHITE : BLACK;

while( true ) {
x += xd;
y += yd;
if( b->grid[x][y] == opponent ) {
b->grid[x][y] = colour;
b->scores[colour] += 1;
b->scores[opponent] -= 1;
continue;
}
if( b->grid[x][y] == colour ) break;
if( b->grid[x][y] == OPEN ) break;
if( x == 0 ) break;
if( y == 0 ) break;
if( x == 7 ) break;
if( y == 7 ) break;
}
}

Share this post


Link to post
Share on other sites