TR Forums

Need to 'estimate the size of the search tree for a game of connect 4 in a 7x6 grid'.

Atm we're thinking of a huge number along the lines of 7^42 but have no way of figuring out if this is correct.

Any help much appreciated!

I've literally *JUST FINISHED* a semester making a Connect4 Board game in Java Amongst other very small programs... no AI, though I thought of trying....

As I understand it, a search tree looks at all the moves available and looks for the most favourable outcome from all the results.

How many levels will it have? 42 I should think, unless there's some rule that you can't make 42 moves without winning, but I don't know of one (btw, don't be surprised if by the end of the development of this you make wild Hitchhiker's Guide to the Galaxy quotes )

How many entries? If I had my calculator with me, and I knew anything about working out permutations, I could give you an answer. Unfortunatly I never covered permutations in maths... sorry.

I'll ask my java lecturer if you like, he might know,
-Mole

yer max depth wud b 42 (or 26 depending if u count both yours and opponents moves)

and i presume it wud branch out by a factor of 7 everytime

7^42 wud b the maximum size of it although that wudnt (and cudnt possibly in an estimate) take into account 'ended game' states.

7^42 is an awfully huge number...

Even doing 1 million of these a second it will take around 2.8 * 10^18 millenia to complete good luck...

Remember that after a column gets filled, that's one less possible choice when deciding where to place a chip.

Still a *HUGE* number until you get down to around 2-3 cols.

Something just doesn't seem right. For example you have to have four checkers in a row in any column, row, or diagonal. If you have 7 colums, that only leaves 7 - 3 = 4 possibilities per row, and 6 - 3 = 3 possibilities per column. Discrediting diagonal, you now only have a search tree of 4 rows and 3 columns now. My brain is tired however, so I don't want to add in the diagonal right now. At least this reduces things to a more reasonable number.

-LS

No Diagonals? That way the game wont be complete. Its just like saying lets play Tic Tac Toe but with no diagonals. ^^

The traditional approach used to estimate game size in typical board games (chess, go, shogi, xiang-qi and the like) is statistical. Measure the average number of moves and then the average branching factor.

A random game generator would give games much larger than real games, so you should make a player than plays reasonably at least (say 2-3 ply-depth bruteforce with random first moves or a random component) and let it play say 100 times, making a log for the average branching and the total number of moves per game.

This isn't a big deal, trust me.

MorgZ

I'm guessing I'm a little late for this thread but just in case...

I just finished an AI project in which I created the game Othello. I also wanted to map out all of the possible steps in the game. I'm guessing that you will not be able to map all the states out just like I was unable too. If you want to try it might be easiest to just start counting in your program when you start mapping.

To do that I had a function that would tell all of the possible moves at a given game state. So for all of the nodes in a given state I created all of the possible moves for the next game state. Then I did this as long as there was a valid move. (In your case a tree would end someone connected 4, or until the board is full).

To store all of this information I used an array of pointers (one for each state of the game, 5 chips, 6 chips, ect...) and then a link list connected each of the states nodes together. Also each node pointed to its parent but not to its children. (To many children and I only needed to look up the tree not down.)

Granted Othello is an 8x8 board but I found with 3 GB of ram/swap I was only able to map between 15 and 16 chips on the board before running out of memory. It was something like 42,000,000 nodes at that point, never found how many nodes it was for 16 chips on the board. I wasn't using a very large structure I think it was only around 30 or so bytes. I'm sure there are quite a few dublicate nodes in there but I didn't want to search each time a node is created and I wanted a node to have only one parent.

I used the MiniMax type AI for my game so I ended up looking/mapping 6 or 7 moves ahead each time the AI was going to move. Worked out pretty well and still ends up using like 60-80 Meg when playing, at some points.

I ended up writing the program in C/C++.

tfp

Oy, there has to be a better way... what are they teaching you guys, how to program for MS??? I would like to think that a good way to play is that same way most people think + 1. For example, the average person will think two or three moves ahead, and not see every single move, but the most obvious. While it would be a little difficult to identify the most obvious, the up front computing would take much less memory than trying everything. Now if the average person sees 3 moves ahead, stop the computer at 4. The thing is, once the opponent moves, most of those moves no longer work and you have to recompute anyway. If you have written a nice routine for identifying likely moves, then you can also test against the opponent's likely moves and skip the unlikely moves which will save even more. Pretty much the same way a typical player thinks. You can then add in a bit of random sampling of unlikely moves to "spice it up".

I dunno, never got into game programming, but by working with small processors all day you learn to optimize or you simply don't make it fit. Perhaps my ideas wont work in reality, but what you are describing seems very memory heavy.

Another thought is to hunt for the most likely move one move at a time until it passes all tests to a set number of iterations. For example:
1. Test for moves that pass the criteria. Toss ones that don't.
2. Randomly choose one that passes, and from that point calculate next move (against possible likely opponent moves).
3. Are there any avaialble moves? Yes, continue, No, start back at first move, and try another branch.
4. Have we reached look ahead # of moves in iteration? No, goto 1. Yes, exit with first move.

Never goes deeper that #of look ahead moves, never stores more than # of look ahead moves at once. Think of it like lightning searching for a conection. The first branch that goes far enough makes contact and you go with that.

I hope this helps.

-LS

Really it all depends on what your trying to do. With my Othello game I don't have that hard of a time beating it when its looking 6 moves a head. I don't need to think that far ahead just have a descent stratagy against the "best move". It also depends on what you are trying to do. I was trying to implement a minimax algo, not an optimized one.

The problem with the algo I was talking about is unless you have a different testing criteria then win or lose you have to map the complete game to use it.

I really don't think 3 or 4 moves a head will make that good of an AI. But I guess it would depend on if you can build some sort of stratagy into the game other then the best move with the current knowledge.

Chances are because its a school project there is no need to do something overly complex because normally they just want something demonstrated and/or compaired. If you just starting out with AI thats normally enough.

For a connect 4 game what would be a good criteria for checking if its a good move other then wins and losses. Othello was simple, just compair number of chips for AI and the Player.

Also yes I to work on small processors /w small amounts of memory at work, thats why the nodes themselves where 30ish bytes storing a 8x8 table, number of chips for AI and Human, and two or three other small peices of information. Without a little thought they could easily be in the 70s...

tfp