Skip to main content
gamedev.net
🔒 Locked

Problem with recursive function

Started by Alexistran Mar 12, 2007 at 1:10 AM 4 replies 1.1k views
Original Post
Alexistran
Alexistran
I have a recursive function (source below) which is crashing when it returns sometimes. I'm completely stumped as to why it's crashing. The ouput it produces is listed below as well EDIT: Code has been revised, and output to match it. EDIT2: I've fixed the problem. Code: 

int BoardImp::futureSight(BoardImp tempb, int colour, int pegN, int forwardCount)
{
	int moveScoresT[16];		 // stores the move scores for this level
	for (int c = 0; c < 16; c++) // going to be using += so need to
		moveScoresT[c] = 0;		 // make sure it's set to 0
	cout << "FC = " << forwardCount << endl;
	// ------------------- control colour -----------------------------//
	// 3 moves will be simulated.
	// colour passed    (forwardCount = 0)
	// opposite colour  (forwardCount = 1)
	// colour passed	(forwardCount = 2)
	if (forwardCount != 0)
		colour = oppColour(colour);
	// ------------------- end control colour -------------------------//
	// ------------------- control depth ------------------------------//
	forwardCount++;
	// ------------------- end control depth ---------------------------//
	// ------------------- simulate move -------------------------------//

	// make the move
	string location = peg[pegN].GetNext();
	tempb.updateBoard(location,colour);
	int a = 0;
	for (int i = 0; i < 16; i++)
	{		
		cout << "i="<<i<<endl;
		// no need to check forwardCount == 1 as thats done before this has even been called once
		int	s = tempb.offDefMove(i,colour); // check if a win can be made
		if ((s >= 1000) && (forwardCount == 2)) // opponent can win
			return -1000000; // this path found a winning move for opponent	(DO NOT TAKE THIS PATH)
		else if ((s >= 1000) && (forwardCount == -1)) // we can win
			moveScoresT += 1000; // this path found a winning move for us (offset against opponent blocking)
		else if ((s > 0 ) && (s < 1000) && (forwardCount == 2)) // opponent can block
			moveScoresT += -1000; // this path found a blocking move for opponent (offset against us finding a win)
		else if ((s > 0 ) && (s < 1000) && (forwardCount == -1)) // we can block a win
			moveScoresT += 100;
		// ------------------- recursive step ------------------------------//
		// call function again
		cout << "Forward Count before = " << forwardCount << endl;
		cout << "moveScoresT[" << i << "] = " << moveScoresT << endl;
		if (forwardCount == 3)
			a = 10;
		else
		{
			a = futureSight(tempb, colour,i,forwardCount); // call recursively			
			//forwardCount--;
			cout << "Forward Count after = " << forwardCount << endl;
		}
		cout << "A="<<a<<endl;
		moveScoresT += a;
		cout << "moveScoresT[" << i << "] = " << moveScoresT << endl;
		// ------------------- end recursive step -------------------------//
	}	
	// ------------------- end simulate move ---------------------------//
	// ------------------- calculate return score ---------------------//
	// After recursion (where its returning)
	int highest = 0;
	for (int k = 0; k < 16; k++)
	{
		// search through moveScoresT for the highest value
		// then return that
		if (moveScoresT[k] > moveScoresT[highest])
			highest = k;
	}
	cout << "highest = " << highest << endl;
	return moveScoresT[highest];
	// ------------------- end calculate return score -----------------//
}
Output: 

FC = 0
i=0
Forward Count before = 1
moveScoresT[0] = 0
FC = 1
i=0
Forward Count before = 2
moveScoresT[0] = 0
FC = 2
i=0
Forward Count before = 3
moveScoresT[0] = 0
A=10
moveScoresT[0] = 10
i=1
Forward Count before = 3
moveScoresT[1] = 0
A=10
moveScoresT[1] = 10
i=2
Forward Count before = 3
moveScoresT[2] = 0
A=10
moveScoresT[2] = 10
i=3
Forward Count before = 3
moveScoresT[3] = 0
A=10
moveScoresT[3] = 10
i=4
Forward Count before = 3
moveScoresT[4] = 0
A=10
moveScoresT[4] = 10
i=5
Forward Count before = 3
moveScoresT[5] = 0
A=10
moveScoresT[5] = 10
i=6
Forward Count before = 3
moveScoresT[6] = 0
A=10
moveScoresT[6] = 10
i=7
Forward Count before = 3
moveScoresT[7] = 0
A=10
moveScoresT[7] = 10
i=8
Forward Count before = 3
moveScoresT[8] = 0
A=10
moveScoresT[8] = 10
i=9
Forward Count before = 3
moveScoresT[9] = 0
A=10
moveScoresT[9] = 10
i=10
Forward Count before = 3
moveScoresT[10] = 0
A=10
moveScoresT[10] = 10
i=11
Forward Count before = 3
moveScoresT[11] = 0
A=10
moveScoresT[11] = 10
i=12
Forward Count before = 3
moveScoresT[12] = 0
A=10
moveScoresT[12] = 10
i=13
Forward Count before = 3
moveScoresT[13] = 0
A=10
moveScoresT[13] = 10
i=14
Forward Count before = 3
moveScoresT[14] = 0
A=10
moveScoresT[14] = 10
i=15
Forward Count before = 3
moveScoresT[15] = 0
A=10
moveScoresT[15] = 10
highest = 0
Forward Count after = 2
A=10
moveScoresT[0] = 10
i=1
Forward Count before = 2
moveScoresT[1] = 0
FC = 2
i=0
Forward Count before = 3
moveScoresT[0] = 0
A=10
moveScoresT[0] = 10
i=1
Forward Count before = 3
moveScoresT[1] = 0
A=10
moveScoresT[1] = 10
i=2
Forward Count before = 3
moveScoresT[2] = 0
A=10
moveScoresT[2] = 10
i=3
Forward Count before = 3
moveScoresT[3] = 0
A=10
moveScoresT[3] = 10
i=4
Forward Count before = 3
moveScoresT[4] = 0
A=10
moveScoresT[4] = 10
i=5
Forward Count before = 3
moveScoresT[5] = 0
A=10
moveScoresT[5] = 10
i=6
Forward Count before = 3
moveScoresT[6] = 0
A=10
moveScoresT[6] = 10
i=7
Forward Count before = 3
moveScoresT[7] = 0
A=10
moveScoresT[7] = 10
i=8
Forward Count before = 3
moveScoresT[8] = 0
A=10
moveScoresT[8] = 10
i=9
Forward Count before = 3
moveScoresT[9] = 0
A=10
moveScoresT[9] = 10
i=10
Forward Count before = 3
moveScoresT[10] = 0
A=10
moveScoresT[10] = 10
i=11
Forward Count before = 3
moveScoresT[11] = 0
A=10
moveScoresT[11] = 10
i=12
Forward Count before = 3
moveScoresT[12] = 0
A=10
moveScoresT[12] = 10
i=13
Forward Count before = 3
moveScoresT[13] = 0
A=10
moveScoresT[13] = 10
i=14
Forward Count before = 3
moveScoresT[14] = 0
A=10
moveScoresT[14] = 10
i=15
Forward Count before = 3
moveScoresT[15] = 0
A=10
moveScoresT[15] = 10
highest = 0
Press any key to continue . . . << Crashes here
Have I missed something? Can anyone identify where I've gone wrong and why it's crashing. [Edited by - Alexistran on March 12, 2007 11:36:33 AM]
Adam Hamilton
Adam Hamilton
You have posted the function that recurses itself. You havn't posted the function that calls futureSight.

Your output suggests that the crash maybe elsewhere, then again, it could be some kind of stack corruption.

Post the code that calls futureSight (or more specifically, the code up to the point that displays the Press any key to continue...)


haegarr
haegarr
And please post also the symptoms of the crash, especially the error message if one is available.

You're using a static variable to control recursion. Although this is legitimate by itself, it also introduces a pitfall to your code. You might consider to cleanly overhand forwardCount as an additional parameter to BoardImp::futureSight. (However, I haven't looked into your code deep enough to see perhaps any difficulties with overhanding forwardCount.)
Alexistran
Alexistran
Error message is simply: "An unhandled exception occurred in score4.exe[976]"

The function never gets as far as getting back to the function that called it. I have checks in place there for that.

The entire output shown comes only from the futureSight function.

The function is meant to be calculating possible moves from 16 possible move sets by looking 3 moves into the future (a total of 4096 moves).

The function reaches 32 and crashes as it returns up.

There are 16 original branches which then have a further 16 branches and each of those has another 16 branches.
Of the second batch of 16 branches, one executes correctly. One gets as far as returning to the branch before crashing.
It is at that point that it crashes.

I have tried rewriting it with forwardCount as a passed parameter and it makes no difference. It still crashes in the same place.
ToohrVyk
ToohrVyk
What line causes causes the crash? What does the call stack look like when the crash occurs? Do all the local values seem correct when it crashes? From the looks of it, it might be a cleanup issue.
Blog — Facebook
Alexistran
Alexistran
I can't look at the call stack or local variables at the point of crashing. Visual Studio refuses to let me debug properly claiming that no symbols have been loaded (which they have). If anyone knows how to fix this VS problem I'd be grateful as well. I've looked on the internet and done what it says and the problem persists.


It either crashes on:

a = futureSight(tempb, colour,i,forwardCount); // call recursively

or return moveScoresT[highest];

It's one of the two.

EDIT:

Nevermind, I managed to fix VS into letting me debug and found where the problem was exactly.

[Edited by - Alexistran on March 12, 2007 11:18:01 AM]

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.

Sign in to reply to this topic.