Results 1 to 18 of 18
  1. #1
    tabchas's Avatar
    tabchas is offline Member
    Join Date
    Mar 2011
    Location
    Austin
    Posts
    60
    Rep Power
    0

    Default Algorithm Design

    Hey guys I am new to java and wanted to start doing algorithm design. I really do not have any clue on where to start and wanted to see if someone could point me in the right direction. My goal is to be able to design an algorithm for tic tac toe and Connect Four.

    Thanks and any hep will be much appreciated!

  2. #2
    Junky's Avatar
    Junky is offline Grand Poobah
    Join Date
    Jan 2011
    Location
    Dystopia
    Posts
    3,800
    Rep Power
    7

    Default

    Others may disagree but I don't think you develop an algorithm for an entire program. Rather you develop an algorithm to achieve a certain task. For example in tic tac toe you would have an algorithm to determine if player/ai wins. You would have an algorithm to determine if player/ai makes a valid move etc. Basically when you write a program you break it down into smaller steps and work on each step independently. Test each step thoroughly before moving onto the next step.

  3. #3
    tabchas's Avatar
    tabchas is offline Member
    Join Date
    Mar 2011
    Location
    Austin
    Posts
    60
    Rep Power
    0

    Default Algorithm Design

    I have already designed an algorithm to check which player wins. The problem is how do I create an algorithm in which the computer decides which play to move.

  4. #4
    Junky's Avatar
    Junky is offline Grand Poobah
    Join Date
    Jan 2011
    Location
    Dystopia
    Posts
    3,800
    Rep Power
    7

    Default

    Ahhh. That's is getting into the realms of AI. A very complex subject. You can either develop the game so it plays dumb, ie just picks the next available spot. Or you can go all the way into very deep recursion where the game determines all possibly outcomes from this point and decides which move would optimum. This is not an easy thing to teach or learn.

  5. #5
    tabchas's Avatar
    tabchas is offline Member
    Join Date
    Mar 2011
    Location
    Austin
    Posts
    60
    Rep Power
    0

    Default Algorithm Design

    I know but is there any place that I can start at? I mean there has to be a place where everyone starts from. Any links or how did you get started with Algorithm Design?

  6. #6
    Junky's Avatar
    Junky is offline Grand Poobah
    Join Date
    Jan 2011
    Location
    Dystopia
    Posts
    3,800
    Rep Power
    7

    Default

    Is google broken again?

  7. #7
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,764
    Blog Entries
    7
    Rep Power
    21

    Default

    TicTacToe isn't much of a game and the recursion doesn't need to go deeper than 9 levels (the board is full then). The following program lists the complete game as well as the number of board configurations if there are n moves played plus the number of winning situations for that level; here's the complete code just for fun:

    Java Code:
    import java.util.HashSet;
    import java.util.Set;
    
    public class TTT {
    	
    	private static final String[][] wins= {
    		// row    diag1        diag2        column
    		{ "xxx", "x...x...x", "..x.x.x..", "x..x..x" },
    		{ "ooo", "o...o...o", "..o.o.o..", "o..o..o" }		
    	};
    	
    	private static final int[][] pos= {
    		{ 0, 3, 6 }, // row
    		{ 0 }, // diag1
    		{ 0 }, // diag2
    		{ 0, 1, 2 } // column
    	};
    	
    	private static Set<String>[] games= new Set[9];
    	
    	private static char[] board= ".........".toCharArray();
    	
    	private static void initialize() {
    		
    		for (int i= 0; i < games.length; i++) games[i]= new HashSet<String>();
    	}
    	
    	private static boolean win(String s, int level) {
    		
    		for (int i= 0; i < wins[level&1].length; i++) {
    			for (int j= 0; j < pos[i].length; j++) {
    				String p= s.substring(pos[i][j], pos[i][j]+wins[level&1][i].length());
    				if (p.replaceAll(wins[level&1][i], "").length() < p.length())
    					return true;
    			}
    		}
    		return false;		
    	}
    	
    	private static boolean register(int level) {
    		
    		String s= new String(board);
    		
    		if (games[level].contains(s))
    			return true;
    		
    		games[level].add(s);
    		
    		return win(s, level);
    	}
    	
    	private static void play(char p, int level) {
    		
    		if (level == board.length) return;
    		
    		for (int i= 0; i < board.length; i++)
    			if (board[i] == '.') {
    				board[i]= p;
    				if (!register(level))
    					play((char)('x'+'o'-p), level+1);
    				board[i]= '.';
    			}
    	}
    
    	private static int wins(int level) {
    		
    		int total= 0;
    		for (String s : games[level])
    			if (win(s, level)) total++;
    		
    		return total;
    	}
    	
    	private static void report() {
    		
    		for (int i= 0; i < games.length; i++) {
    			System.out.println(i+": "+games[i].size()+"/"+wins(i));
    			System.out.println(games[i]);
    		}
    	}
    	
    	public static void main(String[] args) {
    		
    		initialize();
    		play('x', 0);
    		report();
     	}
    }
    There's not much more to be said about this little game.

    kind regards,

    Jos
    Last edited by JosAH; 03-24-2011 at 09:06 AM. Reason: fixed a small nono
    cenosillicaphobia: the fear for an empty beer glass

  8. #8
    tabchas's Avatar
    tabchas is offline Member
    Join Date
    Mar 2011
    Location
    Austin
    Posts
    60
    Rep Power
    0

    Default

    Is it really possible to make the AI code in a recursive function? From what I have researched, everyone uses a bunch of cases or if/else statements to determine the best possible move. What is the best approach to this problem?

  9. #9
    sunde887's Avatar
    sunde887 is offline Moderator
    Join Date
    Jan 2011
    Location
    Richmond, Virginia
    Posts
    3,069
    Blog Entries
    3
    Rep Power
    8

    Default

    There are multiple ways to do ai search. Recursion is a perfectly acceptable approach, finding the best way should be something you decide. You can do breadth first, depth first ai search. Google and see which you think would be the best solution.

  10. #10
    tabchas's Avatar
    tabchas is offline Member
    Join Date
    Mar 2011
    Location
    Austin
    Posts
    60
    Rep Power
    0

    Default

    What do you guys think is a beginner solution? I have seen people use multiple if/else statements but it is something that seems sort of a "brute-force" method.
    I want to use a solution so I can learn how to use it very well but right now I see so many solutions and I do not know what they are doing. Any ideas?

    Thanks!
    Tabish Chasmawala

  11. #11
    ra4king's Avatar
    ra4king is offline Senior Member
    Join Date
    Apr 2011
    Location
    Atlanta, Georgia, US
    Posts
    396
    Rep Power
    4

    Default

    Research A* and Minimax algorithms.

  12. #12
    tabchas's Avatar
    tabchas is offline Member
    Join Date
    Mar 2011
    Location
    Austin
    Posts
    60
    Rep Power
    0

    Default

    Okay... Also, before I get into the Tic Tac Toe AI Design, should I be at a certain level in Java programming? As in should I already be comfortable with collections, binary trees, recursion, and other intermediate java concepts?
    Tabish Chasmawala

  13. #13
    ra4king's Avatar
    ra4king is offline Senior Member
    Join Date
    Apr 2011
    Location
    Atlanta, Georgia, US
    Posts
    396
    Rep Power
    4

    Default

    No real need for binary trees. In fact, I have never used them so far.

  14. #14
    sunde887's Avatar
    sunde887 is offline Moderator
    Join Date
    Jan 2011
    Location
    Richmond, Virginia
    Posts
    3,069
    Blog Entries
    3
    Rep Power
    8

    Default

    While not having that knowledge won't stop you if you are motivated, it will certainly he'll, I believe it was junky that said earlier that ai is a fairly complex topic, it will absolutely take a good amount of thinking. Strong understanding of basics will allow you to concentrate more on the ai part and less on the basics.

  15. #15
    tabchas's Avatar
    tabchas is offline Member
    Join Date
    Mar 2011
    Location
    Austin
    Posts
    60
    Rep Power
    0

    Default

    Thanks for the advice.

    I've only used recursion once and never used collections before so I am going to learn the basics a little before attempting the AI. Whenever I attempt to code the AI, I am kind of lost, most likely because I do not know the basics to AI Design. I might need to see some more example programs to get used to the whole idea.

    Thanks for your help!
    Tabish Chasmawala

  16. #16
    ra4king's Avatar
    ra4king is offline Senior Member
    Join Date
    Apr 2011
    Location
    Atlanta, Georgia, US
    Posts
    396
    Rep Power
    4

    Default

    Try looking at it logically. For example, if 'A' event happens, what should the computer's reaction be? It is all cause -> effect. Then when you have it figured out on what the conditions and rules are and what the reaction of the computer is, try to find a recursive design somewhere. If you don't see it, makes something simple, no matter how messy.

  17. #17
    tabchas's Avatar
    tabchas is offline Member
    Join Date
    Mar 2011
    Location
    Austin
    Posts
    60
    Rep Power
    0

    Default

    As in I think I can do the AI using if/else statements but I do not really know how to make a recursive function out of it or really understand how to implement an algorithm like A* and Minimax. Its really confusing for me and I want to make the AI in the best way possible.

    I might start out with the if/else approach, but where do I go from there?
    Tabish Chasmawala

  18. #18
    ra4king's Avatar
    ra4king is offline Senior Member
    Join Date
    Apr 2011
    Location
    Atlanta, Georgia, US
    Posts
    396
    Rep Power
    4

    Default

    If/else is good for now, later on you will need to progess to path-finding, which is what A* and Minimax excel at. And don't worry if you don't understand them now, with time and with more experience you will understand. Start making small games, good AI is not necessary right now, you just want something working.

Similar Threads

  1. A* algorithm
    By zjames in forum New To Java
    Replies: 6
    Last Post: 11-25-2010, 01:02 PM
  2. Need some help in an algorithm
    By ea09530 in forum New To Java
    Replies: 3
    Last Post: 04-04-2010, 02:13 PM
  3. Help with an Algorithm
    By Manfizy in forum New To Java
    Replies: 22
    Last Post: 07-03-2009, 08:16 AM
  4. O(log n) algorithm help !!!!!!
    By itseeker87 in forum New To Java
    Replies: 8
    Last Post: 09-09-2008, 06:12 PM
  5. Help with algorithm
    By susan in forum New To Java
    Replies: 1
    Last Post: 07-13-2007, 11:26 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
  •