Results 1 to 7 of 7
  1. #1
    Zosden's Avatar
    Zosden is offline Senior Member
    Join Date
    Apr 2008
    Posts
    384
    Rep Power
    7

    Default 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. #2
    Zosden's Avatar
    Zosden is offline Senior Member
    Join Date
    Apr 2008
    Posts
    384
    Rep Power
    7

    Default

    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.
    My IP address is 127.0.0.1

  3. #3
    Java Tip's Avatar
    Java Tip is offline Moderator
    Join Date
    Nov 2007
    Posts
    1,694
    Blog Entries
    430
    Rep Power
    9

    Default

    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.
    "The sole cause of manís unhappiness is that he does not know how to stay quietly in his room." - Blaise Pascal

  4. #4
    Zosden's Avatar
    Zosden is offline Senior Member
    Join Date
    Apr 2008
    Posts
    384
    Rep Power
    7

    Default

    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.
    My IP address is 127.0.0.1

  5. #5
    Java Tip's Avatar
    Java Tip is offline Moderator
    Join Date
    Nov 2007
    Posts
    1,694
    Blog Entries
    430
    Rep Power
    9

    Default

    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.
    "The sole cause of manís unhappiness is that he does not know how to stay quietly in his room." - Blaise Pascal

  6. #6
    Zosden's Avatar
    Zosden is offline Senior Member
    Join Date
    Apr 2008
    Posts
    384
    Rep Power
    7

    Default

    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.
    My IP address is 127.0.0.1

  7. #7
    Java Tip's Avatar
    Java Tip is offline Moderator
    Join Date
    Nov 2007
    Posts
    1,694
    Blog Entries
    430
    Rep Power
    9

    Default

    Good to hear that..
    "The sole cause of manís unhappiness is that he does not know how to stay quietly in his room." - Blaise Pascal

Similar Threads

  1. Alpha-beta algorithm, game tree
    By ljaf_1985 in forum New To Java
    Replies: 0
    Last Post: 03-28-2008, 04:21 PM
  2. SableCC 4-alpha.4
    By JavaBean in forum Java Software
    Replies: 0
    Last Post: 03-10-2008, 01:57 PM
  3. SableCC 4-alpha.3
    By levent in forum Java Software
    Replies: 0
    Last Post: 07-26-2007, 07:59 PM
  4. MegaBlock 0.0.1 alpha
    By JavaBean in forum Java Software
    Replies: 0
    Last Post: 07-14-2007, 08:25 PM
  5. SableCC 4-alpha.2
    By JavaBean in forum Java Software
    Replies: 0
    Last Post: 07-05-2007, 12:16 PM

Posting Permissions

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