# Thread: minmax with Alpha - Beta Pruning

1. ## minmax with Alpha - Beta Pruning

Hello,

I'm new to these forums, so if I post this post has been posted many times before please let me know where another one like it is at.

I have written a Tic Tac Toe game in java using the standard Model - View - Controller. I want to implement an AI system using the minmax with Alpha - Beta pruning. Unfortunately I can not find a decent tutorial or guide to help me. If any one could please at least direct me to a place with a decent tutorial or help me write the code I would be much appreciated.

I will post a download to the zip file because There are to many classes. You can use my code however you like but please leave my name on it. I'm all for open source code, but I also believe that the author should at least be able to say it is their work.

TicTacToe.zip

Thanks for your time and dedication to Computer Science
Last edited by Zosden; 05-02-2008 at 07:25 AM.

2. in case you where wondering min-max is a searching technique and alpha beta pruning is a way to prune the tree to see if its a valid branch.

3. The url is not working. Instead of expecting others to download/open a big project, i reccomend you to try to described your problems as compact as possible. You might try to describe your exact problem. What is wrong with the current implementation.

Instead of coding it for a game, i recommend you to write the algorithm first. Once you are sure that the algorithm works, you can embed the algorithm to any game.

4. Thats the problem I don't understand how min max works. So far my program is fully working, I just wanted to add an AI element to it. My board is represented by a 2D board.

5. Ok. check this to start reading on the topic:

Minimax Explained - AI Depot

Basically, to minimax works, you need a tree of moves in your game. The nodes of this tree represents current state of your game. So for any state, think that you have one node representation.

And you can generate new nodes under a node simply by generating legal moves in the game. So in chess for example, one pawn can move one step forward! Then as a one possible next node you will have the representation of the state where that pawn is moved one step forward.

So far, you learned how to generate a tree. Now you should learn evaluating a node. Basically you assign a number to each node while evaluating, this better the state the higher the evaluation should be!

As a player, you need to maximize the final score. To do that, you select max possible node in the following branch. And you assume that the other user selects the minimum! (So that he minimize your score). In this way, you generate nodes for both MAX's point of view and MIN's point of view and select your action (one of the valid next states!).

If you read that text and mine, i guess it will be more clear for you. Let me know if you have any further questions. By the way, if you dont get a reply soon, please PM me, because i might miss your answer.

6. Thank you this was a very good tutorial, and a very good explanation from yourself. Next time I have an AI question I will contact you and post a thread. After I implement this I will post the source up in this thread.

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•