aspose file tools*
The moose likes Game Development and the fly likes Connect four AI using alpha beta pruning algorithm Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Spring in Action this week in the Spring forum!
JavaRanch » Java Forums » Java » Game Development
Bookmark "Connect four AI using alpha beta pruning algorithm" Watch "Connect four AI using alpha beta pruning algorithm" New topic
Author

Connect four AI using alpha beta pruning algorithm

P Padda
Greenhorn

Joined: Oct 31, 2011
Posts: 1
Hi

I'm trying to implement this algorithm in a game of connect four. I'm using this bit of psuedo code to do so :



I'm having trouble in understanding a few parts:
1) The line

Does this mean that every move has to be evaluated against best_move using the "Evalgamestate" method?

2) What data-structure do you use to store every legal move within the "generatemove" method and what information from that particular state do you store?
Ashish Schottky
Ranch Hand

Joined: Dec 29, 2009
Posts: 93
@Padda: Welcome to Ranch.

When you build any board game, its generally better to keep separate classes for organization ,search,evaluation.

I suggest you to write a clean 2-player game.
Then make the AI component by allowing it to play random. This will test for legal moves in a position and winning combinations.
in connect four, winning is simple, so make another fuction, let it return some value if any player has won, this is your maximum score, and in game like connect4, this is what we want to achieve.

Then make sure you would add in more sophisticated search algorithm like min-max. Here I would like to suggest you that you go for a better frame-work of min-max namely "nega-max".
Once you get this working, then add in alpha-beta pruning , PVS or what ever you feel like.


Answer for your 1) ::

Computer in normal min-max search will compare all the scores
say best_move has score +5 and move B will have score +7 then best_move's score will be assigned as 7 and best_move now will be move B.

However, addition of alpha-beta changes the things quickly.
By adding alpha-beta, search doesnt evaluate all nodes(moves), thus it is faster than naive min-max.

Answer for your 2) ::

It differs from programer to programer. In general and widely used basic data-structure are arrays.
Arrays is java are certainly faster than Strings.

If you think further, assuming your game is for 7x6(standard board), there are only 42 cells.
long type in java offers uptil 64 bits, here you can allot 1-bit per cell so that takes only 42 bits.
This is a complicated approach but would be very fast. However I suggest you not to take this approach on first go, make a working connect4, then optimize it.

I hope this is not home-work.

If you want me to help you, then let me know so that I can write on it.
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Connect four AI using alpha beta pruning algorithm