It has been quite some time since the last post...
I got busy in Google AI challenge. Thought of sharing few of interesting games from there.
This list will be updated regularly. Have a look... if you are not already challenging your coding skills in here, after seeing at some of these battles, you might want to check it out!
Few things to note :
1) Use the green filter at your left hand side to view the game as the bot would have seen it. Even though we can see the whole map, bots can see areas only within a radius from their own ants.
2) 2 Points are awarded for every kill while only 1 point for a new spawn. No bonus for remaining with the larger army at the end!
3) List seems to getting longer, I will crop away most of these games and will leave only the most elegant ones here.
4) If you have any beautiful games, feel free to comment the links and I will include them in here. :-)
5) Note on Dec 9th. Old games were taken out from the beta site now that the official tournament is on. So I removed those links and including real games from the official competition.
Sunday, September 18, 2011
Tuesday, May 24, 2011
Bringing Down Towers of Hanoi - part10
So we have come to the final part of this series! As promised, we will be ending the series with the source code which solves 4 tower case (can be generalized to more towers)
For those who are new and like to give it a try before looking at the solutions, part4 is probably a good place to start, unless you are really new to Towers of Hanoi, in which case it should be part1.
I haven't yet seen a java code to solve the general case for towers of hanoi for 4 towers. If you see a code let me know. I will try to format this nicely and add some comments too later. Since earlier posts contained all explanations needed, I hope you will be able to figure out the algorithm easily. Enjoy!
package com.araaya.hanoitowers;
import java.util.ArrayList;
import java.util.Hashtable;
import java.util.StringTokenizer;
/**
*@author Ashoka Ekanayaka
* www.it-front.net, www.araaya.com
*/
public class HanoiTowers4 {
//ArrayList<Integer> source1, target1, middle1, middle2;
//int steps = -1;
static Hashtable<Integer, HeightInfo> table = new Hashtable<Integer, HeightInfo>();
static {
table.put(1, new HeightInfo(1,0,1));
}
public static void main(String[] args) {
int height = Integer.parseInt(args[0]);
ArrayList<String> towers = new ArrayList<String>(4);
String s = "";
for (int i=height; i>0; i--) {
s = s + i;
if (i != 1) {
s= s + ",";
}
}
towers.add(s);
towers.add("");
//s = "";
//for (int i=2; i>0; i--) {
// s = s + i;
// if (i != 1) {
// s= s + ",";
// }
//}
towers.add("");
towers.add("");
String moveList = HanoiTowers4.getSolution(height, 4, towers);
String[] moves = moveList.split(",");
System.out.println(moves.length + " Moves");
System.out.println(moveList);
}
public static String getSolution(int diskCount, int towerCount, ArrayList<String> towerContents) {
ArrayList<ArrayList<Integer>> towers = new ArrayList<ArrayList<Integer>>(towerCount);
for (int i=0; i<towerCount; i++) {
String s = towerContents.get(i);
ArrayList<Integer> tower = new ArrayList<Integer>(diskCount);
if (!s.equals("")) {
String[] disks = s.split(",");
for (int j=0; j<disks.length; j++) {
tower.add(Integer.parseInt(disks[j]));
}
}
towers.add(tower);
}
StringBuilder moveList = new StringBuilder();
if (towerCount == 3) {
return buildTower3(diskCount, 0, 0, 2, 1, towers, moveList).toString();
} else if (towerCount == 4) {
return buildTower4(diskCount, 0, 3, 1, 2, towers, moveList).toString();
} else {
return null;
}
}
public static StringBuilder buildTower4(int height, int source, int target, int middle1, int middle2, ArrayList<ArrayList<Integer>> towers, StringBuilder moveList) {
if (height == 0) {
return moveList;
}
ArrayList<Integer> targetTower = towers.get(target);
if (targetTower.contains(Integer.valueOf(height))) {
buildTower4(height-1, source, target, middle1, middle2, towers, moveList);
} else {
ArrayList<Integer> middle1Tower = towers.get(middle1);
ArrayList<Integer> middle2Tower = towers.get(middle2);
if (middle1Tower.contains(Integer.valueOf(height))) {
int temp = middle1;
middle1 = source;
source = temp;
}
if (middle2Tower.contains(Integer.valueOf(height))) {
int temp = middle2;
middle2 = source;
source = temp;
}
int newHeight = getSteps(height).t4Height;
buildTower4(newHeight, source, middle1, middle2, target, towers, moveList);
if (height > 2) {
buildTower3(height-1, newHeight, source, middle2, target, towers, moveList);
}
move(source, target, towers, moveList);
print(towers);
if (height > 2) {
buildTower3(height-1, newHeight, middle2, target, source, towers, moveList);
}
buildTower4(newHeight, middle1, target, middle2, source, towers, moveList);
}
return moveList;
}
public static StringBuilder buildTower3(int height, int ceiling, int source, int target, int middle, ArrayList<ArrayList<Integer>> towers, StringBuilder moveList) {
if (height == ceiling) {
return moveList;
}
ArrayList<Integer> targetTower = towers.get(target);
if (targetTower.contains(Integer.valueOf(height))) {
buildTower3(height-1, ceiling, source, target, middle, towers, moveList);
} else {
ArrayList<Integer> middleTower = towers.get(middle);
if (middleTower.contains(Integer.valueOf(height))) {
int temp = middle;
middle = source;
source = temp;
}
buildTower3(height-1, ceiling, source, middle, target, towers, moveList);
move(source, target, towers, moveList);
print(towers);
buildTower3(height-1, ceiling, middle, target, source, towers, moveList);
}
return moveList;
}
public static HeightInfo getSteps(int height) {
if (table.containsKey(height)) {
return table.get(height);
}
boolean optimalFound = false;
int optimalSteps = Integer.MAX_VALUE;
int t4 = 0;
int steps = 0;
for (int t4Height = height-1; !optimalFound && t4Height>0; t4Height--) {
int t3Height = (height - 1) - t4Height;
steps = 1 + 2*(getSteps(t4Height).steps) + 2*((1 << t3Height) - 1);
if (steps < optimalSteps) {
optimalSteps = steps;
t4 = t4Height;
System.out.println("current minimum steps for height " + height + " is : " + steps + " with " + t4Height + "-" + t3Height);
} else {
optimalFound = true; // no point searching beyond this. current steps are the optimal
}
}
System.out.println("putting => " + height + ":" + optimalSteps + ":" + t4);
HeightInfo info = new HeightInfo(height, t4, optimalSteps);
table.put(height, info);
return info;
}
private static void print(ArrayList<ArrayList<Integer>> towers) {
for (ArrayList<Integer> tower : towers) {
for (Integer i : tower) {
System.out.print(i+",");
}
System.out.print(" : ");
}
System.out.println();
}
private static void move(int source, int target, ArrayList<ArrayList<Integer>> towers, StringBuilder strB) {
ArrayList<Integer> targetTower = towers.get(target);
ArrayList<Integer> sourceTower = towers.get(source);
targetTower.add(sourceTower.get(sourceTower.size()-1)); // add the top most element in source to the top of target
sourceTower.remove(sourceTower.size()-1);
strB.append(source + 1);
strB.append("-");
strB.append(target + 1);
strB.append(",");
}
}
For those who are new and like to give it a try before looking at the solutions, part4 is probably a good place to start, unless you are really new to Towers of Hanoi, in which case it should be part1.
I haven't yet seen a java code to solve the general case for towers of hanoi for 4 towers. If you see a code let me know. I will try to format this nicely and add some comments too later. Since earlier posts contained all explanations needed, I hope you will be able to figure out the algorithm easily. Enjoy!
package com.araaya.hanoitowers;
import java.util.ArrayList;
import java.util.Hashtable;
import java.util.StringTokenizer;
/**
*@author Ashoka Ekanayaka
* www.it-front.net, www.araaya.com
*/
public class HanoiTowers4 {
//ArrayList<Integer> source1, target1, middle1, middle2;
//int steps = -1;
static Hashtable<Integer, HeightInfo> table = new Hashtable<Integer, HeightInfo>();
static {
table.put(1, new HeightInfo(1,0,1));
}
public static void main(String[] args) {
int height = Integer.parseInt(args[0]);
ArrayList<String> towers = new ArrayList<String>(4);
String s = "";
for (int i=height; i>0; i--) {
s = s + i;
if (i != 1) {
s= s + ",";
}
}
towers.add(s);
towers.add("");
//s = "";
//for (int i=2; i>0; i--) {
// s = s + i;
// if (i != 1) {
// s= s + ",";
// }
//}
towers.add("");
towers.add("");
String moveList = HanoiTowers4.getSolution(height, 4, towers);
String[] moves = moveList.split(",");
System.out.println(moves.length + " Moves");
System.out.println(moveList);
}
public static String getSolution(int diskCount, int towerCount, ArrayList<String> towerContents) {
ArrayList<ArrayList<Integer>> towers = new ArrayList<ArrayList<Integer>>(towerCount);
for (int i=0; i<towerCount; i++) {
String s = towerContents.get(i);
ArrayList<Integer> tower = new ArrayList<Integer>(diskCount);
if (!s.equals("")) {
String[] disks = s.split(",");
for (int j=0; j<disks.length; j++) {
tower.add(Integer.parseInt(disks[j]));
}
}
towers.add(tower);
}
StringBuilder moveList = new StringBuilder();
if (towerCount == 3) {
return buildTower3(diskCount, 0, 0, 2, 1, towers, moveList).toString();
} else if (towerCount == 4) {
return buildTower4(diskCount, 0, 3, 1, 2, towers, moveList).toString();
} else {
return null;
}
}
public static StringBuilder buildTower4(int height, int source, int target, int middle1, int middle2, ArrayList<ArrayList<Integer>> towers, StringBuilder moveList) {
if (height == 0) {
return moveList;
}
ArrayList<Integer> targetTower = towers.get(target);
if (targetTower.contains(Integer.valueOf(height))) {
buildTower4(height-1, source, target, middle1, middle2, towers, moveList);
} else {
ArrayList<Integer> middle1Tower = towers.get(middle1);
ArrayList<Integer> middle2Tower = towers.get(middle2);
if (middle1Tower.contains(Integer.valueOf(height))) {
int temp = middle1;
middle1 = source;
source = temp;
}
if (middle2Tower.contains(Integer.valueOf(height))) {
int temp = middle2;
middle2 = source;
source = temp;
}
int newHeight = getSteps(height).t4Height;
buildTower4(newHeight, source, middle1, middle2, target, towers, moveList);
if (height > 2) {
buildTower3(height-1, newHeight, source, middle2, target, towers, moveList);
}
move(source, target, towers, moveList);
print(towers);
if (height > 2) {
buildTower3(height-1, newHeight, middle2, target, source, towers, moveList);
}
buildTower4(newHeight, middle1, target, middle2, source, towers, moveList);
}
return moveList;
}
public static StringBuilder buildTower3(int height, int ceiling, int source, int target, int middle, ArrayList<ArrayList<Integer>> towers, StringBuilder moveList) {
if (height == ceiling) {
return moveList;
}
ArrayList<Integer> targetTower = towers.get(target);
if (targetTower.contains(Integer.valueOf(height))) {
buildTower3(height-1, ceiling, source, target, middle, towers, moveList);
} else {
ArrayList<Integer> middleTower = towers.get(middle);
if (middleTower.contains(Integer.valueOf(height))) {
int temp = middle;
middle = source;
source = temp;
}
buildTower3(height-1, ceiling, source, middle, target, towers, moveList);
move(source, target, towers, moveList);
print(towers);
buildTower3(height-1, ceiling, middle, target, source, towers, moveList);
}
return moveList;
}
public static HeightInfo getSteps(int height) {
if (table.containsKey(height)) {
return table.get(height);
}
boolean optimalFound = false;
int optimalSteps = Integer.MAX_VALUE;
int t4 = 0;
int steps = 0;
for (int t4Height = height-1; !optimalFound && t4Height>0; t4Height--) {
int t3Height = (height - 1) - t4Height;
steps = 1 + 2*(getSteps(t4Height).steps) + 2*((1 << t3Height) - 1);
if (steps < optimalSteps) {
optimalSteps = steps;
t4 = t4Height;
System.out.println("current minimum steps for height " + height + " is : " + steps + " with " + t4Height + "-" + t3Height);
} else {
optimalFound = true; // no point searching beyond this. current steps are the optimal
}
}
System.out.println("putting => " + height + ":" + optimalSteps + ":" + t4);
HeightInfo info = new HeightInfo(height, t4, optimalSteps);
table.put(height, info);
return info;
}
private static void print(ArrayList<ArrayList<Integer>> towers) {
for (ArrayList<Integer> tower : towers) {
for (Integer i : tower) {
System.out.print(i+",");
}
System.out.print(" : ");
}
System.out.println();
}
private static void move(int source, int target, ArrayList<ArrayList<Integer>> towers, StringBuilder strB) {
ArrayList<Integer> targetTower = towers.get(target);
ArrayList<Integer> sourceTower = towers.get(source);
targetTower.add(sourceTower.get(sourceTower.size()-1)); // add the top most element in source to the top of target
sourceTower.remove(sourceTower.size()-1);
strB.append(source + 1);
strB.append("-");
strB.append(target + 1);
strB.append(",");
}
}
Friday, April 29, 2011
Bringing Down Towers of Hanoi - part9
As we promised in part8 of this series, In this post we are going to see few sample outputs from Tower4 program in action. Also we will discuss the algorithm behind how to determine the best breakdown of middle towers. (Remember, in four tower case, we have choices on how to distribute the disks between tower 2 and 3 when we want to move disks from tower 1 to 4)
Let's see the case of 5 disks :
6,5,4,3,2, : : 1, :
6,5,4,3, : : 1, : 2,
6,5,4, : 3, : 1, : 2,
6,5,4, : 3,2, : 1, :
6,5,4, : 3,2,1, : :
6,5, : 3,2,1, : : 4,
6, : 3,2,1, : 5, : 4,
6, : 3,2,1, : 5,4, :
: 3,2,1, : 5,4, : 6,
4, : 3,2,1, : 5, : 6,
4, : 3,2,1, : : 6,5,
: 3,2,1, : : 6,5,4,
: 3,2, : 1, : 6,5,4,
2, : 3, : 1, : 6,5,4,
2, : : 1, : 6,5,4,3,
: : 1, : 6,5,4,3,2,
: : : 6,5,4,3,2,1,
17 Moves
If we look at step 8 above (in blue), we will see that the program has distributed top 5 disks as 3 : 2 in the middle 2 towers. It has then moved the 6th disk to 4th tower. It could have distributed them as 4 : 1, but has found that it will be more costly. Mini tower 3-2-1 it has created on tower2 was created using all 4 towers but the Mini tower it has created on tower3 (which has disks 4 and 5) was created using only 3 towers while keeping the already buildup content at tower 2 intact.
Once the biggest disk (disk 6) was moved to tower 4, program has created a mini tower 4-5 at top of tower4 while keeping tower 2 intact. After that step it has created a mini tower 3-2-1 on tower4 using all 4 towers.
Let's have a good look at again and make sure we understand the process!
In general, to solve 4 tower case for n disks, we need to follow these steps :
1) find optimal numbers for x and y such that x+y=n-1
2) build a tower of hight x in tower2 using all 4 towers
3) build a tower of height y (starting from disk x+1) in tower3 while using only 3 towers (since the content we built on tower2 need to be preserved)
4) move the largest disk (which is n) from tower 1 to tower4
5) build a tower of height y on top of tower4 (starting from disk x+1) while using only 3 towers and keeping the content on tower2 intact.
6) build a tower of height x in tower4 using all 4 towers.
Above is a recursive algorithm because to build a tower of n using all 4 towers, we will have to build a tower of x using all 4 towers!
Now, only one problem remaining.
How to decide on the best distribution between tower2 and 3 (in the example it was 3:2 and not 4:1), that is x was 3 and y was 2 how to find x and y ?
Here too we could use recursion!
Following recursive algorithm and the program is something I have come up with and haven't seen in anywhere else yet. If any of you find a similar algorithm or a better one to solve this puzzle please inform me by putting a comment here with your finding. The code for this will appear in the next post
We need some notations here to make things clearer :
Let T4(n) = 'steps to make a tower of height n using 4 towers'
Let T3(n) = 'steps to make a tower of height n using 3 towers'
Then we can express the steps needed for above 6 steps in this form :
T4(n) = 2*(T4(x)+T3(y)) +1
For instance, T4(6) = 2* (T4(3)+T3(2)) + 1
but we know T3(m) is 2m-1, hence T3(2) above is 22-1 = 3
So, T4(6) = 2*T4(3)+7
To build a tower of height 1, we need just 1 step.
According to above algorithm (steps 1 to 6 given above), building a tower of 2 will need 3 steps, since n=2, x=1 and y=0 in this case. (you can work out how we arrived at number 3 as home work!)
Now that we know steps needed to build a tower of 1 and a tower of 2, can we find the steps needed to create a tower of 3 ?
We have 2 choices
n =3, x=1,y=1 and
n=3, x=2, y=0
In the first case, steps needed will be 5. (home work for readers) In the second, it will be 7! (more home work) So we go with option 1. That means T4(3) =5 !!
Now we could revisit the problem of T4(6).
Earlier we found T4(6) = 2 * T4(3) + 7
then T4(6) = 2*5 + 7 = 17 Which is exactly the number of steps our program has taken to solve!
So we could recursively find best x and y for any n
All we need now is to write the nice recursive code. We will give the readers few days to come up with that code before unraveling it in our last post of Towers Hanoi series.
After that we will move to a new game and a new problem !
Your feedback on the Hanoi Towers series so far will be greatly welcome!
Let's see the case of 5 disks :
6,5,4,3,2, : : 1, :
6,5,4,3, : : 1, : 2,
6,5,4, : 3, : 1, : 2,
6,5,4, : 3,2, : 1, :
6,5,4, : 3,2,1, : :
6,5, : 3,2,1, : : 4,
6, : 3,2,1, : 5, : 4,
6, : 3,2,1, : 5,4, :
: 3,2,1, : 5,4, : 6,
4, : 3,2,1, : 5, : 6,
4, : 3,2,1, : : 6,5,
: 3,2,1, : : 6,5,4,
: 3,2, : 1, : 6,5,4,
2, : 3, : 1, : 6,5,4,
2, : : 1, : 6,5,4,3,
: : 1, : 6,5,4,3,2,
: : : 6,5,4,3,2,1,
17 Moves
If we look at step 8 above (in blue), we will see that the program has distributed top 5 disks as 3 : 2 in the middle 2 towers. It has then moved the 6th disk to 4th tower. It could have distributed them as 4 : 1, but has found that it will be more costly. Mini tower 3-2-1 it has created on tower2 was created using all 4 towers but the Mini tower it has created on tower3 (which has disks 4 and 5) was created using only 3 towers while keeping the already buildup content at tower 2 intact.
Once the biggest disk (disk 6) was moved to tower 4, program has created a mini tower 4-5 at top of tower4 while keeping tower 2 intact. After that step it has created a mini tower 3-2-1 on tower4 using all 4 towers.
Let's have a good look at again and make sure we understand the process!
In general, to solve 4 tower case for n disks, we need to follow these steps :
1) find optimal numbers for x and y such that x+y=n-1
2) build a tower of hight x in tower2 using all 4 towers
3) build a tower of height y (starting from disk x+1) in tower3 while using only 3 towers (since the content we built on tower2 need to be preserved)
4) move the largest disk (which is n) from tower 1 to tower4
5) build a tower of height y on top of tower4 (starting from disk x+1) while using only 3 towers and keeping the content on tower2 intact.
6) build a tower of height x in tower4 using all 4 towers.
Above is a recursive algorithm because to build a tower of n using all 4 towers, we will have to build a tower of x using all 4 towers!
Now, only one problem remaining.
How to decide on the best distribution between tower2 and 3 (in the example it was 3:2 and not 4:1), that is x was 3 and y was 2 how to find x and y ?
Here too we could use recursion!
Following recursive algorithm and the program is something I have come up with and haven't seen in anywhere else yet. If any of you find a similar algorithm or a better one to solve this puzzle please inform me by putting a comment here with your finding. The code for this will appear in the next post
We need some notations here to make things clearer :
Let T4(n) = 'steps to make a tower of height n using 4 towers'
Let T3(n) = 'steps to make a tower of height n using 3 towers'
Then we can express the steps needed for above 6 steps in this form :
T4(n) = 2*(T4(x)+T3(y)) +1
For instance, T4(6) = 2* (T4(3)+T3(2)) + 1
but we know T3(m) is 2m-1, hence T3(2) above is 22-1 = 3
So, T4(6) = 2*T4(3)+7
To build a tower of height 1, we need just 1 step.
According to above algorithm (steps 1 to 6 given above), building a tower of 2 will need 3 steps, since n=2, x=1 and y=0 in this case. (you can work out how we arrived at number 3 as home work!)
Now that we know steps needed to build a tower of 1 and a tower of 2, can we find the steps needed to create a tower of 3 ?
We have 2 choices
n =3, x=1,y=1 and
n=3, x=2, y=0
In the first case, steps needed will be 5. (home work for readers) In the second, it will be 7! (more home work) So we go with option 1. That means T4(3) =5 !!
Now we could revisit the problem of T4(6).
Earlier we found T4(6) = 2 * T4(3) + 7
then T4(6) = 2*5 + 7 = 17 Which is exactly the number of steps our program has taken to solve!
So we could recursively find best x and y for any n
All we need now is to write the nice recursive code. We will give the readers few days to come up with that code before unraveling it in our last post of Towers Hanoi series.
After that we will move to a new game and a new problem !
Your feedback on the Hanoi Towers series so far will be greatly welcome!
Tuesday, April 19, 2011
Arrival of the Java Killer ?
The remarkable news of the impending arrival of the new programming language which is already tipped to be the Java Killer is just out.
I had a entire post covering this in araaya blog. What's more the new language is named as Ceylon !! Find out the reasons behing that naming and a pragmatic forcast of things in here.
(Image source http:/www.decidetostayfit.com)
Thursday, April 14, 2011
Towers of Hanoi - part 8
In the earlier post, we learned that still, (surprisingly) there is no mathematical formula for the minimum number of steps needed to solve a Tower of Hanoi puzzle where there can be towers more than 3 and any number of rings. That is no formula exists which gives the number of steps as a function of rings and towers.
In this post, we will do away with mathematical aspects of this puzzle and focus on what we know better. Yea, the algorithm!
Suppose we have 10 rings (all in the 1st tower) there are 4 towers and you want to move all to the 4th tower.
1) We have to place first 9 rings in the 2 middle towers (tower2 and tower3).
2) Move the 10th towers from tower 1 to tower 4
3) build a tower of 9 in tower4 by using the rings in 2 middle towers.
This will lead to a recursive algorithm. Trick is to get the step 1 above right, how best to distribute the first 9 rings among two middle towers ?
What I did was to write a separate method to determine just that! In that method I will calculate steps needed achieve to each of different distribution of 9 rings. Distributions goes like this :
tower2 have first 8 rings, tower 3 have the ring 9 Or
tower2 have first 6 rings, tower 3 has 7 to 9
tower2 have first 5, tower 3 has 6 to 9
and so on....
So my method will calculate steps needed to create each of that distribution and then find the distribution which will need the least number of steps to create. Once we know that, we just call our recursion function to build towers. For instance, if the best configuration is 1-6 in tower2 and 7-9 in tower3, our recursive function will look like this.
buildtower4(tower1,tower2,tower3,tower4,6) // use all 4 towers and build a tower of 1-6 in tower2)
buildtower3(tower1,tower4,tower3,9,7) // use only the give 3 towers and create a tower with rings 9 to 7 in the third tower)
moveRing(tower1, 10, tower4) // ok, we created the optimal distribution of first 9 rings, now move the 10th ring to final destination)
buildTower3(tower3,tower1,tower4,9,7) // build a tower of 9-7 in tower4. don't touch tower2)
buildTower4(tower1,tower4,tower2,tower3,6) // use all 4 towers and build a tower of 1-6 on top of tower4
Implement something like that in any language and you will have a working code which solves the 4 tower puzzle!
Now, 3 challenges from today's post :
1) Write the algorithm to determine the optimal combination to distribute N rings in the two middle towers.
2) Implement that algorithm in code.
3) implement the given algorithm today to solve the 4 tower puzzle once and for all!
In the next post we will see few sample outputs from my code... and few screen shots to ram in what we discussed today, for those who have already got the message from today's post, good luck with the code!
See you soon.....
In this post, we will do away with mathematical aspects of this puzzle and focus on what we know better. Yea, the algorithm!
Suppose we have 10 rings (all in the 1st tower) there are 4 towers and you want to move all to the 4th tower.
1) We have to place first 9 rings in the 2 middle towers (tower2 and tower3).
2) Move the 10th towers from tower 1 to tower 4
3) build a tower of 9 in tower4 by using the rings in 2 middle towers.
This will lead to a recursive algorithm. Trick is to get the step 1 above right, how best to distribute the first 9 rings among two middle towers ?
What I did was to write a separate method to determine just that! In that method I will calculate steps needed achieve to each of different distribution of 9 rings. Distributions goes like this :
tower2 have first 8 rings, tower 3 have the ring 9 Or
tower2 have first 6 rings, tower 3 has 7 to 9
tower2 have first 5, tower 3 has 6 to 9
and so on....
So my method will calculate steps needed to create each of that distribution and then find the distribution which will need the least number of steps to create. Once we know that, we just call our recursion function to build towers. For instance, if the best configuration is 1-6 in tower2 and 7-9 in tower3, our recursive function will look like this.
buildtower4(tower1,tower2,tower3,tower4,6) // use all 4 towers and build a tower of 1-6 in tower2)
buildtower3(tower1,tower4,tower3,9,7) // use only the give 3 towers and create a tower with rings 9 to 7 in the third tower)
moveRing(tower1, 10, tower4) // ok, we created the optimal distribution of first 9 rings, now move the 10th ring to final destination)
buildTower3(tower3,tower1,tower4,9,7) // build a tower of 9-7 in tower4. don't touch tower2)
buildTower4(tower1,tower4,tower2,tower3,6) // use all 4 towers and build a tower of 1-6 on top of tower4
Implement something like that in any language and you will have a working code which solves the 4 tower puzzle!
Now, 3 challenges from today's post :
1) Write the algorithm to determine the optimal combination to distribute N rings in the two middle towers.
2) Implement that algorithm in code.
3) implement the given algorithm today to solve the 4 tower puzzle once and for all!
In the next post we will see few sample outputs from my code... and few screen shots to ram in what we discussed today, for those who have already got the message from today's post, good luck with the code!
See you soon.....
Tuesday, March 8, 2011
Bringing Down Towers of Hanoi - part7
In last post, we planned to discuss more about the problem of multi towers in hanoi and give some hints on the algorithm.
Interestingly, for multiple towers, no one has still come up with a general formula to express the number of steps as a function of number of towers and number of rings. Some general cases have been figured out though. For instance, we don't need to be mathematicians to say whats the number of steps would be for a problem with more towers than there are rings. Say, 11 towers and only 10 rings! what would be the number of steps to solve this ?
Of course, it would take 9 steps to remove top 9 rings into 9 different towers. Then 10 steps to put all rings in the target tower. 19 steps in all. In other words, 2n-1 ! However, people have found that coming up with a general formula when the number of rings are greater than number of towers (which is greater than 3) is little bit harder than that.
In an earlier post we have seen it takes exactly 2n-1 to solve the 3 tower case (worse case) for n rings.
We have just saw that it takes 2n-1 to solve the m tower case for n rings where m > n (best case)
What happens when m =n, Here is my result. I will intentionally leave out the explanations so you can arrive at that independently.
When m = n, it takes (n-1) + 1 + (n-2) + 3 = 2n+1 steps to solve the puzzle!
Similarly, when m = n-1, it becomes 2n+3
It appears like we could express number of steps as (2n-1) + 2*(n-(m+1)) = 4n - 2m + 1
However, these are true only when number of towers are closer to number of rings. When number of towers become less compared to number of rigs, it get complicated. Say, 10 rings in 4 towers. However, solving such a puzzle manually is much easier (in terms of number of steps needed) than solving a similar number of rings with 3 towers. Problem is when we try to find the optimal strategy.
I could display few graphical outputs from the program I currently have but before that, wouldn't you want to give it a try yourself ? Remember, number of steps needed is drastically reduced now. We will still need a recursive solution as the nature of the problem commands....
Interestingly, for multiple towers, no one has still come up with a general formula to express the number of steps as a function of number of towers and number of rings. Some general cases have been figured out though. For instance, we don't need to be mathematicians to say whats the number of steps would be for a problem with more towers than there are rings. Say, 11 towers and only 10 rings! what would be the number of steps to solve this ?
Of course, it would take 9 steps to remove top 9 rings into 9 different towers. Then 10 steps to put all rings in the target tower. 19 steps in all. In other words, 2n-1 ! However, people have found that coming up with a general formula when the number of rings are greater than number of towers (which is greater than 3) is little bit harder than that.
In an earlier post we have seen it takes exactly 2n-1 to solve the 3 tower case (worse case) for n rings.
We have just saw that it takes 2n-1 to solve the m tower case for n rings where m > n (best case)
What happens when m =n, Here is my result. I will intentionally leave out the explanations so you can arrive at that independently.
When m = n, it takes (n-1) + 1 + (n-2) + 3 = 2n+1 steps to solve the puzzle!
Similarly, when m = n-1, it becomes 2n+3
It appears like we could express number of steps as (2n-1) + 2*(n-(m+1)) = 4n - 2m + 1
However, these are true only when number of towers are closer to number of rings. When number of towers become less compared to number of rigs, it get complicated. Say, 10 rings in 4 towers. However, solving such a puzzle manually is much easier (in terms of number of steps needed) than solving a similar number of rings with 3 towers. Problem is when we try to find the optimal strategy.
I could display few graphical outputs from the program I currently have but before that, wouldn't you want to give it a try yourself ? Remember, number of steps needed is drastically reduced now. We will still need a recursive solution as the nature of the problem commands....
Sunday, February 27, 2011
Bringing Down Towers of Hanoi - part6
Today, we are going to see the magic code which solves Towers of Hanoi General Problem. Those who still (bravely) want to give it an own try before looking at the code. Can go through these hints and do so.
Before going to the code, I have something else to show you. This mathematical proof I found from web, which basically gives a formula for the average number of steps for the general case.
wow, that's some formula for you!
Anyway, as you can see, the code below is the simplicity itself! The solution we propose is bounded by 2n-1, and never exceeds that, also when we present a half done problem, it actually solves it optimally. When you look at the code you get the intuitive feeling that this has to be the optimal solution, wish we could device a mathematical proof too for that fact!
private static void buildTower(int height, ArrayList source,
ArrayList target, ArrayList middle) {
if (height < 0) {
return;
}
if (target.contains(Integer.valueOf(height))) {
buildTower(height -1, source, target, middle);
} else {
if (middle.contains(Integer.valueOf(height))) {
ArrayList temp = middle;
middle = source;
source = temp;
}
buildTower(height-1, source, middle, target);
move(source, target);
print();
buildTower(height-1, middle, target, source);
}
}
Bolded are the lines we added to the last solution. (specific case where all rings are in first tower at the beginning.) Now, isn't this simple ?
One more thing : I havn't yet seen this code (or the algorithm) anywhere in the internet. If some one come across this in anywhere else, please post a comment with the link.
In next post, we will discuss few hints on how to solve the 4 tower case.
Have a nice day!
Before going to the code, I have something else to show you. This mathematical proof I found from web, which basically gives a formula for the average number of steps for the general case.
wow, that's some formula for you!
Anyway, as you can see, the code below is the simplicity itself! The solution we propose is bounded by 2n-1, and never exceeds that, also when we present a half done problem, it actually solves it optimally. When you look at the code you get the intuitive feeling that this has to be the optimal solution, wish we could device a mathematical proof too for that fact!
private static void buildTower(int height, ArrayList
ArrayList
if (height < 0) {
return;
}
if (target.contains(Integer.valueOf(height))) {
buildTower(height -1, source, target, middle);
} else {
if (middle.contains(Integer.valueOf(height))) {
ArrayList
middle = source;
source = temp;
}
buildTower(height-1, source, middle, target);
move(source, target);
print();
buildTower(height-1, middle, target, source);
}
}
Bolded are the lines we added to the last solution. (specific case where all rings are in first tower at the beginning.) Now, isn't this simple ?
One more thing : I havn't yet seen this code (or the algorithm) anywhere in the internet. If some one come across this in anywhere else, please post a comment with the link.
In next post, we will discuss few hints on how to solve the 4 tower case.
Have a nice day!
Saturday, February 26, 2011
Bringing Down Towers of Hanoi - part 5
In the last post, I promised you to give more hints on how to solve (find the algorithm that is) general case of towers of Hanoi. Those who are new to this Hanoi business, can get up to date from earlier parts of the series.
part1
part2
part3
Let's consider the following scenario we have a tower of height 5, instead of having all stacked up neatly in the 1st tower, we have the largest ring already in tower3.
Here's what a run of my code produced.
Step 0 -> 3,2,1,0, : : 4,
Step 1 -> 3,2,1, : 0, : 4,
Step 2 -> 3,2, : 0, : 4,1,
Step 3 -> 3,2, : : 4,1,0,
Step 4 -> 3, : 2, : 4,1,0,
Step 5 -> 3,0, : 2, : 4,1,
Step 6 -> 3,0, : 2,1, : 4,
Step 7 -> 3, : 2,1,0, : 4,
Step 8 -> : 2,1,0, : 4,3,
Step 9 -> : 2,1, : 4,3,0,
Step 10 -> 1, : 2, : 4,3,0,
Step 11 -> 1,0, : 2, : 4,3,
Step 12 -> 1,0, : : 4,3,2,
Step 13 -> 1, : 0, : 4,3,2,
Step 14 -> : 0, : 4,3,2,1,
Step 15 -> : : 4,3,2,1,0,
wow! it found the biggest ring is already in where it wanted to be so finished off with the optimal solution. How do we know that was the optimal ? well, because it took exactly 15 steps, which isthe expected to solve a tower with height 4. Since 5th tile is already there for us, it is like solving a tower of height 4!
Now, then, let's make it little difficult for the computer and see. we pit the biggest ring in the MIDDLE tower at start and let's see what will happen.
Step 0 -> 3,2,1,0, : 4, :
Step 1 -> 3,2,1,0, : : 4,
Step 2 -> 3,2,1, : 0, : 4,
Step 3 -> 3,2, : 0, : 4,1,
Step 4 -> 3,2, : : 4,1,0,
Step 5 -> 3, : 2, : 4,1,0,
Step 6 -> 3,0, : 2, : 4,1,
Step 7 -> 3,0, : 2,1, : 4,
Step 8 -> 3, : 2,1,0, : 4,
Step 9 -> : 2,1,0, : 4,3,
Step 10 -> : 2,1, : 4,3,0,
Step 11 -> 1, : 2, : 4,3,0,
Step 12 -> 1,0, : 2, : 4,3,
Step 13 -> 1,0, : : 4,3,2,
Step 14 -> 1, : 0, : 4,3,2,
Step 15 -> : 0, : 4,3,2,1,
Step 16 -> : : 4,3,2,1,0,
aha! not so difficult again. Code was smart enough to know it should just move the biggest ring to the 3rd tower and it was exactly as the earlier problem.
What if we make things seriously wrong and ask it to solve ? In the normal solution path, after first 3 moves, we should be having the two smallest rings stacked in the middle tower. Let's put them on tower 3 and see.
Step 0 -> 4,3,2, : : 1,0,
Step 1 -> 4,3,2,0, : : 1,
Step 2 -> 4,3,2,0, : 1, :
Step 3 -> 4,3,2, : 1,0, :
Step 4 -> 4,3, : 1,0, : 2,
Step 5 -> 4,3,0, : 1, : 2,
Step 6 -> 4,3,0, : : 2,1,
Step 7 -> 4,3, : : 2,1,0,
Step 8 -> 4, : 3, : 2,1,0,
Step 9 -> 4, : 3,0, : 2,1,
Step 10 -> 4,1, : 3,0, : 2,
Step 11 -> 4,1,0, : 3, : 2,
Step 12 -> 4,1,0, : 3,2, :
Step 13 -> 4,1, : 3,2, : 0,
Step 14 -> 4, : 3,2,1, : 0,
Step 15 -> 4, : 3,2,1,0, :
Step 16 -> : 3,2,1,0, : 4,
Step 17 -> 0, : 3,2,1, : 4,
Step 18 -> 0, : 3,2, : 4,1,
Step 19 -> : 3,2, : 4,1,0,
Step 20 -> 2, : 3, : 4,1,0,
Step 21 -> 2, : 3,0, : 4,1,
Step 22 -> 2,1, : 3,0, : 4,
Step 23 -> 2,1,0, : 3, : 4,
Step 24 -> 2,1,0, : : 4,3,
Step 25 -> 2,1, : : 4,3,0,
Step 26 -> 2, : 1, : 4,3,0,
Step 27 -> 2, : 1,0, : 4,3,
Step 28 -> : 1,0, : 4,3,2,
Step 29 -> 0, : 1, : 4,3,2,
Step 30 -> 0, : : 4,3,2,1,
Step 31 -> : : 4,3,2,1,0,
great! it didn't exceed 31 steps.
Now, can you come up with the code to produce this ? give it a try.... I have a one last hint. Solving is not so difficult. it will only add just few extra lines to the earlier code we have discussed.
Meanwhile, for those who have already come up with the code (but shy to post it to us on comments), we have the next stage of the challenge!
What about 4 Towers ? Solving this is easy when we do it manually and takes lesser number of steps. How about coming up with an algorithm to do that ?
This is a very interesting challenge to contemplate on......
part1
part2
part3
Let's consider the following scenario we have a tower of height 5, instead of having all stacked up neatly in the 1st tower, we have the largest ring already in tower3.
Here's what a run of my code produced.
Step 0 -> 3,2,1,0, : : 4,
Step 1 -> 3,2,1, : 0, : 4,
Step 2 -> 3,2, : 0, : 4,1,
Step 3 -> 3,2, : : 4,1,0,
Step 4 -> 3, : 2, : 4,1,0,
Step 5 -> 3,0, : 2, : 4,1,
Step 6 -> 3,0, : 2,1, : 4,
Step 7 -> 3, : 2,1,0, : 4,
Step 8 -> : 2,1,0, : 4,3,
Step 9 -> : 2,1, : 4,3,0,
Step 10 -> 1, : 2, : 4,3,0,
Step 11 -> 1,0, : 2, : 4,3,
Step 12 -> 1,0, : : 4,3,2,
Step 13 -> 1, : 0, : 4,3,2,
Step 14 -> : 0, : 4,3,2,1,
Step 15 -> : : 4,3,2,1,0,
wow! it found the biggest ring is already in where it wanted to be so finished off with the optimal solution. How do we know that was the optimal ? well, because it took exactly 15 steps, which isthe expected to solve a tower with height 4. Since 5th tile is already there for us, it is like solving a tower of height 4!
Now, then, let's make it little difficult for the computer and see. we pit the biggest ring in the MIDDLE tower at start and let's see what will happen.
Step 0 -> 3,2,1,0, : 4, :
Step 1 -> 3,2,1,0, : : 4,
Step 2 -> 3,2,1, : 0, : 4,
Step 3 -> 3,2, : 0, : 4,1,
Step 4 -> 3,2, : : 4,1,0,
Step 5 -> 3, : 2, : 4,1,0,
Step 6 -> 3,0, : 2, : 4,1,
Step 7 -> 3,0, : 2,1, : 4,
Step 8 -> 3, : 2,1,0, : 4,
Step 9 -> : 2,1,0, : 4,3,
Step 10 -> : 2,1, : 4,3,0,
Step 11 -> 1, : 2, : 4,3,0,
Step 12 -> 1,0, : 2, : 4,3,
Step 13 -> 1,0, : : 4,3,2,
Step 14 -> 1, : 0, : 4,3,2,
Step 15 -> : 0, : 4,3,2,1,
Step 16 -> : : 4,3,2,1,0,
aha! not so difficult again. Code was smart enough to know it should just move the biggest ring to the 3rd tower and it was exactly as the earlier problem.
What if we make things seriously wrong and ask it to solve ? In the normal solution path, after first 3 moves, we should be having the two smallest rings stacked in the middle tower. Let's put them on tower 3 and see.
Step 0 -> 4,3,2, : : 1,0,
Step 1 -> 4,3,2,0, : : 1,
Step 2 -> 4,3,2,0, : 1, :
Step 3 -> 4,3,2, : 1,0, :
Step 4 -> 4,3, : 1,0, : 2,
Step 5 -> 4,3,0, : 1, : 2,
Step 6 -> 4,3,0, : : 2,1,
Step 7 -> 4,3, : : 2,1,0,
Step 8 -> 4, : 3, : 2,1,0,
Step 9 -> 4, : 3,0, : 2,1,
Step 10 -> 4,1, : 3,0, : 2,
Step 11 -> 4,1,0, : 3, : 2,
Step 12 -> 4,1,0, : 3,2, :
Step 13 -> 4,1, : 3,2, : 0,
Step 14 -> 4, : 3,2,1, : 0,
Step 15 -> 4, : 3,2,1,0, :
Step 16 -> : 3,2,1,0, : 4,
Step 17 -> 0, : 3,2,1, : 4,
Step 18 -> 0, : 3,2, : 4,1,
Step 19 -> : 3,2, : 4,1,0,
Step 20 -> 2, : 3, : 4,1,0,
Step 21 -> 2, : 3,0, : 4,1,
Step 22 -> 2,1, : 3,0, : 4,
Step 23 -> 2,1,0, : 3, : 4,
Step 24 -> 2,1,0, : : 4,3,
Step 25 -> 2,1, : : 4,3,0,
Step 26 -> 2, : 1, : 4,3,0,
Step 27 -> 2, : 1,0, : 4,3,
Step 28 -> : 1,0, : 4,3,2,
Step 29 -> 0, : 1, : 4,3,2,
Step 30 -> 0, : : 4,3,2,1,
Step 31 -> : : 4,3,2,1,0,
great! it didn't exceed 31 steps.
Now, can you come up with the code to produce this ? give it a try.... I have a one last hint. Solving is not so difficult. it will only add just few extra lines to the earlier code we have discussed.
Meanwhile, for those who have already come up with the code (but shy to post it to us on comments), we have the next stage of the challenge!
What about 4 Towers ? Solving this is easy when we do it manually and takes lesser number of steps. How about coming up with an algorithm to do that ?
This is a very interesting challenge to contemplate on......
Wednesday, February 23, 2011
Bringing Down Towers of Hanoi - part4
In last post, we wondered what on earth the number 2n-1 doing (regardless of how many N rings we used!) in our little towers problem, for all the values of N.
1) make a tower N-1 on the transit tower
2) move ring N from source to the final destination
3) make a tower N-1 on final destination
That involved 2 towers with height N-1 and moving of one ring. Similarly making a tower of N-1 will be equal to making 2 towers of N-2 and moving a ring. if we expand this for 3 ring case:
tower of 3 = 2 * (tower of 2) + 1 = 2 * (2*(tower of 1) +1) + 1 = 2 * (2*(1) +1) + 1 = 7 = 23 - 1
(since making a tower of 1 always takes one move)
so, making a tower of 3 involved making 2 towers of 2 and 1 move.
that is, 4 towers of 1 and 2 + 1 moves.
that is, 2(3-1) towers of 1 and 21 + 20 moves. (making a tower of 1 takes just 1 move)
that is, 2n-1 + (2n-2 + 2n-3 + 2n-4 + ... + 20)
Total Steps = 2n-1 + (2n-2 + 2n-3 + 2n-4 + ... + 1)
but the sum of sequence (2n-2 + 2n-3 + 2n-4 + ... + 1) = 2n-1 - 1
Hence total steps = 2n-1 + 2n-1 - 1 = 2 * (2n-1 ) - 1 = 2n-1 !!
Wow, now we know why it has to be 2n-1 always !!
Our series is only just starting to get interesting! Now to the today's challenge :
We can now write a nice recursive function to solve the puzzle. However, what we are solving is actually a subset of the problem. We have so far considered cases where all the rings are in tower 1. How about we removing that restriction, how about letting the rings to be anywhere on 3 towers (as long as a bigger ring is not upon a smaller). Can we come up with the code to resolve that ?
In fact, this can be considered as the general case in Towers of Hanoi. What we have discussed in earlier posts was just a specific subset of it. In the next post, we will come with few more hits on how to approach that.
Meanwhile, try it out yoursef!
Tuesday, February 22, 2011
Bringing Down Towers of Hanoi - part3
Today, we will see the code to solve Towers of Hanoi. A simple recursive function which does following... (If we have 10 rings, N would be 10)
1) build a tower of height N-1 on tower2 (from tower1)
2) move the ring N from tower1 into tower3
3) build a tower of height N-1 (again) but this time on top of tower3 (from tower2)
but we have to do it recursive for N-1 (that is 9) too then also for 8 etc .. For those who are new to the series or like to give another attempt to write the code on their own, you can visit here and here for details and motivation.
The Complete Java code can be found at the end of this post. (it would be straightforward to write this in any other language) You can run it passing the number of rings as a parameter for the main method. ie : java HanoiTowers 5 and it will display the proceedings in a text base command line display.
This is the output I got for 5 rings :
Step 0 -> 4,3,2,1,0, : :
Step 1 -> 4,3,2,1, : : 0,
Step 2 -> 4,3,2, : 1, : 0,
Step 3 -> 4,3,2, : 1,0, :
Step 4 -> 4,3, : 1,0, : 2,
Step 5 -> 4,3,0, : 1, : 2,
Step 6 -> 4,3,0, : : 2,1,
Step 7 -> 4,3, : : 2,1,0,
Step 8 -> 4, : 3, : 2,1,0,
Step 9 -> 4, : 3,0, : 2,1,
Step 10 -> 4,1, : 3,0, : 2,
Step 11 -> 4,1,0, : 3, : 2,
Step 12 -> 4,1,0, : 3,2, :
Step 13 -> 4,1, : 3,2, : 0,
Step 14 -> 4, : 3,2,1, : 0,
Step 15 -> 4, : 3,2,1,0, :
Step 16 -> : 3,2,1,0, : 4,
Step 17 -> 0, : 3,2,1, : 4,
Step 18 -> 0, : 3,2, : 4,1,
Step 19 -> : 3,2, : 4,1,0,
Step 20 -> 2, : 3, : 4,1,0,
Step 21 -> 2, : 3,0, : 4,1,
Step 22 -> 2,1, : 3,0, : 4,
Step 23 -> 2,1,0, : 3, : 4,
Step 24 -> 2,1,0, : : 4,3,
Step 25 -> 2,1, : : 4,3,0,
Step 26 -> 2, : 1, : 4,3,0,
Step 27 -> 2, : 1,0, : 4,3,
Step 28 -> : 1,0, : 4,3,2,
Step 29 -> 0, : 1, : 4,3,2,
Step 30 -> 0, : : 4,3,2,1,
Step 31 -> : : 4,3,2,1,0,
Step 0 above was the starting state of 3 towers (separated by ":" s). To solve the entire problem, it took only 4 lines of code!
source, ArrayList target, ArrayList middle) {
if (height < 0) return;
buildTower(height-1, source, middle, target);
move(source, target); // just moves the top ring from source into top of target
buildTower(height-1, middle, target, source);
}
That was all which took for solving the whole puzzle, Now, that's the power of recursion!
Now to the second part of the challenge : The puzzle above took exactly 31 moves. Similarly you would see puzzle with 10 will take 1023. 4 rings will take 15. N rings will take exactly
How did that happen ? can we explain how on earth the value 2n - 1 comes in for all values of N ? what is the significance of 2 there ? Try to figure it out, we will discuss the explanation in the next post.
Meanwhile...
Following is the complete Java code for today's post. Enjoy!
}
1) build a tower of height N-1 on tower2 (from tower1)
2) move the ring N from tower1 into tower3
3) build a tower of height N-1 (again) but this time on top of tower3 (from tower2)
but we have to do it recursive for N-1 (that is 9) too then also for 8 etc .. For those who are new to the series or like to give another attempt to write the code on their own, you can visit here and here for details and motivation.
The Complete Java code can be found at the end of this post. (it would be straightforward to write this in any other language)
This is the output I got for 5 rings :
Step 0 -> 4,3,2,1,0, : :
Step 1 -> 4,3,2,1, : : 0,
Step 2 -> 4,3,2, : 1, : 0,
Step 3 -> 4,3,2, : 1,0, :
Step 4 -> 4,3, : 1,0, : 2,
Step 5 -> 4,3,0, : 1, : 2,
Step 6 -> 4,3,0, : : 2,1,
Step 7 -> 4,3, : : 2,1,0,
Step 8 -> 4, : 3, : 2,1,0,
Step 9 -> 4, : 3,0, : 2,1,
Step 10 -> 4,1, : 3,0, : 2,
Step 11 -> 4,1,0, : 3, : 2,
Step 12 -> 4,1,0, : 3,2, :
Step 13 -> 4,1, : 3,2, : 0,
Step 14 -> 4, : 3,2,1, : 0,
Step 15 -> 4, : 3,2,1,0, :
Step 16 -> : 3,2,1,0, : 4,
Step 17 -> 0, : 3,2,1, : 4,
Step 18 -> 0, : 3,2, : 4,1,
Step 19 -> : 3,2, : 4,1,0,
Step 20 -> 2, : 3, : 4,1,0,
Step 21 -> 2, : 3,0, : 4,1,
Step 22 -> 2,1, : 3,0, : 4,
Step 23 -> 2,1,0, : 3, : 4,
Step 24 -> 2,1,0, : : 4,3,
Step 25 -> 2,1, : : 4,3,0,
Step 26 -> 2, : 1, : 4,3,0,
Step 27 -> 2, : 1,0, : 4,3,
Step 28 -> : 1,0, : 4,3,2,
Step 29 -> 0, : 1, : 4,3,2,
Step 30 -> 0, : : 4,3,2,1,
Step 31 -> : : 4,3,2,1,0,
Step 0 above was the starting state of 3 towers (separated by ":" s). To solve the entire problem, it took only 4 lines of code!
if (height < 0) return;
buildTower(height-1, source, middle, target);
move(source, target); // just moves the top ring from source into top of target
buildTower(height-1, middle, target, source);
}
That was all which took for solving the whole puzzle, Now, that's the power of recursion!
How did that happen ? can we explain how on earth the value 2n - 1 comes in for all values of N ? what is the significance of 2 there ? Try to figure it out, we will discuss the explanation in the next post.
Meanwhile...
Following is the complete Java code for today's post. Enjoy!
package com.araaya.hanoitowers;
import java.util.ArrayList;
/**
*@author Ashoka Ekanayaka
* www.it-front.net, www.araaya.com
*/
public class HanoiTowers {
static ArrayList source1, target1, middle1;
static int steps = -1;
public static void main(String[] args) {
int height = Integer.parseInt(args[0]);
source1 = new ArrayList(height);
target1 = new ArrayList(height);
middle1 = new ArrayList(height);
for (int i=height-1; i >= 0; i--) {
source1.add(i);
}
print();
buildTower(height-1, source1, target1, middle1);
}
private static void buildTower(int height, ArrayList source, ArrayList target,
ArrayList middle) {
ArrayList
if (height < 0) return;
buildTower(height-1, source, middle, target);
buildTower(height-1, source, middle, target);
move(source, target);
print();
buildTower(height-1, middle, target, source);
}
private static void print() {
steps++;
System.out.print("Step " + steps + " -> ");
for (Integer i : source1) {
System.out.print(i+",");
}
System.out.print(" : ");
for (Integer i : middle1) {
System.out.print(i+",");
}
System.out.print(" : ");
for (Integer i : target1) {
System.out.print(i+",");
}
System.out.println();
}
private static void move(ArrayList source, ArrayList target) {
target.add(source.get(source.size()-1)); // move top element in source to top of target
source.remove(source.size()-1);
}
}
Bringing Down Towers of Hanoi - part2
Ok, Here we would discuss the solution and the code to implement it for our little tower puzzle. Those who are new to the series or those who like to give one last try at the puzzle before looking at the answer. Can do so by going back to part1.
Let's imagine we have a simple tower of 5 rings.
To move the rings in first tower to 3rd tower, we need to move the larger ring to 3rd tower first since we can not place it above any other rings. (remember the rule : there can never be a larger ring on top of a smaller one) However, to move the largest ring from tower 1, we need to move all the other out of it first so that we can lift it. At the same time we have to keep the tower1 empty so that we can put the largest ring there. That means we need to have this position.
Aha! now we can move the largest ring to tower3, then we will have to build a tower from 1-4 on top of tower 3 to complete the puzzle.
In other words, to build a tower of height N on tower3 (from tower1), we need to :
1) build a tower of height N-1 on tower2 (from tower1)
2) move the ring N from tower1 into tower3
3) build a tower of height N-1 (again) but this time on top of tower3 (from tower2)
Let's go back to the diagram where we have cleared tower1 to lift the largest ring (5th ring) :
To lift that, we had to create a tower of 1-4 on tower2, but to do that we need to move the ring 4 into tower2, this means we need to remove rings 1-3 from tower 1 first so that we can move ring4 into the middle one...
Hmm, so we needed to build a tower 1-3 on tower3 in order to move 4 into tower2! (in order to move ring 5 to the ultimate goal, tower3) Similarly, we would first have to build a tower 1-2 on tower2 to move the ring3 to tower3. To do that, we need to move 1 into tower3 so that we can move 2 into tower 2. So our first move should be :
Thus, moving the smallest ring to tower2 as the first move will be wrong! ring1 has to be on tower 3 because : (hold your breadth now, see whether you can follow this in your head till the end)
We needed to move 2 into tower2 (to build 1-2 on tower2), that was because
We needed to move 3 into tower3 (to build 1-3 on tower3), that was because
We needed to move 4 into tower2 (to build 1-4 on tower2), that was because
We needed to move 5 into tower3 (to build1-5 on tower3), that was because
It was the end goal of the puzzle!
Simple isn't it ? Solving the case of 10 rings would have the exact same logic. There we will have to move ring 1 into tower2 as our first move. (follow the same logic in your mind for 10 steps and you will see why)
Now to the code. Earlier we deduced that,
Building a tower of height N on tower3 (from tower1), is as same as saying :
1) build a tower of height N-1 on tower2 (from tower1)
2) move the ring N from tower1 into tower3
3) build a tower of height N-1 (again) but this time on top of tower3 (from tower2)
that included building a tower of N-1 on tower2, but in the same logic, we can define building a tower of N-1 as :
1) build a tower of height N-2 on tower3 (from tower1)
2) move the ring N-1 from tower1 into tower2
3) build a tower of height N-2 (again) but this time on top of tower2 (from tower3)
and so on until we build a tower of 1. Now, can write the small little recursive function to solve the entire puzzle?
Hint : it has only 3 lines.
In the next post, we will see the code and we will also investigate why that it always take 2n - 1 steps to solve a Tower of Hanoi problem with N rings.
Challenge 1 : write the code to solve Towers of Hanoi puzzle for a given N.
Challenge 2 : in the above solving algorithm, prove that it always takes exactly 2n - 1 steps to solve the puzzle.
Let's imagine we have a simple tower of 5 rings.
To move the rings in first tower to 3rd tower, we need to move the larger ring to 3rd tower first since we can not place it above any other rings. (remember the rule : there can never be a larger ring on top of a smaller one) However, to move the largest ring from tower 1, we need to move all the other out of it first so that we can lift it. At the same time we have to keep the tower1 empty so that we can put the largest ring there. That means we need to have this position.
Aha! now we can move the largest ring to tower3, then we will have to build a tower from 1-4 on top of tower 3 to complete the puzzle.In other words, to build a tower of height N on tower3 (from tower1), we need to :
1) build a tower of height N-1 on tower2 (from tower1)
2) move the ring N from tower1 into tower3
3) build a tower of height N-1 (again) but this time on top of tower3 (from tower2)
Let's go back to the diagram where we have cleared tower1 to lift the largest ring (5th ring) :
To lift that, we had to create a tower of 1-4 on tower2, but to do that we need to move the ring 4 into tower2, this means we need to remove rings 1-3 from tower 1 first so that we can move ring4 into the middle one...
Hmm, so we needed to build a tower 1-3 on tower3 in order to move 4 into tower2! (in order to move ring 5 to the ultimate goal, tower3) Similarly, we would first have to build a tower 1-2 on tower2 to move the ring3 to tower3. To do that, we need to move 1 into tower3 so that we can move 2 into tower 2. So our first move should be :
Thus, moving the smallest ring to tower2 as the first move will be wrong! ring1 has to be on tower 3 because : (hold your breadth now, see whether you can follow this in your head till the end)
We needed to move 2 into tower2 (to build 1-2 on tower2), that was because
We needed to move 3 into tower3 (to build 1-3 on tower3), that was because
We needed to move 4 into tower2 (to build 1-4 on tower2), that was because
We needed to move 5 into tower3 (to build1-5 on tower3), that was because
It was the end goal of the puzzle!
Simple isn't it ? Solving the case of 10 rings would have the exact same logic. There we will have to move ring 1 into tower2 as our first move. (follow the same logic in your mind for 10 steps and you will see why)
Now to the code. Earlier we deduced that,
Building a tower of height N on tower3 (from tower1), is as same as saying :
1) build a tower of height N-1 on tower2 (from tower1)
2) move the ring N from tower1 into tower3
3) build a tower of height N-1 (again) but this time on top of tower3 (from tower2)
that included building a tower of N-1 on tower2, but in the same logic, we can define building a tower of N-1 as :
1) build a tower of height N-2 on tower3 (from tower1)
2) move the ring N-1 from tower1 into tower2
3) build a tower of height N-2 (again) but this time on top of tower2 (from tower3)
and so on until we build a tower of 1. Now, can write the small little recursive function to solve the entire puzzle?
Hint : it has only 3 lines.
In the next post, we will see the code and we will also investigate why that it always take 2n - 1 steps to solve a Tower of Hanoi problem with N rings.
Challenge 1 : write the code to solve Towers of Hanoi puzzle for a given N.
Challenge 2 : in the above solving algorithm, prove that it always takes exactly 2n - 1 steps to solve the puzzle.
Bringing Down Towers of Hanoi - part1
Hope this post will not bring as much destruction as it's title suggests. In fact, we are not interested in bringing down any single tower in Hanoi, not even in any where else for that matter. What we would be doing is to brining down the problem of Towers of Hanoi into the levels we can understand it. Of course, if that was the title, we wouldn't probably be in here reading this right now would we ?
Towers of Hanoi is a popular puzzle, first introduced by the French mathematician Édouard Lucas in 1883. (However, some do maintain that the puzzle is much older than that) Those who are not familiar with the puzzle can learn all about it from here. There is a particular interest on this puzzle by the hacker (programmer, developer, coder) community mainly due to the fact that it has been taught in many 1st year CS courses throughout the world. The puzzle is a great example to demonstrate the power of recursion.
However, Towers of Hanoi is a deep enough problem that one can do it for a PhD. It could go many levels in depth and complexity. The most simplest version, I guess most of our readers have already studied in first year. Let's approach the problem step by step. If you are not a programmer and/or haven't done this problem before consider yourself lucky! you got an opportunity to have a fresh look at a very interesting problem and reap all the satisfaction of finding the solution on your own! Oh boy, this series gonna be a bit longer one....
Ready to jump in ? Ok, let's bring them down then!
Problem is to move all the rings from first tower into the third tower, one buy one. Here's the catch : you can not ever put a bigger ring on top of a smaller ring. That's why you have been provided with a middle tower, to transit.
Can you solve this your self ? of course you can. (animation at top of the page) All it need is some patience...
Now can we design a computer program to solve this. let's give it a try ....
Hint :
1) Solve it by hand for fewer number of rings and think recursively.
2) Consider three towers as three arrays. One has digits 0 to 9 in that order at start. At the end of the program execution, we need to have all digits in the 3rd array in the proper order.
We will see the answer to this basic version of the problem in the next article by the form of a peace of small, executable code. Remember, we would be upping the ante a bit in the next article and things would get more and more challenging and fun as we go on.....
So, do try it! give it a shot if you haven't already wrote a program to solve this by your self!
Sunday, February 20, 2011
Planet Wars - My First AI Contest (part 2)
First part of this post described how I missed the actual competition but still managed to have loads of fun and come up with my own bot thanks to nice people who have published their bots and made it possible for me to conduct a local tournament. Those who wondering what the Planet Wars is and what the big deal behind this so called AI competition, you can get up to date with all that from here.
In this post, I will mainly discuss the strategies and path I took when designing my bot and the lessons learned.
One of main lessons I learned from this experience is that the precious calculations are always way better than heuristic guesses. Sometimes when the problem is complicated, we tend to invent an obvious looking heuristic ("if my planet's ships are greater than enemy planet ships, attack the enemy with 50% of my strength" for instance) even though it may be the easier option, in the long run, investing our time on preciously calculating and picking our choice is always superior. It was particularly interested to note how heuristics disappeared from my algorithm and replaced by calculations as it was evolving.
Mainly I had 5 steps in my code :
1) Attack : if one or more of my planets can send ships to capture another planet even temporarily, do so. After considering all incoming fleets for the enemy planet, enemy growth over the attacking distance and possible reinforcements enemy can receive from it friends, (if those friends are nearer than my attacking planet that is), if it seems like I can capture the planet, I usually did so. My Planet will not hesitate to even attack with full strength if the enemy planet has a higher growth than itself, Otherwise it will use just the excess ships.
2) Defense : if one of my planets has incoming enemy fleets, I would assemble ships from my nearby planets and reinforce the planet which is under threat. Again all the incoming fleets, my own growth over the enemy attacking distance and reinforcements I can find were included in calculations. Nearby planets were given priority when selecting defenders.
3) Sniping : If an enemy is moving towards a neutral planet, I would try to reach there just after enemy has landed. That way enemy will do all the hard work of destroying the neutral defenders while I will have to fight only with it's depleted remaining forces.
4) Neutral planet hunting : if there are unoccupied planets which are nearer to me than to the enemy and if it is desirable (hear I used a heuristic) to take them, do so.
5) reinforcements : far away planets sending their ships to planets which are nearer to enemy planets.
Beside above, I tried to maintain a minimum force on planets which are nearby to enemy. Amount of that force was calculated by the attacking strength of the nearest enemy and defensive strength of my planets which were nearer to me than the enemy. Any excess above this limit was used in attacks. In defense, defenders trying their best to send enough ships to defend a planet by using their excess forces only.
Some bots were passing there chance on very first turn hoping for sniping chances on their second turn or in fear of being sniped themselves, I guess. I never liked that strategy. In initial moves, I took only the planets which are nearer to me than the enemy. In case of planets which fell in the middle, I chose not to attack them on the very first turn and to leave them for the enemy take, then I tried sniping on 2nd turn. This strategy gave me mixed results. When attacking a neutral planet or when doing a sniping, I did try to calculate the impact of "future planets" on them. That is planets which are not being claimed by either party but very soon will belong to one side. This could be easily deduced by the fleets in motion. Code would explain how this is done. I got few extra rating points after implementing this feature.
Another gray area for me was to decide whether I should change my behavior according to the game status. That is, should I attack less when I'm ahead in growth, should I attack more when I'm behind etc. Experiments on those always gave me mixed results. I eventually concluded that attack whenever it can be done with accuracy is best in most situations. This increased my score against stronger bots.
Few things I haven't implemented : Ideally the bot should compare advantages and disadvantages between an attack and defense. Should I let my planet fall and try to take that enemy planet etc... If I saw a sure attack I always took it and then tried to defend planets with available ships. It would have been cool to have a comparison though.
I gave lowest priority to attacking neutrals at the later stages of the game.
my functions to determine what is the minimum force to take an enemy planet and the minimum force required to defend an own planet was the same. It considered all fleets bound towards that planet, growth and reinforcements from friends. However I did not have any game tree and a mechanism to decide what if I do this, he do that and then I do this etc... I thought that sort of a min max tree approach is not so suitable for something like Planet Wars where problem space was huge and we had to come up with a move within a second. However, I have noted others talking about this any apparently getting some good results as well. I never tried that approach. If we are sensibly reinforced, well defended and always on the look for weaknesses of the enemy while being aggressive at the early stages on neutral hunting, I thought that will be good enough to be within first 100. may be I was correct in that, but then again that may also explain why my bot couldn't reach first 60, for instance.
One very interesting thing I noted was that even some of the stronger bots were not defending themselves properly at times. For instance, when in the opening where both parties have only one planet each, I managed to take the enemy by directly attacking it while it was busy sending fleets for neutrals. This was an easy check to do and guard against, yet most haven't done it and I scored few quick victories with that.
There are lot of finer details I like to discuss but that will grow this post to insane levels. Anyway the shared code should explain lot of things adequately. If anyone has questions/criticisms/suggestions, I would be glad to reply.
In this post, I will mainly discuss the strategies and path I took when designing my bot and the lessons learned.
One of main lessons I learned from this experience is that the precious calculations are always way better than heuristic guesses. Sometimes when the problem is complicated, we tend to invent an obvious looking heuristic ("if my planet's ships are greater than enemy planet ships, attack the enemy with 50% of my strength" for instance) even though it may be the easier option, in the long run, investing our time on preciously calculating and picking our choice is always superior. It was particularly interested to note how heuristics disappeared from my algorithm and replaced by calculations as it was evolving.
Mainly I had 5 steps in my code :
1) Attack : if one or more of my planets can send ships to capture another planet even temporarily, do so. After considering all incoming fleets for the enemy planet, enemy growth over the attacking distance and possible reinforcements enemy can receive from it friends, (if those friends are nearer than my attacking planet that is), if it seems like I can capture the planet, I usually did so. My Planet will not hesitate to even attack with full strength if the enemy planet has a higher growth than itself, Otherwise it will use just the excess ships.
2) Defense : if one of my planets has incoming enemy fleets, I would assemble ships from my nearby planets and reinforce the planet which is under threat. Again all the incoming fleets, my own growth over the enemy attacking distance and reinforcements I can find were included in calculations. Nearby planets were given priority when selecting defenders.
3) Sniping : If an enemy is moving towards a neutral planet, I would try to reach there just after enemy has landed. That way enemy will do all the hard work of destroying the neutral defenders while I will have to fight only with it's depleted remaining forces.
4) Neutral planet hunting : if there are unoccupied planets which are nearer to me than to the enemy and if it is desirable (hear I used a heuristic) to take them, do so.
5) reinforcements : far away planets sending their ships to planets which are nearer to enemy planets.
Beside above, I tried to maintain a minimum force on planets which are nearby to enemy. Amount of that force was calculated by the attacking strength of the nearest enemy and defensive strength of my planets which were nearer to me than the enemy. Any excess above this limit was used in attacks. In defense, defenders trying their best to send enough ships to defend a planet by using their excess forces only.
Some bots were passing there chance on very first turn hoping for sniping chances on their second turn or in fear of being sniped themselves, I guess. I never liked that strategy. In initial moves, I took only the planets which are nearer to me than the enemy. In case of planets which fell in the middle, I chose not to attack them on the very first turn and to leave them for the enemy take, then I tried sniping on 2nd turn. This strategy gave me mixed results. When attacking a neutral planet or when doing a sniping, I did try to calculate the impact of "future planets" on them. That is planets which are not being claimed by either party but very soon will belong to one side. This could be easily deduced by the fleets in motion. Code would explain how this is done. I got few extra rating points after implementing this feature.
Another gray area for me was to decide whether I should change my behavior according to the game status. That is, should I attack less when I'm ahead in growth, should I attack more when I'm behind etc. Experiments on those always gave me mixed results. I eventually concluded that attack whenever it can be done with accuracy is best in most situations. This increased my score against stronger bots.
Few things I haven't implemented : Ideally the bot should compare advantages and disadvantages between an attack and defense. Should I let my planet fall and try to take that enemy planet etc... If I saw a sure attack I always took it and then tried to defend planets with available ships. It would have been cool to have a comparison though.
I gave lowest priority to attacking neutrals at the later stages of the game.
my functions to determine what is the minimum force to take an enemy planet and the minimum force required to defend an own planet was the same. It considered all fleets bound towards that planet, growth and reinforcements from friends. However I did not have any game tree and a mechanism to decide what if I do this, he do that and then I do this etc... I thought that sort of a min max tree approach is not so suitable for something like Planet Wars where problem space was huge and we had to come up with a move within a second. However, I have noted others talking about this any apparently getting some good results as well. I never tried that approach. If we are sensibly reinforced, well defended and always on the look for weaknesses of the enemy while being aggressive at the early stages on neutral hunting, I thought that will be good enough to be within first 100. may be I was correct in that, but then again that may also explain why my bot couldn't reach first 60, for instance.
One very interesting thing I noted was that even some of the stronger bots were not defending themselves properly at times. For instance, when in the opening where both parties have only one planet each, I managed to take the enemy by directly attacking it while it was busy sending fleets for neutrals. This was an easy check to do and guard against, yet most haven't done it and I scored few quick victories with that.
There are lot of finer details I like to discuss but that will grow this post to insane levels. Anyway the shared code should explain lot of things adequately. If anyone has questions/criticisms/suggestions, I would be glad to reply.
Planet Wars - My First AI Contest (part 1)
I can't believe I wasted 2 months on this. I can't believe I comprehensively wasted 2 moths on this at all! (those who have red the blog of the winner, Bocsimacko The Brilliant, will find that phrase little familiar :-) )
It was late when I got to know about Google's AI contest. I have missed the first contest as well, I got to know about the second contest, "Planet Wars" just few days before it ended. Considering the competition was running for over 2 months, that didn't give me much chance to compete effectively. To make the matters even worse, I was to find out (foolishness of me, should have checked that out before everything else!) about the submission deadline just a day before it!
So I ended ended up hurriedly submitting not even the best code I have written in those few days. And the competition was of course a disaster for my Bot. May be I should have satisfied with the results (1200 out of 6000 competitors) of what was made in just 4 days, but something else happened during the final competition.....
I really began to get carried away by the beauty of the game, and the challenge it offered. I just continued development of my bot hoping that the competition server will keep running even after the official competition so that I could still evaluate my bot by playing it against others. Unfortunately, official server was never started after the actual competition. Can't blame the organizers for that. They have provided a wonderful experience and organized a hugely successful competition. What's more, they have made the server software open source. Few people were already running their own TCP servers where others could compete. However, after the competition, even the players seemed they are tired after a competition which ran for over 2 months, and no one was so keen on playing on TCP servers. Even the servers were not available after few days. At least all my attempts to connect to one was ended in failure.
My only remaining option was to download the bots published by others after the competition and play my bot against them in locally arranged tournaments. By this time my bot was improving fast and I was in a hurry to implement all my ideas and see how they would fair up against other bots. So I didn't look into downloaded code as that would influence my thoughts and I wouldn't be able to test my bot in a fair manner. A big big thank for those who published their code. I downloaded the java bots I came across, so my special thanks goes to GreenTea(ZerlingRush), Smloh, Manwe56, Deccan, Exaide, Eburnette, Ludakris, zvold(krokokrusa), InvaderZim. Without you guys it won't be possible for me to test my bot at all and you helped me to improve myself a lot. Looking forward to compete with you in a real tournament soon.
GreenTea was always a tough opponent for my bot, so was Smloh1. At initial stages almost all bots were very difficult to beat. I implemented features one after other, attack first, defense, neutral planet hunting etc and things improved dramatically. specially after proper defense and optimized neutral hunting. As for attacking, less attacking the better it was top bots were very quick to punish incorrect attacks. I thought Ludakris was a better bot than it's rating suggested, specially in close quarter battles. Manwe56 was little slower than other bots for some reason but was stronger than my one in most cases. Exaide has a random behavior as it was getting different results against the same bot on same map! it was a mysterious bot for me in the beginning. I felt I was bit luckier against Mkemp, zvold and eburnette and may be bit unlucky against Deccan whom I couldn't reach on ratings even though individual matches against that bot went close. Smloh1 was slow initially until I had to investigate and eliminate system.outs from the code :-)
It took about 2 months before this craziness ended and I had enough improving my very first AI bot. If the competitions I locally arranged is to be trusted and ELO tables do a good job in measuring performances and translating them into ratings, then I think I could be somewhat satisfied with my efforts. My final bot performed around 3280, (it got very close ratings in 2 different sets of maps against same opponents, so I guess the performance rating calculation is fairly accurate) which would mean had it managed to compete in the real competition, it may (arguably) have ranked somewhere between 60 - 70. I may have got an advantage since I have few good bots at hand to test my bot against with, but then again in the real tournament preparation, competitors may have had the privilege of playing against others on TCP servers as well as in the live server.
I didn't do fine tunings targeting the final tournament maps since my interest in the game dried down after solving the challenge of implementing all my game strategies and getting them to work. Some fine tuning would have helped to snatch up few more rating points... but my main interest was to get the algorithms right.
Now that the initial goal is achieved (to build a decent bot on my own), I can now go visit others code and analysis, learn something new and have a laugh at clumsier ways I may have achieved certain things in my code.
Source code of the final bot can be found in here. Excel with all tournament statistics and rating calculations along with ELO tables used is also there. I'm planning to explain my code, strategies and lessons learned in a future article if the time permits. Meanwhile, apologies if the code lacks enough comments.
All the best for all contestants in the upcoming contest! those who haven't get involved in this fun, do sign up!! trust me, you won't be regretting this. (specially if you like AI programming and/or problem solving in general)
Part 2
It was late when I got to know about Google's AI contest. I have missed the first contest as well, I got to know about the second contest, "Planet Wars" just few days before it ended. Considering the competition was running for over 2 months, that didn't give me much chance to compete effectively. To make the matters even worse, I was to find out (foolishness of me, should have checked that out before everything else!) about the submission deadline just a day before it!
So I ended ended up hurriedly submitting not even the best code I have written in those few days. And the competition was of course a disaster for my Bot. May be I should have satisfied with the results (1200 out of 6000 competitors) of what was made in just 4 days, but something else happened during the final competition.....
I really began to get carried away by the beauty of the game, and the challenge it offered. I just continued development of my bot hoping that the competition server will keep running even after the official competition so that I could still evaluate my bot by playing it against others. Unfortunately, official server was never started after the actual competition. Can't blame the organizers for that. They have provided a wonderful experience and organized a hugely successful competition. What's more, they have made the server software open source. Few people were already running their own TCP servers where others could compete. However, after the competition, even the players seemed they are tired after a competition which ran for over 2 months, and no one was so keen on playing on TCP servers. Even the servers were not available after few days. At least all my attempts to connect to one was ended in failure.
My only remaining option was to download the bots published by others after the competition and play my bot against them in locally arranged tournaments. By this time my bot was improving fast and I was in a hurry to implement all my ideas and see how they would fair up against other bots. So I didn't look into downloaded code as that would influence my thoughts and I wouldn't be able to test my bot in a fair manner. A big big thank for those who published their code. I downloaded the java bots I came across, so my special thanks goes to GreenTea(ZerlingRush), Smloh, Manwe56, Deccan, Exaide, Eburnette, Ludakris, zvold(krokokrusa), InvaderZim. Without you guys it won't be possible for me to test my bot at all and you helped me to improve myself a lot. Looking forward to compete with you in a real tournament soon.
GreenTea was always a tough opponent for my bot, so was Smloh1. At initial stages almost all bots were very difficult to beat. I implemented features one after other, attack first, defense, neutral planet hunting etc and things improved dramatically. specially after proper defense and optimized neutral hunting. As for attacking, less attacking the better it was top bots were very quick to punish incorrect attacks. I thought Ludakris was a better bot than it's rating suggested, specially in close quarter battles. Manwe56 was little slower than other bots for some reason but was stronger than my one in most cases. Exaide has a random behavior as it was getting different results against the same bot on same map! it was a mysterious bot for me in the beginning. I felt I was bit luckier against Mkemp, zvold and eburnette and may be bit unlucky against Deccan whom I couldn't reach on ratings even though individual matches against that bot went close. Smloh1 was slow initially until I had to investigate and eliminate system.outs from the code :-)
It took about 2 months before this craziness ended and I had enough improving my very first AI bot. If the competitions I locally arranged is to be trusted and ELO tables do a good job in measuring performances and translating them into ratings, then I think I could be somewhat satisfied with my efforts. My final bot performed around 3280, (it got very close ratings in 2 different sets of maps against same opponents, so I guess the performance rating calculation is fairly accurate) which would mean had it managed to compete in the real competition, it may (arguably) have ranked somewhere between 60 - 70. I may have got an advantage since I have few good bots at hand to test my bot against with, but then again in the real tournament preparation, competitors may have had the privilege of playing against others on TCP servers as well as in the live server.
I didn't do fine tunings targeting the final tournament maps since my interest in the game dried down after solving the challenge of implementing all my game strategies and getting them to work. Some fine tuning would have helped to snatch up few more rating points... but my main interest was to get the algorithms right.
Now that the initial goal is achieved (to build a decent bot on my own), I can now go visit others code and analysis, learn something new and have a laugh at clumsier ways I may have achieved certain things in my code.
Source code of the final bot can be found in here. Excel with all tournament statistics and rating calculations along with ELO tables used is also there. I'm planning to explain my code, strategies and lessons learned in a future article if the time permits. Meanwhile, apologies if the code lacks enough comments.
All the best for all contestants in the upcoming contest! those who haven't get involved in this fun, do sign up!! trust me, you won't be regretting this. (specially if you like AI programming and/or problem solving in general)
Part 2
Friday, February 18, 2011
Welcome !!
Welcome to our blog!
Here we will discuss and analyze the use of artificial intelligence in gaming, Game Theory, IQ enhancing games and puzzles, AI algorithms used in them etc...
Creating games for PC and smart phones (iphone, android, windows mobile) is our hobby. We intend to share our experience and passion with our readers.
Stay tuned for up coming articles on :
Planet Wars (ai contest from Google) and our experience.
Towers of Hanoi : this is covered in many 1st year CS courses on AI. Here we intend to go little deeper, one step at a time ..
MasterMind : The classic board game.
Dual : An addictive yet simple board and puzzle game developed as a new and own concept.
15 Puzzle : you know it! most simplest of board games out there. or is it ?
and many more.....
If you have interesting thoughts, ideas games and algorithms to share, you are welcome to comment in here.
Here we will discuss and analyze the use of artificial intelligence in gaming, Game Theory, IQ enhancing games and puzzles, AI algorithms used in them etc...
Creating games for PC and smart phones (iphone, android, windows mobile) is our hobby. We intend to share our experience and passion with our readers.
Stay tuned for up coming articles on :
Planet Wars (ai contest from Google) and our experience.
Towers of Hanoi : this is covered in many 1st year CS courses on AI. Here we intend to go little deeper, one step at a time ..
MasterMind : The classic board game.
Dual : An addictive yet simple board and puzzle game developed as a new and own concept.
15 Puzzle : you know it! most simplest of board games out there. or is it ?
and many more.....
If you have interesting thoughts, ideas games and algorithms to share, you are welcome to comment in here.
Subscribe to:
Posts (Atom)