# Connect 4 Game

This topic is 5018 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Would representing the board with a couple of integers allow the program to search a lot deeper for some given time constraint as opposed to just using a two dimensional array of integers? It would use less space but would the execution time decrease significantly for searching some n-ply depth? Also, I'm doing a minimax search.

##### Share on other sites
You'd get a bit of a saving.

But use alphabeta, and your search depth doubles for the same time. (which is almost impossible to do any other way).

You then have a fast midway evaluator, so you can do some nice move ordering beforehand, as well as having a transposition table and a good leaf evaluator, and your game will be almost unbeatable!

From,
Nice coder

##### Share on other sites
I'm pretty sure that I can implement the alpha-beta search and a transposition table, but not sure on doing the move ordering thing. Is this done by just having the function that generates the possible moves for a given position return a list of moves sorted from best to worst?

##### Share on other sites
I wrote a strong connect 4 program many years ago. The move ordering technique that I used was something similar to history heuristic, which is very popular in chess programming.

Keep a table 42*42 integers for each side, initially all zero. At the end of your alpha-beta function, take the entry corresponding to the side to move, the oponent's last move and the best move from the current alpha-beta loop. If a beta cut took place, use that move.

Before the alpha-beta loop, look at the table for the side to move, the oponent's last move and each of the moves available, and sort the moves according to that value (high values first).

My program also had a table of 42 integers for each side, with the same updating procedure that I just described, but ignoring the oponent's last move. The sorting function used a linear combination of the two (something like 42*table1[side_to_move][last_move][current_move]+table2[side_to_move][current_move]).

Of course you should also store the best move in the transposition tables, and try that move first when you are revisiting a node. Use the history heuristic described above to sort the remaining moves.

A few more tips about connect 4:
- Make the move generator smart enough to detect immediate threats and to recognize suicidal moves, so the set of available moves is reduced. Extend situations where only one move is available (i.e., don't substract one to the depth count for forced moves).
- Learn how to play really well. I described a good analysis of the relative importance of threats here: http://www.gamedev.net/community/forums/topic.asp?topic_id=225611&whichpage=1

• ### What is your GameDev Story?

In 2019 we are celebrating 20 years of GameDev.net! Share your GameDev Story with us.

• 9
• 34
• 16
• 11
• 11
• ### Forum Statistics

• Total Topics
634122
• Total Posts
3015646
×