# Algorithm Design

• 03-24-2011, 02:39 AM
tabchas
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!
• 03-24-2011, 02:46 AM
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.
• 03-24-2011, 03:15 AM
tabchas
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.
• 03-24-2011, 03:19 AM
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.
• 03-24-2011, 03:34 AM
tabchas
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?
• 03-24-2011, 03:42 AM
Junky
• 03-24-2011, 08:37 AM
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:

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();         } }```

kind regards,

Jos
• 04-10-2011, 09:19 PM
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?
• 04-11-2011, 01:46 AM
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.
• 04-17-2011, 01:06 AM
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!
• 04-17-2011, 01:12 AM
ra4king
Research A* and Minimax algorithms.
• 04-17-2011, 03:47 AM
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?
• 04-17-2011, 03:48 AM
ra4king
No real need for binary trees. In fact, I have never used them so far.
• 04-17-2011, 04:03 AM
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.
• 04-17-2011, 02:27 PM
tabchas

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.