Connect 4 in C++

badgermonkey · 12 Feb 2007 at 10:20

Hi,

I have to code a connect 4 game in c++. The game should be played on a 7x6 (7 across 6 up) grid, which should be stored as a 2D array.

This is being done as a console application (in DOS box basically), so windows programming is unneccessary. The pieces can be displayed as different letters, eg. R and B.

I also need to program AI to play against. The AI must be able to make smart decisions, such as blocking pieces, and attempting to win etc.

I don't need to include diagonals in the winning criteria, however if I do there is the potential for very large bonus marks.

If anyone could give me advice on what I need to look at using, perhaps a bit of help on the AI etc it would be extremely useful

It's just I've sat here for 2 hours and all I've managed to do is initialised the array as follows.

Code:

#include "stdafx.h"
#include <iostream.h>

int main(int argc, char* argv[])
{
	int gridWidth = 7 ; int gridHeight = 6 ;	
	int gridArray[gridWidth][gridHeight] ;

	for (i = 0 ; i < gridHeight ; i++)
	{
		for (j = 0 ; j < gridWidth ; j++)
			gridArray[i][j] = 0 ;
	}

	


	return 0;
}

As you see, not much for 2 hours

triggerthat · 12 Feb 2007 at 10:32

Have it in a Grid / Game class and use the main method just to start playing the game.

badgermonkey · 12 Feb 2007 at 11:21

triggerthat said:
Have it in a Grid / Game class and use the main method just to start playing the game.

What would I be messing around with in the class though?

happytechie · 12 Feb 2007 at 11:23

step one is to write a connect 4 game for one player and a seperate class for the computer player that can just make random moves for now. get your player to choose the column and make a check for a win. a diagonal isn't that hard.

you'll need a class to represent all of the major things in the game, perhaps a player, a board and something to check for wins (unless the board does that).

rudimentary AI won't be that hard to do, check all the valid moves, see how many in a tow each one gives and choose the highest sort of thing. TBH if it's taken you two hours to write that you probably need to set your sights a little lower unless it's a long term project.

Personally I wouldn't be using a C style two dimensional array as a game grid, I'd use a C++ class to represent the game board...

what level are you at (or meant to be at) in c++ are we talking 1st year uni Programming 101 course or something else?

Paul

badgermonkey · 12 Feb 2007 at 11:39

rudimentary AI won't be that hard to do, check all the valid moves, see how many in a tow each one gives and choose the highest sort of thing. TBH if it's taken you two hours to write that you probably need to set your sights a little lower unless it's a long term project.

Ah that took two hours because I spent a long time trying to work out how I'd go about doing this program. The actual code there took a couple of minutes to bang out, what I meant was 2 hours after picking up the problem to work on, that was all I've got

And yeah, basically it's first year programming, we've done classes, references, pointers and just recently done some inheritence. No matrices as yet.
So pretty basic

happytechie · 12 Feb 2007 at 11:57

start with design not banging out code.

you need to represent the board in one class and have some sort of game class to control everything. Personally I'd have a player (real person or AI) class and another class to control the display as well.

A 2D array will be fine for storing the board in memory I guess, but why an int array though? I would have thought that a cell of a connect 4 game could be red, black or empty....

In fact why not use a cell class that has the ability to store these things...

Paul

DaveF · 12 Feb 2007 at 12:03

happytechie said:
rudimentary AI won't be that hard to do, check all the valid moves, see how many in a tow each one gives and choose the highest sort of thing. TBH if it's taken you two hours to write that you probably need to set your sights a little lower unless it's a long term project.

Problem is, that level of AI won't beat the average four year old. You really need to look several moves ahead, but I think that's going to be beyond the OP.

Personally I wouldn't be using a C style two dimensional array as a game grid, I'd use a C++ class to represent the game board...

But if that C++ class is just going to hold a 2D array, does it really matter?

Actually, a 2D 7x6 array is probably not the best way of representing the board anyhow. If you surround the board with "psuedo-pieces", you can avoid ever having to check if you're "off the edge", which will make your code a lot simpler.

Once you do that, I think you're better off using a 1D array as this will simplify the AI code somewhat.

Incidentally, Connect 4 was solved in 1988 - there's a thesis on it here.

SiD the Turtle · 12 Feb 2007 at 12:42

Checking wise, it shouldn't be too hard to check adjacent cells have the same colour.

AI wise, I'd say read up on game trees. Is this a uni project? You may have studied game trees in algorithm classes. Basically you'd need the AI to simulate all possible moves for a number of turns. Connect 4 is a finite move game so you could let it work out all moves until the end but it'll cook your CPU unless you're good at algorithms. Then it can see all the possible paths to a win victory and thus make a move that takes it one step closer to that win. It'll then discard all the other parts of the tree and work down that as you make your moves.

Eriedor · 12 Feb 2007 at 13:24

Your best choice of AI for this is deffinetly a game tree.

Use pruning algorithms to lower time to construct the tree as it will be quite large.

happytechie · 12 Feb 2007 at 13:26

There are a load of different ways to do it, and I agree that the AI I suggested would be trivial to beat BUT it would enable the OP to get moving on his project and get SOME marks for the course.

The actual data structures are probably irrelevant anyway it's not like we need to support 90fps with a constantly moving camera position in 3dimensions is it?

I did a connect 4 prog in C for one of the assignments on my C course ages ago, it wasn't that tricky. That assignment was all about manipulating the output on the console and managing input from the user though. monochrome, 80 cols and 26 lines for the win.

HT

DaveF · 12 Feb 2007 at 14:39

happytechie said:
There are a load of different ways to do it, and I agree that the AI I suggested would be trivial to beat BUT it would enable the OP to get moving on his project and get SOME marks for the course.

Didn't intend to suggest otherwise.

The actual data structures are probably irrelevant anyway it's not like we need to support 90fps with a constantly moving camera position in 3dimensions is it?

No, but you might want to support calculating 50 milion nodes per second. And, I think it's an instructive example of how a slightly non-obvious representation can actually simplify the final code you have to write.

What I do find a bit ridiculous is a course project expecting you to produce AI to play against, while saying that "you don't need to handle diagonals"! Diagonals are a heck of a lot easier than producing even a half-decent AI...