Jump to content
  • Advertisement
Sign in to follow this  
GosuDrew

Connect 4 Game

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

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 this post


Link to post
Share on other sites
Advertisement
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 this post


Link to post
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 this post


Link to post
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.

If the explanation wasn't clear enough, please ask for clarification.

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

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • 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!