Sunday, March 2, 2014

My AI tron bot

Tron is just similar to the snake game you play on mobile. There is a slight variation that at every step, the snake keeps growing on it's size. You hit anywhere, you die.


The movie Tron Legacy is entirely based on this game.

My tron AI was ranked 31/672 bots in Codingame. I actually didn't use any machine learning techniques. Instead I learnt myself by watching the replays of a lot of games to decide my strategy.

The challenge in this game is that our code should work for any number of opponents into the arena and it should run in 100 milli seconds. And within 100ms, our bot should decide the next move (left/right/up/down).

This is the core logic of my tron AI.

struct Direction{
    int dir;
};

//Just a comparator which could compare two directions and returns true if directionA is better than directionB

inline bool operator < (Direction A, Direction B){
    if(A.dir==B.dir)
        return false;
   
    if(isSafe[A.dir]!=isSafe[B.dir])
    {
        if(isSafe[A.dir])
            return true;
        return false;
    }

    if(selfish[A.dir]!=selfish[B.dir])
    {
        if(selfish[A.dir])
            return true;
        return false;
    }       
    if(defend[A.dir]!=defend[B.dir])
    {
        if(defend[A.dir])
            return true;
        return false;
    }
   
    if(attack[A.dir]!=attack[B.dir])
    {
        if(attack[A.dir])
            return true;
        return false;
    }

    if(!(target[A.dir]==target[B.dir]))
        return target[A.dir]<target[B.dir];    
           
    if(futureful[A.dir]!=futureful[B.dir])
    {
        if(futureful[A.dir])
            return true;
        return false;
    }
   
    if(best[A.dir]!=best[B.dir])
    {
        if(best[A.dir])
            return true;
        return false;
    }

    if(closer[A.dir]!=closer[B.dir])
    {
        if(closer[A.dir])
            return true;
        return false;
    }
   
    if(safeTouch[A.dir]!=safeTouch[B.dir])
    {
        if(safeTouch[A.dir])
            return true;
        return false;
    }
   
    if(touches[A.dir]!=touches[B.dir])
    {
        if(touches[A.dir])
            return true;
        return false;
    }
   
    return A.dir<B.dir;
}

Step1: Choose a safe move. An unsafe move is a move which lets your bot die.
Step2:
Be selfish. Choose the direction containing maximum free spaces. This might sound crazy. But if you don't take this path, you are probably going to lose anyhow. It's better to take a selfish move which might help you if your opponent makes mistakes.
Step3:

Proof
: If player X can reach a point (x,y) faster than any other player, then regardless of the shortest path X choose, no one can stop X in reaching (x,y).

By finding the nearest player for all the points in the map, we could know the points a player can reach faster than anyone else.

A defensive direction is a direction which will make the number of nearest points to be maximum (points we can reach faster than all enemies should be maximum). Choose such a direction.

Step4: Choose an attacking direction if possible.
Let S be the set of points we can reach faster than all the enemies.
For each point in S, draw a line from S[i] to current position and check whether the enemies have less survival time than us. Choose a point for which ∑(survivalTime[me]-survivalTime[enemy[i]]) is maximum and move towards that direction.

Step5: In case we have many possible positions to attack with equal score, choose the target which is closer and move towards it.

Step6: We should think at least one step ahead in order to utilize maximum space on the board. We need not waste spaces on the board. (Edit:  This can help to utilize more spaces than that of this step.)

Step7: Block all the points enemies can reach faster than us. Now choose the direction with maximum survival time.

Step8: Get closer towards the farthest enemy faster!. Going towards the farthest enemy can give us some space to breathe in.

Step9: Once we know that an enemy is about to die, we should try to occupy that space. It's better not to touch the enemy who is about to die. This should be done only when aliveEnemies>1.

Step10: It's always safer to move on the edges of walls to occupy more spaces.


You probably could have got bored if I had shared my entire 1035 lines of code.
Hope you liked it :) Share your suggestions/improvements.