Skip to main content
GameDev.net gamedev.net
🔒 Locked

My algorithm sucks (4 in a row)

Started by DeadXorAlive Aug 16, 2005 at 4:39 PM 17 replies 5.6k views
Original Post
DeadXorAlive
DeadXorAlive
Just finished my first game in C++. It's a '4 in a row' console game with a little help from conio.h. It works(only for 2 human players) but I'm not so happy with how I did it. Besides my terrible design I am particularly unhappy with one function. It's called CheckVictory, a member of class Bord, and it checks for a victory (duh). Maybe someones cares to give some critique or suggestions how it should be done? I'm also interested in general pointers (no pun intended) to the proper way of implementing algorithms. To parafrase (the code itself is somewhat lengthy): CheckVictory does a lot of checking on a vector of ints, where each int can represent an empty position or one that is filled by a particular player. This vector is always of size 42, and represents a bord of 7 columns and 6 rows. First row goes from 0 to 6, second from 7 to 13, etc. The checking happens in a for-loop which is nested in another for-loop, which contains 4 more loops, 18 if-statements (including boundery-checking for the vector), 6 else-statements, and a bunch of simple expressions like assignments. It is based on the fact that vector[i-7] gives the above row, similiar stuff for diagonals and (ugh) that if (i+1)%7 == 0, it means that the position (i) is on the right side of the bord. I don't like that it's so complicated. I can't even parafrase the idea well in a couple of sentences. Maybe it should not have been an vector to represent the bord? Maybe seven vectors to represent the columns which can grow with .push_back? I think I lack some mathematical skills. I also think there should be a more elegant solution.
smr
smr
Does it work?
DeadXorAlive
DeadXorAlive
Yes it works. I haven't tested all conditions, but it seems to work as intended.
stylin
stylin
First of all congratulations! I don't know how long it's been finished, but I think it's always a good idea to give yourself time to pat yourself on the back for all your hard work.

Second, if your algorithm works for all cases, then maybe there's something else that you might want to improve upon (add a computer player, port to OpenGL/DirectX/GDI).

Third, have you looked into nested and/or recursion?

:stylin:
:stylin: "Make games, not war." "...if you're doing this to learn then just study a modern C++ compiler's implementation." -snk_kid
Zahlman
Zahlman
Separate out the checking for rows vs columns vs diagonals.

Extract a function just for the purpose of checking contents of a row/column. To avoid special cases in the logic, you could have an out-of-bounds request return a different integer value representing 'out-of-bounds'; since it will not equal either a black piece or a red piece (I'm using the traditional Connect 4 colours here), the matching algorithms will Just Work by detecting a non-matching set of pieces. (If you get a silly result like "out-of-bounds wins!", then you need to check your loop indices. :) )

Then see if there are any other obvious simplifications to the logic. If all else fails, post it.

Note that because the dimensions are known, std::vector may not really be of any use to you. With a plain 2D array, you still have a single 'chunk' of storage, and you get obvious syntactic sugar for checking a row/column. However, you will still have to guard against out-of-bounds accesses.
Sneftel
Sneftel
Well, first of all, you're missing a level of abstraction. Representing 2D arrays under the hood as 1D arrays is fine (and necessary) but needs to be hidden inside a class where you don't have to see it. So the first thing you should do is build a good board class, something that allows you to (among other things) find out whether there's a piece in a particular position indexed by row and column. You can have it do bounds checking for you, too... this avoids a LOT of tricky and very hard-to-find errors.

Checking for this sort of victory condition is actually a little tricky to do in an elegant manner. But here's one way to approach it. First of all, forget that your board is 7*6. Make it c*r. Next, forget that it's "connect-4"; now it's "connect-n". Make your victory checker able to find whether there's a victory, for ANY c, r, and n. This sounds counterproductive, but trust me: your final function will be much shorter, and much nicer.
fireside
fireside
Hard to tell much from your description. Any code gets complicated as far as number of lines. The important thing is to get used to breaking your code down into functions and classes that make it more readable. You don't want 100's of lines of sequential code. I often rewrite a program as an excersize. If you can read it and find errors easily, and it works, it's good code.
pinacolada
pinacolada
Well, if it's any help, here's how I would write it.

#define BOARD_WIDTH 6#define BOARD_HEIGHT 7#define GET_INDEX(x,y) ((x)*BOARD_HEIGHT + (y))boolean CheckVictory(){  for (int start_x = 0; start_x < BOARD_WIDTH; start_x++)    for (int start_y = 0; start_y < BOARD_HEIGHT; start_y++)    {      for (int direction=0; direction < 4; direction++)      {        boolean bFourInARow = true;        for (int check = 0; check < 4; check++)        {          int dx[] = {-1, 0, 1, 1};          int dy[] = {-1, -1, 1, 0};          int this_x = start_x + dx[direction] * check;          int this_y = start_y + dy[direction] * check;                    if (this_x < 0 || this_x >= BOARD_WIDTH ||              this_y < 0 || this_y >= BOARD_HEIGHT)          {            bFourInRow = false          }          else          {            boolean bFilledIn = vector[GET_INDEX(this_x,this_y)]; // <- probably need to change this                          if (!bFilledIn)              bFourInARow = false;          }        }        if (bFourInARow) return true;      }    }  return false;}


Warning: code is untested and may or may not be pulled out of my ass

[Edited by - pinacolada on August 16, 2005 5:59:44 PM]
mother
mother
Using a one-dimensional vector for the 2D board is fine. Just make a member function like getPiece(x, y) to hide this detail.

Have you tried breaking your code up into functions?

I haven't tested this code, but maybe it'll give you some ideas:

// 0 = no piece// 1 = player 1's piece// 2 = player 2's pieceint Board::getPiece(int x, int y) {  assert(x >= 0 && x < getWidth() && y >= 0 && y < getHeight());  return pieces[y * getWidth() + x];}bool Board::checkVictory(int& winningPlayer) {  for (int player = 1; player <= 2; ++player)  {    for (int x = 0; x < getWidth() - 4; ++x)    {      for (int y = 0; y < getHeight() - 4; ++y)      {        if (checkFourInARowRight(x, y, player) ||             checkFourInARowDown(x, y, player) ||             checkFourInARowDiagonalRightDown(x, y, player))        {          winningPlayer = player;          return true;        }    }  }  return false;}bool Board::checkFourInARowRight(int startX, int y, int player) {  for (int i = 0; i < 4; ++i)  {    if (getPiece(startX + i, y) != player)    {      return false;    }  }  return true;}bool Board::checkFourInARowDown(int x, int startY, int player) {  for (int i = 0; i < 4; ++i)  {    if (getPiece(x, startY + i) != player)    {      return false;    }  }  return true;}bool Board::checkFourInARowDiagonalRightDown(int x, int y, int player){  for (int i = 0; i < 4; ++i)  {    if (getPiece(x + i, y + i) != player)    {      return false;    }  }  return true;}

nhatkthanh
nhatkthanh
The way I usually write any algorithm is first understand completely what need to be done, then try to divide (divide and conquer stratagies) it as far as I can go for the moment. This process require working the algorithm out on board or on paper. Then it will be a simple logic to code conversion after that. Once the algorithm works and tested, then go in and optimize further, and this might involve changing algorithm for the sub portion of the original algorithm. Yes, divide the algorithm up into many smaller algorithms as much as you can, then you can code the small one easily and replace/changes to the small one.
Matt Apple
Matt Apple
Ok, I presume you are checking for victory conditions after
each player's move. One way to tighten up your program is
to only search for "connect-4's" that include the last position
played. In other words, if a win occurs on any given turn then
the "connect-4" has to include the last position played. This
greatly reduces the number of tests you have to perform as
opposed to checking the entire 6x7 grid.
DeadXorAlive
DeadXorAlive
Fast and very helpful replies. Thank you all very much.

Though my code works just fine, I understand now that it's not reusable at all. I can't read it and understand it without a lot of effort. I can't increase the size of the bord. I have no useable code for a computer player.

I was worried about the overhead, trying to make an efficient algorithm. But I should not have based an algorithm on that criteria, am I right? (I know this is not DOOM3). Just go for nice and good design, than if and only if neccesary optimize the important parts?

Quote:
Third, have you looked into nested and/or recursion?


Recursion means a function is calling itself? I don't understand what a nested vector is, a vector of vectors?

Quote:
One way to tighten up your program is to only search for "connect-4's" that include the last position played.

Of course!!! This is what a human player would do. I knew I was doing some redundant things. Very simple, very nice.
nilkn
nilkn
Quote:
Recursion means a function is calling itself?


Yes. Recursive algorithms can be sort of mind-boggling at first because it's difficult to imagine the algorithm being executed, but once you get the hang of it, recusion allows you to often write very efficient algorithms with very little code.

Quote:
I don't understand what a nested vector is, a vector of vectors?


Yes:

std::vector< std::vector< int > > vec2d;


That is essentially a vector, each element of which is another vector. You could treat each contained vector as a row of your board, for example.

BTW, you probably shouldn't be using nested vectors explicitly. In other words, you'll want to write a help class to wrap up the functionality.
pinacolada
pinacolada
Quote:
Original post by DeadXorAlive
I was worried about the overhead, trying to make an efficient algorithm. But I should not have based an algorithm on that criteria, am I right? (I know this is not DOOM3). Just go for nice and good design, than if and only if neccesary optimize the important parts?


Nah, just worry about making it look good. How many times total does it need to loop? 100? 1,000 times maybe? There's no costly operations going on inside, so 1,000 iterations is practically nothing for modern processors. You would need to have a loop with about 100 million iterations before you ever noticed any performance issues.
Glak
Glak
the key to good code (at least at that amature level) is simply making it readable. If you know what the code is doing and if someone else can come along and read it and figure it out, then it is good code. It doesn't have to have some fancy design that would impress people, it just needs to be understandable.

As for your problem I would make the board 13x12. Put a buffer all around the real board. Instead of red or black pieces fill it with border pieces. Then you don't need to make special cases to avoid going out of bounds.

Ok here are my two tries, the second is based on the first. Once the piece falls you need to check if it is part of a line of four. There are 4 angles that the line can have, up/down, left/right, and both diagonals. Let's say that we are checking for a horizontal line. The piece that fell is one of the four pieces. We need the number of pieces to the left plus the number to the right to be 3+. To organize our code we will need some helper functions. Also the victory check function is going to be passed the location and color of the piece. I assume that 0,0 is the lower left corner.

int GetColorAt(int x, int y); //define this yourselfbool Wins(int x, int y, int color){    //horizontal    int left(0), right(0); //can also be "int left=0;"    //diagonal    int upper_left(0), lower_right(0);    //other diagonal    int lower_left(0), upper_right(0);    //vertical, "up" not needed    int down;    if( GetColorAt(x-1,y)==color )    {        ++left;        if( GetColorAt(x-2,y)==color )        {            ++left;            if( GetColorAt(x-3,y)==color )                 ++left;        }    }    //now do the same thing for the right, I'm not going to type it all here    if(left+right>2)        return true;    //continue on with each other angle}


ok so that code is going to be long, why not make it simpler? Make a function that goes from the starting location outwards, counting how many of the right color are on the way, up to 3. The two parameters to the function would be how to get to the next spot, 1, 0, -1.

int GetColorAt(int x, int y);//as aboveint GetLength(int x, int y, int dx, int dy, int color){    int length(0);    for(int i=1; i<4; ++i)    {        if(GetColorAt( x+i*dx, y+i*dy )==color)            ++Length;        else            break;    }    return length;}bool Wins(int x, int y, int color){    //diagonal from upper rigtht to lower left    if( (GetLength(x,y,1,1,color)+GetLength(x,y,-1,-1,color))>2)        return true;       //diagonal from lower rigtht to upper left    if( (GetLength(x,y,1,-1,color)+GetLength(x,y,-1,1,color))>2)        return true;     //horizontal    if( (GetLength(x,y,1,0,color)+GetLength(x,y,-1,0,color))>2)        return true;     //vertical    if( (GetLength(x,y,0,1,color)+GetLength(x,y,0,-1,color))>2)        return true;    return false;}
cyric74
cyric74
Quote:
Original post by DeadXorAlive
I was worried about the overhead, trying to make an efficient algorithm. But I should not have based an algorithm on that criteria, am I right? (I know this is not DOOM3). Just go for nice and good design, than if and only if neccesary optimize the important parts?


Highly efficient and optimized code is nice, but you'll quickly learn that there are much more important things, like finishing the project in a reasonable amount of time. Sometimes you just have to say 'if it works, it works'--you will find that much easier to say in the future when following the basics of good code design (as has been suggested above).

You can create all kinds of bad code that may shave off lots of time from an algorithm, but it comes at a large cost:

A) Difficult for you to read, and impossible for someone else to even attempt reading
B) Makes the hard work you put in that piece of code totally worthless in the long-run, when it may have possibly generated some decent modular functions you could have used in a future project
C) Makes the program basically useless to show off as demo code for a job application

Honestly, if I were you, I wouldn't nitpick your current code as long as it works. As a learning experience, I would say that this game taught you the most valuable lesson in programming, and so its job is finished. Go on to something bigger, better, and do it with the mental tools learned here.

Cyric
DeadXorAlive
DeadXorAlive
Quote:
Representing 2D arrays under the hood as 1D arrays is fine (and necessary) but needs to be hidden inside a class where you don't have to see it.

A final question(s): is it necessary to code it as a 1D array and why? And if you code it as a array[][], does the compiler translate it into array[] under the hood (just curious)?


With all the help I got from this and the examples, maybe I'll rewrite the whole thing as an excersize now. Make a X in a row or something.
nilkn
nilkn
Quote:
Original post by DeadXorAlive
I was worried about the overhead, trying to make an efficient algorithm. But I should not have based an algorithm on that criteria, am I right? (I know this is not DOOM3). Just go for nice and good design, than if and only if neccesary optimize the important parts?


An efficient algorithm doesn't mean efficient code. In other words, your algorithm is not defined by the code that you write it in; it is independent of language.

What I mean is don't worry about optimizing your code down each and every line (unless you absolutely must). Worry about optimizing your algorithm.

A good algorithm is one that does only what it needs to do to get the job done, within the bounds of clarity.

If your algorithm is so bogged down in complicated mathematics, honestly you should probably considering simplifying it at the expense of efficiency for the sake of clarity and ease of understanding. It'll help you out in the long run when you come back needing to make changes.

Generally, if there's more than one standard algorithm for solving a certain problem, you should usually pick the simplest one. Don't choose the extremely complex one which utilizes highly advanced mathematics that you barely understand.

If you can solve the problem without writing software to solve quadratic equations, do it. So what if you're algorithm is now quadratic whereas it could have been linear? You're losing performance, but gaining clarity.

With modern computers, extremely efficient code doesn't really matter hardly anymore. What does matter, however, is whether or not some random person could understand your code just by looking at it for a few minutes.

So in conclusion: focus less on getting your algorithm very efficient and more on getting your algorithm clear, concise and understandable.

Topic Locked

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

Sign in to reply to this topic.