Archive for the 'Programming' Category

Automate Rapidshare free downloads - No more captchas

Monday, July 14th, 2008

Earlier this month the popular file sharing service Rapidshare decided to drop the use of captcha’s. This came as a huge surprise to myself because previously Rapidshare has used some of the most convaluded captcha puzzles ever! At points I would be Lucky to get 25% of captures used by Rapidshare right.

Dropping the use of captcha’s has paved the way for automated downloads but Rapidshare are aware of this and has lowered the download speed of free users to 500 kilobit per second.

Never less I would rather the lower speed and with the capability to have the damn thing automated. So here it is, my simple bash script to download a batch of files of Rapidshare. Hell if you only want to download 1 file its only a “one” linner.

URL=$(curl -s <URL TO RAPIDSHARE FILE>| grep "<form id=\"ff\" action=\"" | grep -o ‘http://[^"]*rar’);ourfile=$(curl -s -d "dl.start=Free" "$URL" | grep "document.dlf.action=" | grep -o ‘http://[^"]*rar’ | head -n 1); sleep 90;wget $ourfile;

Full version to download a batch of files specified in a file called input.txt, 1 file per line.

New Version (1/11/2008): Rapidshare has added a wait time in between file downloads. On top of your download
to start. This has been fixed.

Download the full .sh with some enhancments made by Tune. Also see comments for a Python version by Conman.

Download Itay’s version with some nice features. See his comment for the features.

while read line
do

URL=$(curl -s $line | grep "<form id=\"ff\" action=\"" | grep -o ‘http://[^"]*rar’);
ourfile=$(curl -s -d "dl.start=Free" "$URL" | grep "document.dlf.action=" | grep -o ‘http://[^"]*rar’ | head -n 1);
sleep 90; #70 secs for 200mb 50 secs for 90mb
wget $ourfile;

done < input.txt

Analysis

while read line
do
Code……………..
done < input.txt

Loop through all lines in the file input.txt, store each line in a variable called ‘line’, move to the next line.

URL=$(curl -s $line | grep "<form id=\"ff\" action=\"" | grep -o ‘http://[^"]*rar’);

Use curl to ‘download’ the page of the url we are processing. Pipe the downloaded pages source code through some greps to extract the action URL of the html form which we need to ’submit’ to trigger the download. Store this url in a variable called ‘URL’.

ourfile=$(curl -s -d "dl.start=Free" "$URL" | grep "document.dlf.action=" | grep -o ‘http://[^"]*rar’ | head -n 1);

Using curl again, ’submit’ a html form to our extracted URL, passing it the post data (-d switch in curl) of being a free user. Rapidshare then replies with a new page with a list of Rapidshare servers to download from, they are stored in lines of Javascript starting with ‘document.dlf.action=’. After the equal sign is the direct url to our file, so lets grab this with another grep!

We are now have a list all the Rapidshare servers holding our file like this.

http://rs202l3.rapidshare.com/files/50141870/1554876/centos-5.0.tar.part01.rar
http://rs202l33.rapidshare.com/files/50141870/1554876/centos-5.0.tar.part01.rar
http://rs202tl3.rapidshare.com/files/50141870/1554876/centos-5.0.tar.part01.rar
http://rs202cg.rapidshare.com/files/50141870/1554876/centos-5.0.tar.part01.rar
http://rs202l32.rapidshare.com/files/50141870/1554876/centos-5.0.tar.part01.rar
etc…..

We will try our luck with the first one, so filter this output through ‘head’ telling it to extract one line (head -n 1)

sleep 90;

Rapidshare still makes us wait for our file! So, we will just wait here for however long it takes which is 70 secs for a 200mb (new file size limit) 50 secs for 90mb (old file size limit).

wget $ourfile;

Finally the wait is over, luckily its the script doing the waiting, not us. Lets get our file. wget our file that is…

Closing comments, if you know how to improve the script please let me know. At the moment it will only work with .rar files though you could easily change this. A generic version would be nice but this is what most files are in on RS.

A version which uses proxys to download files in parallel would be good.

I dont like piping a grep command into a grep command so I’m sure this could be done with just one grep.

I use use both wget and curl, which here accentually do the same job, if you have one or the other you can fix the script up to only use either.

Tip: Set your batch download up an in a screen session and detach it so you can ssh in and monitor your downloads where ever you go. This will also let your downloads continue downloading when you close your terminal window or putty sesion.

Programs needed: Bash (duh!), head, grep, sleep and curl or wget

Note: I have required to increase the sleep time to 90 seconds. I am unsure how to calculate this time because it has seemed to change from when I first wrote this. It may well be RS has increased the time or the value is variable depending on how much you have previously downloaded. So 90 seconds seems like a safe value for now.

Gemapis - Milestone 1 tech demo

Wednesday, May 28th, 2008

This project was started over a year ago, though 95% of the work has been done in the last few weekends (to be honest it seems like I spent more time on the video and blog post then on it itself).

Gemapis is a map/tile editor for 2D tile based games such as RPG’s and Platformer’s. Typically it will be used for games resembling the graphics of SNES or Sega Megadrive (Genisis) era of games.

 I have released a video showing off Gemapis’s features which were todo’s in milestone one which is now complete.  Theres a few big things to do in milestone two before a first release.

 

Features you saw in the video include:  

  • Tile layers
  • Tile transparency
  • Tile rotation
  • Tile mirroring
  • Group tile selection
  • Saving the tile data and reloading it
  • Saving map data into a binary format which will be able to be read by many systems and programming languages.

Features I will/would like to include:

  • Undo/Redo of map edits
  • Nice user interface
  • Polygon hit detection (expressed in XML)
  • Map entity specifications Eg, Sprites, NPC’s, Events etc (expressed in XML)

Like I said in the video. If your interested in helping let me know; you will get SVN access (like with most of my projects).  I ask for help because I cant be good at everything ;)

Gemapis will be open source software.

 In the tech video/demo for milestone 2 you will see a C++ game using a map created in Gemapis and hopefully using all the features described above.

High resolution video can be found here.

 

Your-V-Lyrics

Saturday, May 3rd, 2008

Heres a Web 2.0 mashup I made in a few hours in PHP. 

The idea of Your-V-Lyrics is to search for a artist and a song so you can watch/listen to the video clip as well follow the lyrics next to the video.

So far it works quite well. Especially for music videos where the director really embraces the lyrics and theme of the song.

 Try it out!. Here are some of my favourite music videos

Deftones - Change

System of a down - Arials

Tool - Schism

Metallica - Frantic

Rammstein - Ich will

Incase you wanted to know, videos are from youtube.com and lyrics from lyricwiki.org

Status update

Saturday, March 1st, 2008

It’s been a while between blog posts partly because I’ve been busy; partly because I have been lazy.

I will discuses 3 topics here so if one doesn’t interest you don’t read it.

Firstly I want to talk about my new laptop and Windows Vista.
My old Compaq P3 laptop died a few months back (closer to a year back) I was surprised how much mistreatment it actually survived through but it eventually chocked with my wrong doing so I its death is on my shoulders.
Ever after that tragic day I have been looking for a new one, even my pc was getting close to being due for an upgrade with slower compile times, Flash videos using nearly 100% CPU and barely only being able to play 4 year old games at low frames.

So I bought a Asus M51SN, the version I purchased has a Core Duo 2.5Ghz CPU 6MB cache(L2), 2 GB ram, 200GB HDD, 512MB 9500M GS GFX (Geforce 9), TV Tuner and Vista Ultimate. It also came with a free wireless router.
The hardware is very capable and the CPU and GFX architecture were only released last month.

Setting up my free Asus wireless router was kind of tricky. It came with very basic lame instructions which required you to run a setup cd on Windows and press a button on the device to put it into a ‘find me setup’ mode. I can see why there is so many un-secured wireless networks when these things are designed to be easy to setup but this makes them defautly un-secure.

Using some assumptions and guessing I was able to setup the router the right way without having to use the crappy 2 step instructions in the manual. Knowing that routers by default have the class C IP address of 192.168.1.1 I was able to hit the router setup page from my browser. After a few attempts I was then able to guess the default administrator username and password (which was ‘admin’ and ‘admin’) and login to configure the wireless encryption password and some other junk. The default username and password wasn’t even documented in the manual.

I was having some initial problems accessing the rest of the network and the internet because the setup was….
MyWirelesssRouter—-MainRouter—-Internet/RestOfHomeNetwork

After trying allot of settings I realised its probably because MyWirelesssRouter and MainRouter probably have the same IP address. This was the case, upon changing MyWirelesssRouter’s IP from 192.168.1.1 everything worked. The thing I hate about networking compared to programming is that there is no debug mode. You usually have to use some kind of logic to work your problems out. Obviously things like ping, traceroute and nmap work in allot of situations but not all.

The most surprising thing about my laptop is I actually like Vista. This may be because I had such low expectations with everything I had heard. From a general users point of view I would say it’s better than XP! From an technical point of view I will tell you it’s memory foot print is allot larger and its install size is fucking huge. Vista Ultimate also comes with Windows media Center which I really like also.
Speaking of Media Center, At the moment I’m Writing this in Word 2007 (which at the moment my opinion is simply ‘its different’ ) while watching Gyroscope on JTV on ABC2. Which I can pause and rewind. Im also told ABC2 has Red Dwarf which I can’t wait to watch also.

The only 2 issues I have run across so far is there is no port of Nvidias Nview application for Vista which isn’t MS’s fault. The other main issue is there is a bug where my DVD drive will stop working some times. Once I reboot all is fine with it.

The main thing I don’t like about Vista is well… its Windows :p

Need antivirus, endless OS updates, proprietary, inferior kernel design and basically everything else detailed in the OS comparison section of Eric Raymond’s book ‘The Art of Unix programming’

Next Im going to talk about a bug that I came across on code I maintain but didn’t write.

The bug only ever happens on one day every 4 years. Yes that’s right it’s a leap year bug! The code was essentially doing age validation, it would take the current day, month and year then minus x amount of years from the current year. It would then check to see if your age was less than the max age limit (current date – x years).

Well you see the date on this particular day was the 29th of February 2008 (last Friday).
So the code was something like

DateTime.parse(29,02,2008 - x);

Where x is 2. The problem is 29th of February 2006 (2008-2) doesn’t exist! So when it goes to parse the date it throws an invalid date exception! Making problems even worse is this genius of a programmer put this code in a try catch block and would handle the exception of a invalid date with the error message along the lines off ‘you are too old’ which was also the error you got if in fact you were to old.

This is only one error which plagues the whole project. How could of this been easily avoided? Use the DateTime library to do the hard work, library writers are always nearly 1000 times smarter than you and their code has been tested that many times better also. A much more logical way to write this would have been

DateTime.parse(29,02, 2008).minusYears(2);

Lessons to learn: Do not use incorrect error messages and generic exceptions, use library’s when they are available and most importantly from my quotes page ’Always program as if the person who will be maintaining your program is a violent psychopath that knows where you live’

Finally, A quick review on games I’ve been playing.

Hitman Blood money PC, nice graphics and physic. Doesn’t really bring much new to the game play from the previous Hitman titles.

Pokemon Perl (DS), Dosnt offer much new game play from previous Pokemon games, graphics are quite bad for a DS game, allot of the sound is still taken from the original gameboy game, doesn’t make use of touch pad much. I look forward to playing it online though.

Final Fantasy 3 remake (DS), great game in all aspects. Starts of a little slow but gets allot better. Only downside is it lacks mini games which would have been made so totally awesome with the features of DS (duel screen, touch pad and microphone).

Netsend!

Wednesday, December 26th, 2007

I just want to talk about a small application Ive been working on and a few other things.

For very small periods on and off over the last 6 months I have been working an application I am calling netsend. Netsend is / will be a networking tool with the main aim of sending a file across a network peer to peer. Weather is be across a LAN or the internet.

Netsend is person to person. Peer to peer (single peer). The Idea is simple, I want to send Mr-x a picture of a purple monkey. I simply run netsend. Mr-x connects and the transfer starts. After the transfer is complete both programs on mine and Mr-x machines end. In contrast it will also be able to compress a bunch of pictures of purple monkeys, encrypt them and send them to a backup server every night.

Yes I know theres FTP, secure copy, chat protocol x or some other similar application.

But netsend differs in that its not a service like FTP, its only function is to successfully copying 1 file at a time. Its not designed just for humans sending files like with chat clients (although you can get a interactive command line). It can be 100% automated. It will be 100% open source and multi platform.

The idea of netsend is like any good OS/Networking tool which allot of the unix paradigm is designed around. Make it do one job and do it well, use IPC (Inter Process Communication) and use standard Input and Output to make it generic. Also lots of options and features helps also but no feature creep.
At the moment its features are short and platforms are limited.

  • Percentage completion status bar
  • File resume
  • Windows 32

Here are some screen shots with a transfer through the loopback network.
But I have had the exact same success across the internet and a LAN.

First screen capture is of a transfer taking place. 2nd is of an md5 checksum of the original file and then of the sent file. The checksum is the same, the transfer went 100%

Netsend p2p network transfer Netsend p2p network transfer
If you are interested in trying a very very early release of netsend download it here. Sorry Im working on getting it ported to more systems (Linux is next). Note the executable is pretty large because it hasn’t been stripped of debugging information or optimized. Netsend will be designed to be light weight and require very few external library’s.

The next feature I want to add is specifying a range or single IP which can make a connection.

The other thing I wanted to talk about was Microsoft’s File Checksum Integrity Verifier.

Seems like a pretty good free command line utility to check that byte by byte bit by bit two files are the same. You can generate checksums in MD5 or SHA1. I will be keeping this handy.

Your programmer personality type

Saturday, November 17th, 2007

Very long time between posts. Ive been really busy.

Just a quite post about a interesting online programmer personality test I found. My results can be found below.
Your programmer personality type is:

DLSB

You’re a Doer.
You are very quick at getting tasks done. You believe the outcome is the most important part of a task and the faster you can reach that outcome the better. After all, time is money.

You like coding at a Low level.
You’re from the old school of programming and believe that you should have an intimate relationship with the computer. You don’t mind juggling registers around and spending hours getting a 5% performance increase in an algorithm.

You work best in a Solo situation.
The best way to program is by yourself. There’s no communication problems, you know every part of the code allowing you to write the best programs possible.

You are a liBeral programmer.
Programming is a complex task and you should use white space and comments as freely as possible to help simplify the task. We’re not writing on paper anymore so we can take up as much room as we need.

Just some quick thoughts on my results - Seems Im a Doer rather than a Planner. This is probably true in some essence. I wont plan small to medium projects but this is probably because im a Solo programmer rather than a Team programmer so I know in my head how I want something to be done anyway. Though I do believe on large projects with a large team just like testing you can never do enough planning.

I think Im a Solo programmer because I program to get away from people. The computer does what I say. No questions. If things screw up its my fault. Stupid people who needs em… I find programming in a Team is only good if its a really tight team. Though im really all for concepts like Open Source.

Seems Im a Low level programmer. I tend to disagree with this. I will more likely only go to a low level language when the problem requires/suits it though I am more likely to choose JAVA or .net. It does annoy me how much JAVA and VB do abstract you from the hardware sometimes you just want to do pointer arithmetic or make use of unsigned data types. C# is a bit better that VB or JAVA in that respect.

It probably thinks Im Low level because I answered ‘Allow me to make use of system resources’ in the following question.

The ‘perfect’ language will:

I answered this because I dont think a language that allows anyone to program is practical. Computers are complex and I wish people would stop pretending otherwise. Languages like JAVA are THAT EASY that anyone who passed high school maths should be able to do simple programming tasks in it now anyway.

Well, thats all for now. See you all in a few months.

ABreakoutC - Another break out clone

Sunday, August 26th, 2007

Today I have finished the first release of a Breakout clone I have been working on for PC (Linux / Windows / PC).

If you dont know what Breakout is; it was one of the first arcade games ever made. It involves hitting a ball at blocks using a paddle which you can move left and right. Breaking all the blocks progresses you to the next level. Like latter versions of breakout, ABreakoutC includes power-ups which add special effects to the game.

ABreakoutC was my first game written in c++ using SDL which is a cross platform game/media library.

It and its source are released under the GPL3 and the graphics were made in entirely in GIMP.

The game was developed in Linux with the help of the Netbeans (best IDE in the world) c++ plugin.

Game Objects

abreakoutcitems.png

Controls

Pause/Resume - P
Start the ball moving - Space bar
Move paddle - Left key, right key

Screen shots

abreakoutc1.png abreakoutc2.png abreakoutc3.png

Downloads

Windows
x86Linux-32
Source

System requirments

1Ghz or better Celeron. 128 Meg or ram.
Note - You cant go higher than 60fps

If you want to design your own levels (let me know and I will talk you through it), provide music to the game or even add a power-up your welcome to. Getting a few people working on this would be great. Also I would like someone to do a Visual c++ build as mine is only MinGW.

———Update!———

If you have previous downloaded any version of the game please get version 002 (from the above locations) there was a bug which will cause what seems like a random crash on Windows which is now fixed.

For those that are interested it was a memory violation caused by…
if(ds[i]->blockDestroySprite1->status == Sprite::FINISHED){
delete ds[i]->blockDestroySprite1;
ds.erase(ds.begin() + i);
}

gs->apply_surface(ds[i]->location_X,ds[i]->location_Y,
ds[i]->blockDestroySprite1->spritesheet,ds[i]->blockDestroySprite1->getFrame());

As you can see I was deleting the sprite then trying to draw the sprite on certain instances. I have no idea why this error didnt occur on Linux (where I did all of my testing). I have now fixed all versions to delete the sprite after it is drawn.

Game Artificial Intelligence using the Minimax Algorithm

Saturday, June 9th, 2007

Version 1.0

Prerequisite knowledge

Obviously you must know how to program in the chosen language.
How stack and heap memory work for your language (if it has it).
Recursion.

Helpful knowledge

How to debug your code and view the call stack.
By reference and by value parameters.
CSharp / JAVA

Whats next (Part 2 - Increasing performance)

Using a code profiler to tweak the algorithm and your code.
Alpha-beta pruning to increase search time.

Introduction

This tutorial will show the reader through explanations and code examples how to implement the Minimax Algorithm for Artificial Intelligence for the turn based computer game of their choice.

Before we begin I suggest the reader takes a look at the Minimax wiki artical
to understand some of the concepts involved with this algorithm which I will be talking about.

It doesn’t matter if you don’t understand much on that article yet (I didn’t until I worked on this).

Also I suggest you get some experience programming and debugging recursion before you try to implement Minimax into the game of your choice.

Level of difficulty: Hard to learn at first, but easy to do once understood.

Examples are done in Csharp, it was the only suitable language I had a compiler for where I wrote this.
If you know JAVA the code is accentually the exact same other than writing to the console.

What is Minimax?

Minimax is a computer algorithm which looks at all the possible outcomes of a situation and decides which is the best decision to take. This makes it perfect for turn based computer games.

It works on the principle of ‘Maximizing’ the chances of its self (the AI) winning while at the same time ‘Minimizes’ the chances of the other players winning.

The concept is actually extremely easy to understand.

The game which will use Minimax

In this tutorial I will be designing Minimax for a ‘pick up stick game’. The rules of this game are simple which makes it easy to explain and are as follows.

- The ‘pick up sick game’ is a game played by two players.
- The game starts with a number of sticks (Ill be using 10 in this example).
- Players take turns of either picking up 1,2 or 3 sticks.
- The player to pick up the last stick looses.

The game tree

The ‘Game Tree’ which is all possible game out comes of the game can be seen in the image below.

For ease of understanding I have shown the tree as if the game was from six sticks onwards. Ie, player one takes 1 sticks and player two takes 3 sticks 10 – (1+3) = 6; then the next move is player one’s in the game tree.

Now remember if there is 1 stick left and its your turn, you have to pick that stick up which means you loose.

Note: A player cannot make a loosing move on purpose and this is not shown.

Minimax game tree for 'pick up sticks' game

How to interpret the ‘Game tree’ diagram

Each player takes a turn at making a move. Players take alternate turns. This is shown to the right (P1 / P2).

The game ends once there are no sticks left. If you add up all the ‘Leaf’s ‘ of a game branch it will add up to be 6.

A branch is a possible way the game could play. In the diagram from 6 sticks left onwards the game can end in 10 different ways. Hence there are 10 branches.

Branches where blue wins are circled in blue and branches where red wins in red.

Leafs are shown in Orange, Purple and Green. They represent how many sticks will be picked up if that branch or fork of the game is taken.

Familiarize yourself with the game tree. I will refer to it thought the tutorial.

What the game tree shows us.

The game tree can be used to find the best possible move. For example, in the diagram when there are 6 sticks left and its player one’s turn it would be better for the player to pick up 1 stick this is because it results in a more likely chance of winning then picking up 2 or 3 sticks.

Picking up 1 stick results in a 3 to 1(66.67%) chance of winning where as 2 or 3 sticks results in a 1 to 1 and a 2 to 2 chance (50%).

Writing the code

So now how do we write code to search through the game tree to find the best possible move at any give point in the game?

A 2 player version

First you need to set up the rules of the game I suggest you write the game if you were writing 2 human player version first.

[csharp]
//The number of starting sticks
private static int NoSticks = 10;

//Max number of sticks a player can pick up at a time
private const int MAXPICKUP = 3;

//Holds the amount specified by the player to pickup
private static int PickUpAmount = 0;

//Holds which players turn it is
private static bool player1 = true;
[/csharp]

We set up values to hold how many sticks are left, we define the maximum pick up amounts and a value to hold which players turn it is (which will act as a switch between the players)

[csharp]
static void Main(string[] args)
{
//Let the game run while there is atleast one stick to pickup
while(NoSticks >= 1)
{

/*Prompt player one how many sticks they would like to pick up
*when its their turn. And prompt player two when its theirs.*/
if (player1)
{
Console.Write(”How many sticks would you like to pick up player1? :”);
}
else
{
Console.Write(”How many sticks would you like to pick up player2? :”);
}

//Read in the amount of sticks to pick up specified by the player
try{
PickUpAmount = Int32.Parse(Console.ReadLine());
} catch (System.FormatException ex) {
PickUpAmount = 0;
}

//Only make a the move if the pick up amount is valid
if (PickUpAmount < 4 && PickUpAmount > 0)
{
NoSticks = NoSticks - PickUpAmount;
Console.WriteLine(”Number of sticks left ” + NoSticks);
player1 = !player1;
}else{
Console.Write(”You can only pick up between 1,2 or 3 sticks”);
}
}

/*When there are no sticks left, the game is over.
*who ever picks up the last stick looses*/
showWinner();
}

[/csharp]

Next we write code to run the game until the game is over.

[csharp]
///
/// Shows which player has won the game.
///

private static void showWinner()
{
if(player1)
{
Console.WriteLine(”Player 1 wins”);
}
else
{
Console.WriteLine(”Player 2 wins”);
}
}
[/csharp]

Show which player has won the game.

Summary

If you wish to see how the 2 player version game runs download the source code and comment out the line that has ’showPlayerBestMove();’ in the file MainClass.cs

The AI version

The following code will go in a static class called ‘AI’

[csharp]
public static int three = 0,two = 0,one = 0;
[/csharp]

In the AI class we need to set up variables to hold how important the AI picks the corresponding amount sticks.
Because in the ‘pick up sticks’ game you can pick up one, two or three sticks we have values representing these choices.

For other games: This would be a list of every posible move in the game at any one time.
as you could imagine some games have thousands of choices a player can make
and this list can be quite large and will likely be an array of choices.

[csharp]
public static void runMinimax(int sticksLeft,bool playerAI,int noSticksToPickUp,ref int rootPickup)
{
int maxPickup = 3;

//Make the move
sticksLeft -= noSticksToPickUp;

//If after the pickup is made the game is over (no sticks are left) switch the turn
//to the other player.
if(sticksLeft == 0)
{
playerAI = !playerAI;
}

//Test to see if it was a lossing move
if(sticksLeft <= 1)
{
//'Max' has lost - Min has won (BAD)
if (playerAI)
{
if(rootPickup == 1) one- -;
if(rootPickup == 2) two- -;
if(rootPickup == 3) three- -;
}
//'Min' has lost - Max has won (GOOD)
else
{
if(rootPickup == 1) one+ +;
if(rootPickup == 2) two+ +;
if(rootPickup == 3) three+ +;
}
return;
}

//Start move logic using game rules

//If there is less sticks left then the maximum pick up amount then set
//the maximim pickup amount to the number of sticks left.
if (sticksLeft < maxPickup)
{
maxPickup = sticksLeft;
}

//Start the recursion which runs through all the posible moves at this current level

for (int i = 1;i <= maxPickup;i++)
{
runMinimax(sticksLeft,!playerAI,i,ref rootPickup);
}
return;
}
[/csharp]

runMinimax is basically the recursive method which runs the Minimax logic to find out how many sticks to pick up at the current point in the game. The amount calculated is the ultimate best choice to pick up.

For other games: Runs the Minimax logic to find out the best move at the current point in the game. The move calculated is the ultimate best move.


    parameter - sticksLeft

The number of sticks left avaliable to pick up. It is ‘the current state of the game’. In other games such as chess this would be the current board state. Ie, what pices are on the board and their positions.


    parameter - playerAI

Holds which players turn it is. If it is the AI’s turn (playerAI is true),
we are maximizing the chances of the AI winning. If it is the players turn, we
are minimizing the chances of the player winning.


    parameter - noSticksToPickUp

The number of sticks to pick up from the current game.


    parameter - rootPickup

This holds the value that we increment (the ‘root pickup amount’/'game move’ results in a win for the AI when the game is over on the current game branch) or decrement (result is oposite of increment). Think of it as the origonal move made by the AI that started the Minimax recursion. It is the value passed to the minimax algorithum method on the bottom of the call stack.
If we want to test how good picking up 3 sticks at the current point in the game, we pass it 3.
If we want to test how good moving king from A3 to A4 is we pass this logic.

[csharp]
public static int getNoSticksToPickUp()
{

//Find highest value logic
if(one > two && one > three)
{
return 1;
}

if(two > one && two > three)
{
return 2;
}
if(three > two && three > one)
{
return 3;
}
return 0;
}
[/csharp]

To finish of the AI class we need a method to find and return the best move.

Other games: This may be a loop that loops through all posible moves and returns
the highest move.
It is returning the maximum (best) move.

Implementing the AI into our original 2 player game.

Finally we need to take our AI code and implement it the origonal 2 player game. We do this by adding logic to start the algorithum

[csharp]
///

/// Shows which player has won the game.

///


private static void showPlayerBestMove()
{

int maxPickup = MAXPICKUP;

//If there is less sticks left then the maximum pick up amount then set

//the maximim pickup amount to the number of sticks left.

if (NoSticks < maxPickup)

{

maxPickup = NoSticks;

}

//Start the recursion which runs through all the posible moves at the root level

for (int i = 1;i <= maxPickup;i++)

{
AI.runMinimax(NoSticks,player1,i,ref i);

}

//Get the number of sticks to pick up as calculated from the AI

Console.WriteLine("You should pickup " + AI.getNoSticksToPickUp() +
" sticks");

//Resets all the moves. All moves will now be equally important
//until AI is run again
AI.resetCount();
}

}
[/csharp]

And finally add a line to run it all. Replace your player 2 logic with the call to start the AI

[csharp]
//call AI logic

showPlayerBestMove();
[/csharp]

Sumary

In summary I would like to share a few things I have learnt while doing Minimax.

- You still need to add your game specific logic. The code shown above will be similar for every game though you will still need to add your own game specific logic for things like making the move.
-Dont try to make your code perfect the first time around. Write the logic for understandability you can fix things latter (part 2).
-Its a very good idea to know how heap / stack works and how by reference and by value parameters works if you dont know these two things well you will never get anywhere.
-Know how to debug your code and how to set break points where certain conditions are meet. Know how to step into and over methods. Make sure you watch the call stack while debugging. Debugging recursion is always intense.

Source code / Program downloads / Other

I suggest you take a look at the full copy of the tutorials source code and run the compiled program (.net/Monno enviroment needed). Both source and binary can be found here.

Please leave questions and comments.

If you wish you can convert this tutorial into another language (programming or spoken) and I will put it here.

I dedicate this to Cocco.

Cobol

Thursday, April 26th, 2007

Cobol - Code Only (no comments because even the programmers have no idea what its doing) Business Oriented Language.
COBOL hurts my head. No more please.
I think its funny that in 25 years programmers will probably go ‘oh no not C#’ (if their not already doing it now).

That is all.

Mobile app - Geek tools

Friday, April 13th, 2007

This weekend I have finished programming my first mobile application. It actually wasnt the first one I have finished but it was the first one I started.

Basically the idea behind Geek tools was to create a set of useful and fun tools for mobile that only geeks would have a need for.

Features:

Prime number checker: Can check a 64-bit integer for primality.

This may come in use some day. Maybe if you only place bets on horses which have only primes as their number.

Al bhed translator: Al bhed is a language spoken by a race in the game Final Fantasy 10. This tool allows you to convert from Al bhed to English and vice versa. The code that does this is very generic so it could be done to any other language and I am open to suggestions. Eg, Elvish.

Binary / Hex / Octal / Decimal / ASCII convertor: So far this is the ‘killer app’ of the tool set. I havnt seen any other J2ME apps with this capability so it may be the first! It can convert between any of the formats to any other format or base.

Some advice when using this; know the capability of your phone and dont give it something insane to convert to all other formats or it can take a while.

If you wish you can download it here http://jwhatson.googlepages.com/GeekTools.zip

Im very open to suggestions and ideas so please let me know if you want a feature added to Geek tools. Also like all of my phone apps im interested how it works on your phone.