Algorithm Design

[tabchas]

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!

[Junky]

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.

[tabchas]

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.

[Junky]

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.

[tabchas]

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?

[Junky]

Is google broken again?

[JosAH]

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:

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

[tabchas]

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?

[sunde887]

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.

[tabchas]

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!

[ra4king]

Research A* and Minimax algorithms.

[tabchas]

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?

[ra4king]

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

[sunde887]

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.

[tabchas]

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!

[ra4king]

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.

[tabchas]

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?

[ra4king]

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.