Help with connect4 algorithm

Huge thanks dude
Workin on that right now!
Again my thanks to you

[edited by - Packetloss on May 24, 2003 8:51:42 PM]

Connect 4 has been solved. I believe the solution uses expert features to significantly reduce the search, then it''s just a simple lookup during play. I can''t find the paper for the life of me, but google has knowledge of it

In a perfect game, I believe the first player wins unless the second plays perfectly too.


This is another learning-based approach:
http://www.cs.tau.ac.il/~evend/Workshop/sadna-games-fun_approx.ppt

And one for the record:
http://ai-depot.com/LogicGames/MiniMax.html

---

Artificial Intelligence Depot - Maybe it''s not all about graphics...

Yeah, the game is solved. But that doesn''t mean that you can''t have fun trying to make a program to play it.

Actually, the first player has a winning strategy. That means that it can win, no matter what the second player does.

I made a strong program to play this many years ago, and I learned a lot in the process. Once you get the program working, you can make tons of improvements to the basic minimax. This is what I did:
- Alpha-beta. Essential. Practically doubles your search depth.
- Clever ordering of the moves. Helps alpha-beta a lot.
- Hash tables. Avoids redundant searches and can also help to sort the moves.
- A good evaluation function. This is perhaps even more important than good searches, and requires several things:
* Knowledge of the relative importance of different threats
* Knowledge of the game result when all possible 3-piece threats have already been created (more a math problem than programming)
- Boosting the search on forced moves. They shouldn''t count as moves at all.
- Opening book. There is no point in having your program thinking from scratch in positions that happen all the time. You build a database of known opening positions with the recommended moves and associated probabilities, and your program just follows the recommendation without thinking. Be careful what you put here!
- Writting the evaluation function in assembly. This was important in 1995, but today''s compilers do a better job.

In the end, my program (running on a 486 at 50MHz, 12 seconds per move) only had to think for a few moves in each game. The early moves were part of the opening book and the on last ~20 moves, the program was powerful enough to search the entire tree.

I made the program for a contest in a Spanish magazine, and I won. It was a lot of fun!

quote:

---

Original post by alexjc
Connect 4 has been solved. I believe the solution uses expert features to significantly reduce the search, then it''s just a simple lookup during play.

---

Velena was the first to solve it in this manner:
Velena, A Shannon C-type program which plays connect four perfectly There are links to papers on this website.

I found a program called Mustrum that can solve the game in under an hour from the starting position with a 1.5GHz machine. I assume that it does not expert strategy, but perhaps it does it sorting the moves during alpha-beta.

Here''s a great article about Expert Play in Connect-Four, James D. Allen to help you make a more effective evaluation function.

Jason Doucette - online résumé page: www.jasondoucette.com
projects, real-time graphics, artificial intelligence, world records, wallpapers/desktops
"Great minds discuss ideas, average minds discuss events, small minds discuss people." - Anna Eleanor Roosevelt, 1884-1962

Connect4 may have been solved for a 7*6 board, but it''s much more fun playing on a 20*10 board for instance. I once coded a Connect4-player once, based on a recursive search function. But you need a pretty good evaluation function to really tell you what''s a good move and what''s not.

Has anyone had a go at trying to make an connect4 application that can handle arbitrary boards?

Thanks,

Edo

Yes, I have. But, it was only a small project for a day or two to get used to writing C++, since at the time I hadn''t written much in it. The links I gave in my last post are actually helpful in a variable sized board, if the height is an even number that is. I am not going to get into the reasons here, take a look at some of those articles if you want to see.

You are quite correct that you need a very good evaluation function for it to play properly. In some cases, a game can be lost after 4 or 5 moves, and no search will solve that with any reasonable time (it would have to see to the end of the game, in which case you have the game solved already).

Jason Doucette - online resume page: www.jasondoucette.com
projects, real-time graphics, artificial intelligence, world records, wallpapers/desktops
"Great minds discuss ideas, average minds discuss events, small minds discuss people." - Anna Eleanor Roosevelt, 1884-1962

quote:

---

Original post by alvaro
- Alpha-beta. Essential. Practically doubles your search depth.
- Clever ordering of the moves. Helps alpha-beta a lot.
- Hash tables. Avoids redundant searches and can also help to sort the moves.

---

Alpha-beta will not double your search depth.

Let''s talk about the effective branching factor first. The effective branching factor is how much longer it takes to perform a search one ply deeper. So if it takes 1 minute to search to depth 8, and it takes 3 minutes to search to depth 9, then your effective branching factor is 3, since depth 9 took 3 times longer than depth 8. This means that to get to depth 10 it will probably take around 9 minutes (3 times longer than depth 9).

Min-max will perform a search on every single move. So if there are 8 legal moves in most connect-4 positions, then the effective branching factor for a min-max search of a connect-4 position is 8. This means that to search to depth 1, you only have to look at 8 moves. Depth 2 = (8 * 8) = 64, depth 3 = (8 * 8 * 8) = 512, and so on.

Here is where alpha-beta comes in. Alpha-beta lowers your effective branching factor. The effectiveness of alpha-beta depends entirely on how well you order the moves you search. So if you can make a good guess at what the best move is, search it before the other legal moves, and your search will take less time. Basically alpha-beta works by searching the first move, then when it searches the next move it says, "The first move was better than this move, so I''m not going to spend as much time searching it." If you don''t search the best move first though, then alpha-beta can''t say, "I already have a better move," and it has to search each move completely until it finds the best move. It has been proven that if you have *perfect* move ordering (meaning you search the best move first, second best second, etc.), you will lower your effective branching factor to the square root of the "real" branching factor. So if your branching factor for min-max in connect-4 was 8, and you were able to get perfect move ordering, your branching factor would go down to about 2.8, which means you get to search deeper. Using min-max, to search to depth 3 we had to look at (8 * 8 * 8) = 512 positions. Using alpha-beta, with our branching factor of 2.8, we have to look at (2.8 * 2.8 * 2.8) = 22 positions. Obviously 22 is a LOT better than 512. Effective branching factor is not constant, so sometimes the search might take 3.0 times as long, somtimes 2.6 times as long, but on average it will be around 2.8 (the square root of 8), if you have good move ordering.

If you have random move ordering (meaning you don''t try to search the best move first), alpha-beta will still help, but it won''t be as effective. If you have the moves ordered from worst to best, then alpha-beta will not help you at all, because alpha-beta becomes pure min-max (has to search every move).

The transposition table will be able to further lower your effective branching factor, because it will stop you from doing expensive searches on positions that you have already searched. The transposition table also helps you order your moves better. Before you do a search, you can look in the transposition table to see if the position has a "best move" stored (maybe from a previous search). If it does, you can search that move first, and that will help alpha-beta out.

There are various other ways to get good move ordering. In chess we use history tables and killer tables. We also use iterative deepening and internal iterative deepening, which helps out a lot. And we use some special case knowledge sometimes, such as "if my opponent just captured my piece, try all of the moves that re-capture his piece", because that will probably be the best move (otherwise we lose our piece).

Great news guys. Ive got the algorithm to work, with a 8 play search. The evaluate function isnt that great yet, but the computer is a very decent player. Thx for all the help guys :D
Im using negamax with alphabeta cutoffs

Btw my algorith, with your help, beats the crap outta my mates algorithm heheh :D

Again my thx