Monday, May 5, 2008

AI The Third

The "expert" level of the Artificial Intelligence is ready (still to be debugged). The main algorithm is the same as the "intermediate" level. Calculate all the possible moves, evaluate the resulting position and make the move with the best ranking.

The main difference is the evaluation routine which in this case consider many other things like the position where men are hit, the possibility of getting hit when leaving a bloat, the special scenario in which there's no more contact possible, etc.

I'm very happy of the way this is working because it could lead to great improvements in the quality of the artificial intelligence. Also because this algorithm could be applied to other games if I get it to consider several plies instead of just one. Of course this is not a simple thing, but hey, you have to start by the basics.

Thursday, February 7, 2008

Finally, some steps towards Internet Marketing

When I started this blog, I suggested I would explain how to market the end product online, but I also left clear I had no idea how to do that. Well, I've finally accomplished the first steps related to the marketing part. I still have a lot to learn regarding the subject, so if anyone is reading this blog and has some ideas I would love to hear them.

So, how do we manage to sell anything online? There are several different options and all of them can happen at the same time, but one of the more attractive way I've found is through Affiliate Marketing. I came around a website called clickbank.com (OK, OK, I don't need to know everbody knows that site since last century, I just found it). The main idea of Affiliate Marketing is: 1) You develop a product and create a basic website promoting it and with a few specific features that "link" it to a third pary that's going to charge the customer and transfer the money to you; 2) You register yourself with that third pary, register your product in it and let it know the address of your "sales page"; 3) Some affiliates registerd with that third pary find your product intersting and create websites, articles, post advertising and so on making people go to your sales page; 4) When the customer purchases your product, a special tracking mecanism from the third pary determines the affiliate that drove the customer to your site and pays him a commission on your behalf. Of course it also takes a commission for itself and then pays you what's left.

Obviously, in this case that third party is clickbank. Which by the way is absolutely free, so you don't have to spend a dime before really starting to sell. They'll only charge commissions after the sales and after issuing the payments twice a month (If you've sold anything at all :p).

The Second AI Level... waaaaay better !

All right, I'm kind of excited because what I thought would be very difficult ended up being kind of piece of cake. The first level of AI was so stupid because it merely looked for the first valid move and that's it. The second level, which is almost finished except for a little bug fixing, is far better in concept.

First, it creates an array of all the possible "combination of moves". With just this part of the definition it has two great advantages over the first level: considering all the possible moves and combining the moves allowed by each of the dice. This includes the possibility of moving the same man several times.

But what would be the objective of having a list of possible moves if you're not going to "choose" the best of them. So the second part of the implementation is a "position evaluator". This is what makes me feel like I'm on the right track. Why? because all the implementations of chess engines have an algorithm that evaluates which one is the best among a list of valid moves.

What does the position evaluator take into account? Well, so far, as positive for the rank, it considers the number of home board points that are blocked, the distance from the isolated men to the opponent's men, the advanced your men are, etc. on the negative side, the number of isolated men, the points with more than 5 men, etc.

So it's unbeatable? ... I wouldn't say so. In fact, I would say it still plays fairly bad if you compare it to an experienced human player, but it will definitely have better odds than the first level. Specially if it has just a little luck. Besides, I had to leave room for the third and final AI level.

Friday, December 7, 2007

My first AI... Very "A", not "I" at all

My first Artificial Intelligence ever is ready, I don't think it qualifies as an AI since it doesn't learn, it's just a very basic "move evaluation and selection algorithm", but aren't chess engines the same thing??? Of course !!! you don't install your newly acquired ChessMaster and then "train" it submitting hundreds of thousands of highly selected games so it learns what is a good move and what is not.

Why do we use the term Artificial Intelligence? I have not clue, so I thought, should I use "human vs phone" instead? I'm still thinking about it, but for the time being, I'm going with the flow of the industry and I have labeled it AI.

What's even worst, as can be seen from the following code, my move evaluation and selection algorithm is not even that :(. It doesn't "evaluate" the possible moves and then "select" the best option. It just finds the first possible valid move and does it. It's very gratifying to watch the game answer your moves though. Even if the moves it does are absolutely dumb. I hope I can proudly label AI the second level when it's done, the first level should be labeled Artificial Stupidity...


public byte[][] getMoves(Board board)
{
byte moves[][] = new byte[board.getAvailableMovesCount()][2];
super.cloneBoard(board);
int currentMove = 0;
for(int i = 0; i <>
{
if(super.availMoves[i] != 0)
System.out.print(super.availMoves[i] + " ");
System.out.println();
}

label0:
do
{
if(currentMove <>
{
if(super.barCount[board.getTurn() - 1] > 0)
{
for(int i = 0; i <>
{
if(super.availMoves[i] == 0)
continue;
int point = board.getTurn() != 2 ? 24 - super.availMoves[i] : super.availMoves[i] - 1;
if(super.boardColor[point] == board.getOpponent() && super.boardCount[point] >= 2)
continue;
moves[currentMove][0] = -1;
moves[currentMove][1] = (byte)point;
System.out.println("moving from " + moves[currentMove][0] + " to " + moves[currentMove][1]);
super.barCount[board.getTurn() - 1]--;
if(super.boardColor[point] != board.getTurn())
super.boardCount[point] = 1;
else
super.boardCount[point]++;
super.boardColor[point] = board.getTurn();
currentMove++;
super.availMoves[i] = 0;
continue label0;
}

return moves;
}
int j;
if(board.playerCanBearOff())
label1:
for(j = 6; j > 0; j--)
{
int point = board.getTurn() != 2 ? j - 1 : 24 - j;
if(super.boardColor[point] != board.getTurn())
continue;
int i = 0;
do
{
if(i >= 4)
continue label1;
if(super.availMoves[i] > j)
{
moves[currentMove][0] = (byte)point;
Board _tmp = board;
moves[currentMove][1] = -2;
super.boardCount[point]--;
if(super.boardCount[point] == 0)
super.boardColor[point] = 0;
currentMove++;
super.availMoves[i] = 0;
continue label0;
}
i++;
} while(true);
}

j = board.getTurn() != 2 ? 23 : 0;
do
{
if(board.getTurn() != 2 ? j <>= 24)
continue label0;
if(super.boardColor[j] == board.getTurn())
{
for(int i = 0; i <>
{
if(super.availMoves[i] == 0)
continue;
int point = board.getTurn() != 2 ? j - super.availMoves[i] : j + super.availMoves[i];
if(point <>= 24 super.boardColor[point] == board.getOpponent() && super.boardCount[point] >= 2)
continue;
moves[currentMove][0] = (byte)j;
moves[currentMove][1] = (byte)point;
System.out.println("moving from " + moves[currentMove][0] + " to " + moves[currentMove][1]);
super.boardCount[j]--;
if(super.boardCount[j] == 0)
super.boardColor[j] = 0;
if(super.boardColor[point] == board.getOpponent())
super.boardCount[point] = 1;
else
super.boardCount[point]++;
super.boardColor[point] = board.getTurn();
currentMove++;
super.availMoves[i] = 0;
continue label0;
}

}
j += board.getTurn() != 2 ? -1 : 1;
} while(true);
}
return moves;
} while(true);
}


P.D.: Even though the first level of the AI is absolutely stupid, it has managed to beat a couple of friends once or twice. Obviously they hadn't played the game before. So the skill level is not that inappropriate after all.

The importance of beta testing

Of course you can test your program yourself, you run it a thousand times when you're developing it testing small pieces of the code. But when you want to develop a first-class program without spending a lot of money, you need to ask some friends for their help in this annoying but very important task.

It doesn't matter if you offer them a free copy of the final release, a couple beers, a free dinner (specially good idea if the beta tester in question is a girl you like), you will always find at least half a dozen friends willing to test your game. This will allow you to have different points of view regarding certain features and will expose your program to different environments. In this case, testing your mobile game against different phones is very important because they all use different screen resolutions and keyboard mappings.

As of today, I haven't really figured out the best way to tackle those two problems: screen resolution and keyboard mappings.

For the first one, I've made everything that's drawn in the screen adjust to a ratio of the total screen resolution, but that's more difficult when it comes to stored graphics because you need to choose a different image file depending on the resolution. It has come to my mind that I could make a "screen definition" file format that defines which image files to use and where to put them in the screen. It could also define font styles and sizes, colors and so on. This would not only make it very easy to setup a new screen resolution for a newly marketed mobile device but would also make the game "skinable", which would make a great feature altogether.

About the keyboard mappings, I also think I should make a "keyboard configuration" option. That way, the user itself could choose what keys he wants to use for every action and the game would work with every possible device.

As a proof of concept, and also to figure out the keyboard mappings of the phones a couple friends use, I developed a small Midlet that gives feedback of the keys as the user presses them. This is the code of the Canvas that does it all:

import javax.microedition.lcdui.*;
import javax.microedition.lcdui.game.*;
import java.io.IOException;
import java.io.InputStream;

class KeyTestCanvas extends Canvas {

private int lastKeyCode;

public KeyTestCanvas(){
}

protected void paint(Graphics g){
int w = getWidth();
int h = getHeight();
g.setColor(0x000000);
g.fillRect(0, 0, w, h);
g.setColor(0xFFFFFF);
g.drawString("keyCode:", 10,10,Graphics.TOP|Graphics.LEFT);
g.drawString(Integer.toString(lastKeyCode), 80,10,Graphics.TOP|Graphics.LEFT);
g.drawString("GameAction:", 10,30,Graphics.TOP|Graphics.LEFT);
try {
g.drawString(Integer.toString(getGameAction(lastKeyCode)), 80,30,Graphics.TOP|Graphics.LEFT);
} catch (Exception e) {
g.drawString("Exception", 80,30,Graphics.TOP|Graphics.LEFT);
}
g.drawString("KeyName:", 10,50,Graphics.TOP|Graphics.LEFT);
try {
g.drawString(getKeyName(lastKeyCode), 80,50,Graphics.TOP|Graphics.LEFT);
} catch (Exception e) {
g.drawString("Exception", 80,50,Graphics.TOP|Graphics.LEFT);
}
}

protected void keyPressed(int keyCode){
lastKeyCode = keyCode;
repaint();
}

}