Jump to content
  • Advertisement

Archived

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

Kandolo

Recursion

This topic is 6501 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

In my C++ class, I have an assignment to create a tic tac toe game that uses a recursive function to find out if someone has one. The trick is that it has to be reusable for any size grid (in some fashion). (Another words, I need a way for it to track around the grid). My teacher says she''s never had anyone do it before, and she doesn''t even know if it is possible. I''m assuming it is. Anyone have any suggestions?? I''ve been working on it a week now with no success (I''ve been having to deal with a stack overflow lately ;p) Thanks a lot in advance! And, if not, at least give me reasons as to why using a recursive function is extremely unpractical ;p - Kandolo

Share this post


Link to post
Share on other sites
Advertisement
I'm going to throw out a couple of thoughts to consider. I haven't actually done this, so I'm not guaranteeing success.

Say you start in the top left corner of your grid. You have the entire diagonal, the horizontal, and the vertical. Try picturing this as a tree with 3 rather than the usual 2 branches to start with. Now, consider this:

There are only TWO potential diagonal cases regardless of the size of your tic tac toe grid: One starting in the upper left corner, one starting in the upper right.

This means that the two diagonal cases can be checked independently, and actually pretty easily, I'm sure you can do this one. The diagonal cases can therefore be excluded from the recursion. Yay! BSP tree!

Now, for the actual tree, follow closely here, this could hurt a bit:

ALL vertical wins can be extrapolated recursively from the top row

ALL horizontal wins can be extrapolated recursively from the left column

This is regardless of actual size of grid. Consider:


1 2 3
4 5 6
7 8 9

Head node = 1
Consider: squares in the main branches (top row, left column) have a greater "value" than sub branches (those spawning vertically from the top row and those spawning horizontally from the left column). I add this consideration simply for visual reasons.

Tree: (this had BETTER show up right...)

...............1
......_________/\__________
.....4.....................2
..../.\.................../.\
..5....7.................5...3
./..../................./.../
6....8.................8...6
..../...................../
...9.....................9

Anyway, I think you can see how it would be possible to recursively determine if any of the 2 major paths or N minor paths contain a win.

Disclaimer: I did this off the top of my head. I refuse responsibility to any brain cell damage or frustration it might cause.

-fel

Edit: GRRRRRR. *sigh* *tries dots*

Edited by - felisandria on December 1, 2000 2:31:36 PM

Share this post


Link to post
Share on other sites
I had to do a simillar program some time ago, checking all the possible wins on a chessboard with 8 queens, so it''s simillar to your problem. I used recursion and was able to check the diagnoal quite easily.


Just replace the board[8][8] with the 2d array (if that is what you''re using) for your board.

Also, this wasn''t written to be reused, so you''ll have to change the if statements to whatever numbers you need (possibly using min and max to find how many spots there are).

Sorry if this doesn''t make sense, haven''t had a lot of sleep lately.


//dir[2] doesn''t really need to be an array, it could simply be
//2 variables which tell the function what direction the program
//should check

int chkDiag (int board[8][8], int x, int y, int dir[2])
{
int i,j;

//in other words... if there are any more spots it can go diagnoly
if (x+dir[0] > -1 && x+dir[0] < 8 && y+dir[1] > -1 && y+dir[1] < 8)
{
if (board[ x+dir[0] ][ y+dir[1] ] == 1) //queen at spot
return(1);
else
return( chkDiag(board, x+dir[0], y+dir[1], dir) ); //else, no queen and keep caling function
//until end of diagnol or 2 queens found
}


return(0); //returns 0 meaning it made it to the end of the board with no other queens
}

Share this post


Link to post
Share on other sites
I threw something together just to see if it was easy or not. It is.

The algorithm is real simple, what''s my prize for it?

I wrote a console app to go with it. You can download the exe.

tictactoe

Note, the exec does not check to see if you are trying to overwrite another move, and the top left corner is row 0, col 0.

I forgot to compress the file, and the only reason there is a limit of 30 on the size of the board is I was to lazy to make the board a dynamic 2D array.

Share this post


Link to post
Share on other sites
Ok, the way I see it the most general instance of the problem is to look for a run of length R in for one player in an A x B board. So for standard tic-tac-toe it''s R = 3, A = 3, B = 3. For go-maku it''d be something like R = 5, A = 13, B = 13. (Not sure about the A and B there).

The iterative method would be, assuming that our board data is in an A x B array:

int FindWinner(int ** board, int R, int A, int B) {
int i, j, k, p;
// check for verticle runs
for (i = 0; i < A - R + 1; i ++) {
for (j = 0; j < B; j ++) {
p = board[ i ][ j ];
for (k = 0; k < R && p != 0; k++) {
if (board[ i + k ][ j ] != p) p = 0;
}
if (p != 0) return p;
}
}
// check for horizontal runs
for (i = 0; i < A; i ++) {
for (j = 0; j < (B - R + 1); j++) {
p = board[ i ][ j ];
for (k = 0; k < R && p != 0; k++) {
if (board[ i ][ j + k ] != p) p = 0;
}
if (p != 0) return p;
}
}
// check for diagonal runs
for (i = 0; i < A - R + 1; i ++) {
for (j = 0; j < (B - R + 1); j++) {
p = board[ i ][ j ];
for (k = 0; k < R && p != 0; k++) {
if (board[ i + k ][ j + k ] != p) p = 0;
}
if (p != 0) return p;
}
}
return 0;
}

From here you can turn it into multiple recursive functions or try to turn it into a single recursive function. With multiple recursive functions it''d look like:

int FindVerticle(board, int i, int j, int R, int A, int B) {
int k, p;
p = board[ i ][ j ];
for (k = 1; k < R && p != 0; k++) {
if (board[ i + k ][ j ] != p) p = 0;
}
if (p != 0) return p;

if (j + 1 < B) {
p = FindVerticle(board, i, j + 1, R, A, B);
if (p != 0) return p;
}

// only recurse on i, if j == 0 in order to
// prevent overlap recursion
if (j == 0 && (i + 1) < (A - R + 1)) {
p = FindVerticle(board, i + 1, 0, R, A, B);
if (p != 0) return p;
}

return 0;
}

int FindHorizontal(board, int i, int j, int R, int A, int B) {
// you can fill in yourself
}

int FindDiagonal(board, int i, int j, int R, int A, int B) {
// you can fill in yourself
}

int FindWinner(int ** board, int R, int A, int B) {
int p;

p = FindVerticle(board, 0, 0, R, A, B);
if (p != 0) return p;

p = FindHorizontal(board, 0, 0, R, A, B);
if (p != 0) return p;

p = FindDiagonal(board, 0, 0, R, A, B);
return p;
}


Of course FindVertical, FindHorizontal, FindDiagonal still have a loop in them, so you can either leave it be, introduce more recursive helper functions, or do something evil like:

int FindVerticle(board, int i, int j, int k, int p, int R, int A, int B) {
// see if we have a verticle run
int p_prime;
p_prime = board[ i ][ j ];

// if k > 0, then this was a continuation of a run check
if (k > 0) {
if (p != p_prime) return 0;
if (k + 1 == R) return p;
return FindVerticle(board, i + 1, j, k + 1, p, R, A, B);
} else { // k == 0
// begin run check
if (p_prime != 0) {
p_prime = FindVerticle(board, i + 1, j, 1, p_prime, R, A, B);
if (p_prime != 0) return p_prime;
// otherwise recurse
}

// recurse on j
if (j + 1 < B) {
p_prime = FindVerticle(board, i, j + 1, 0, 0, R, A, B);
if (p_prime != 0) return p_prime;
}

// only recurse on i, if j == 0 in order to
// prevent overlap recursion
if (j == 0 && (i + 1) < (A - R + 1)) {
p_prime = FindVerticle(board, i + 1, 0, 0, 0, R, A, B);
if (p != 0) return p_prime;
}
}

return 0;
}

If you want to take the original FindWinner function and turn it into a single recursive function, first combine the loops:

int FindWinner(int ** board, int R, int A, int B) {
int i, j, k, p_v, p_h, p_d;

for (i = 0; i < A; i ++) {
for (j = 0; j < B; j ++) {
if (i < (A - R + 1)) p_v = board[ i ][ j ];
else p_v = 0;
if (j < (B - R + 1)) p_h = board[ i ][ j ];
else p_h = 0;
if (i < (A - R + 1) && j < (B - R + 1)) p_d = board[ i ][ j ];
else p_d = 0;

for (k = 1; k < R && (p_v != 0 || p_h != 0 || p_d != 0); k++) {
if (i < (A - R + 1)) {
if (board[ i + k ][ j ] != p_v) p_v = 0;
}
if (j < (B - R + 1)) {
if (board[ i ][ j + k ] != p_h) p_h = 0;
}
if (i < (A - R + 1) && j < (B - R + 1)) {
if (board[ i + k ][ j + k ] != p_d) p_d = 0;
}
}
if (p_h != 0) return p_h;
if (p_v != 0) return p_v;
if (p_d != 0) return p_d;
}
}
return 0;
}

Now transform the FindWinner with combined loops into a recursive function with a single for loop:

int FindWinner(int ** board, int i, int j, int R, int A, int B) {
int k, p_v, p_h, p_d;

if (i < (A - R + 1)) p_v = board[ i ][ j ];
else p_v = 0;
if (j < (B - R + 1)) p_h = board[ i ][ j ];
else p_h = 0;
if (i < (A - R + 1) && j < (B - R + 1)) p_d = board[ i ][ j ];
else p_d = 0;

for (k = 1; k < R && (p_v != 0 || p_h != 0 || p_d != 0); k++) {
if (i < (A - R + 1)) {
if (board[ i + k ][ j ] != p_v) p_v = 0;
}
if (j < (B - R + 1)) {
if (board[ i ][ j + k ] != p_h) p_h = 0;
}
if (i < (A - R + 1) && j < (B - R + 1)) {
if (board[ i + k ][ j + k ] != p_d) p_d = 0;
}
}
if (p_h != 0) return p_h;
if (p_v != 0) return p_v;
if (p_d != 0) return p_d;

int p;
if (j + 1 < B) {
p = FindWinner(board, i, j + 1, R, A, B);
}

if (j == 0 && (i + 1) < A) {
p = FindWinner(board, i + 1, 0, R, A, B);
}

return 0;
}

From there you can recurse on k like before. (but more painfully)

int FindWinner(int ** board, int i, int j, int k, int p_v, int p_h, int p_d, int R, int A, int B) {
int p_prime;

if (k > 0) { // continuation of run check
if (p_v == 0 && p_h == 0 && p_d == 0) return 0;
if (i < (A - R + 1)) {
if (board[ i + k ][ j ] != p_v) p_v = 0;
}
if (j < (B - R + 1)) {
if (board[ i ][ j + k ] != p_h) p_h = 0;
}
if (i < (A - R + 1) && j < (B - R + 1)) {
if (board[ i + k ][ j + k ] != p_d) p_d = 0;
}
if (k + 1 == R) {
if (p_v != 0) return p_v;
if (p_h != 0) return p_h;
if (p_d != 0) return p_d;
return 0;
}
return FindWinner(board, i, j, k + 1, p_v, p_h, p_d, R, A, B);
} else { // k == 0
if (i < (A - R + 1)) p_v = board[ i ][ j ];
else p_v = 0;
if (j < (B - R + 1)) p_h = board[ i ][ j ];
else p_h = 0;
if (i < (A - R + 1) && j < (B - R + 1)) p_d = board[ i ][ j ];
else p_d = 0;
p_prime = FindWinner(board, i, j, 1, p_v, p_h, p_d, R, A, B);
if (p_prime != 0) return p_prime;

// no winner, so recurse
if (j + 1 < B) {
p = FindWinner(board, i, j + 1, 0, 0, 0, 0, R, A, B);
}

if (j == 0 && (i + 1) < A) {
p = FindWinner(board, i + 1, 0, 0, 0, 0, 0, R, A, B);
}
}
return 0;
}


Of course, I didn''t compile or check any of these. But you should be able to see enough of how it''s done to fix them yourselves.

Share this post


Link to post
Share on other sites

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!