Java Forums

Main Menu
Home
Today's Posts
FAQ
Search
Contact Us

Java Network
Linux Archive
Java Tips
Java Tips Blog

Sponsored Links





Welcome to the Java Forums.

You are currently viewing our boards as a guest which gives you limited access to view most discussions and access our other features. By joining our free community, you will:

  • have access to post topics
  • communicate privately with other members (PM)
  • not see advertisements between posts
  • have the possibility to earn one of our surprises if you are an active member
  • access many other special features that will be introduced later.

Registration is fast, simple and absolutely free so please, join our community today!

If you have any problems with the registration process or your account login, please contact us.

Reply
 
LinkBack Thread Tools Display Modes
  #1 (permalink)  
Old 04-24-2008, 09:15 AM
Zosden's Avatar
Senior Member
 
Join Date: Apr 2008
Posts: 386
Zosden is on a distinguished road
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 09:25 AM.
Bookmark Post in Technorati
Reply With Quote
Sponsored Links
  #2 (permalink)  
Old 04-29-2008, 09:28 PM
Zosden's Avatar
Senior Member
 
Join Date: Apr 2008
Posts: 386
Zosden is on a distinguished road
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
Bookmark Post in Technorati
Reply With Quote
  #3 (permalink)  
Old 05-01-2008, 10:10 PM
Moderator
 
Join Date: Nov 2007
Posts: 1,659
Java Tip will become famous soon enoughJava Tip will become famous soon enough
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.
__________________
Want to make your IDE the best?
To view links or images in signatures your post count must be 10 or greater. You currently have 0 posts.


To view links or images in signatures your post count must be 10 or greater. You currently have 0 posts.
to our beloved Java Forums! (closes on July 27, 2008)
Bookmark Post in Technorati
Reply With Quote
  #4 (permalink)  
Old 05-01-2008, 10:23 PM
Zosden's Avatar
Senior Member
 
Join Date: Apr 2008
Posts: 386
Zosden is on a distinguished road
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
Bookmark Post in Technorati
Reply With Quote
  #5 (permalink)  
Old 05-02-2008, 10:22 AM
Moderator
 
Join Date: Nov 2007
Posts: 1,659
Java Tip will become famous soon enoughJava Tip will become famous soon enough
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.
__________________
Want to make your IDE the best?
To view links or images in signatures your post count must be 10 or greater. You currently have 0 posts.


To view links or images in signatures your post count must be 10 or greater. You currently have 0 posts.
to our beloved Java Forums! (closes on July 27, 2008)
Bookmark Post in Technorati
Reply With Quote
  #6 (permalink)  
Old 05-02-2008, 10:38 AM
Zosden's Avatar
Senior Member
 
Join Date: Apr 2008
Posts: 386
Zosden is on a distinguished road
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
Bookmark Post in Technorati
Reply With Quote
  #7 (permalink)  
Old 05-02-2008, 10:40 AM
Moderator
 
Join Date: Nov 2007
Posts: 1,659
Java Tip will become famous soon enoughJava Tip will become famous soon enough
Good to hear that..
__________________
Want to make your IDE the best?
To view links or images in signatures your post count must be 10 or greater. You currently have 0 posts.


To view links or images in signatures your post count must be 10 or greater. You currently have 0 posts.
to our beloved Java Forums! (closes on July 27, 2008)
Bookmark Post in Technorati
Reply With Quote
Sponsored Links
Reply


Thread Tools
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

vB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are On


Similar Threads
Thread Thread Starter Forum Replies Last Post
Alpha-beta algorithm, game tree ljaf_1985 New To Java 0 03-28-2008 06:21 PM
SableCC 4-alpha.4 JavaBean Java Announcements 0 03-10-2008 03:57 PM
SableCC 4-alpha.3 levent Java Announcements 0 07-26-2007 09:59 PM
MegaBlock 0.0.1 alpha JavaBean Java Announcements 0 07-14-2007 10:25 PM
SableCC 4-alpha.2 JavaBean Java Announcements 0 07-05-2007 02:16 PM


All times are GMT +3. The time now is 09:56 AM.


VBulletin, Copyright ©2000 - 2009, Jelsoft Enterprises Ltd.
Content Relevant URLs by vBSEO ©2007, Crawlability, Inc.
Copyright ©2006 - 2007, www.java-forums.org