Page 2 - [appleeaters]How long?

I never got a chance to really delve into killing robots intentionally. It happens as a matter of course in this algorithm. Too much work, not enough play

http://jeff.caughel.net/robots.phps

-Jeff

Great looking code!!

my submit:
http://deaddy.no-ip.org/apples.phps

I'll be posting my code online in the near future, but until then ...

I was wondering what people were using for an algorithm. Looking at lots of lines of code can sometimes make me go crazy unless I spend some serious time understanding it. For example, my algorithm:



* the time limit is calculated thus:
60 sec - (last_move * distance)
last_move = time it took for last move plus a tiny amount to compensate for my code
distance = 1/2 the distance between bad robot and myself

I really like where I have the closest robots and I scan all apples to find any eatable apple. With that information, I can plot the best route to take ... but it didn't compensate for robots crasing into each other. Room for improvement.

When I get things ready, the web site will be http://rumkin.com/reference/php_contest/ with a link to the apple eating robot competition there.

Well... mine was pretty straight forward.
find all live robots within M moves
in each of the 8 directions
find all apples within M/2 in each
of the directions, consider their
importance to be 1/D^2
find all dead robots within M/2 in
each direction, consider their
importance to be 1/D^2
if there are apples that can be reached,
go in the direction with the highest
score (sum of 1/D^2 for each apple)
else if there are dead robots that can
be reached,go in the direction with
the highest score (sum of 1/D^2 for
each dead robot) and try to stay
opposite the closest live robot
else move toward the nearest side toward
the point you just were at. (this
presumes that there will be lines of
robots horizontally or vertically at
that point x or y respectively.)


I wanted to be more agressive about killing robots... I just ran out of time to develop
the algroithm.

the 1/d^2 was arrived at empirically... for
those familiar with physics, I would appreciate
a detailed explanation of why that number works
better than others.

Thanks,

Jeff

Nice idea to describe our algorithms! Much easier than trying to understand code ;-) Here is mine:

I used a standard (?) AI algorithm, breadth first search of the game tree:

I use a 40x40 box around me. Anything outside that, is not taken into account.

I created an EvaluateBoard() function which gives an evaluation of how good things look in the current board. This function, takes the current 40x40 box, the starting number of apples and the starting number of live robots. It uses weights to give back the evaluation. 4 things are considered:
Total number of eaten apples (large is good)
Total number of killed robots (large is good)
Median distance from apples (small is good)
Median distance from robots (large is good)

I also have one (recursive) function that evaluates all available moves (1 to 9) then simulates robotslib for these moves and evaluates all new moves (1 to 9) then simulates robotslib for these moves and evaluates all new moves (1 to 9)...etc...you get the point...
In other words it plays ALL moves, then does the work of robotslib to get the new board and plays again ALL moves etc. I do this for a depth of 2 because larger depths need LOTS of time.

To find good weights for EvaluateBoard, i created a small test script that changed weights, played 30 games and recorded scores.

drm

I tried a couple of different things.
Stuff I tried that just took way too long.
k-means clustering to find the best cluster of apples to go for.
alpha-beta search on the possible moves. Worked ok for a depth of 2-3 but higher than that was very painful to wait on.
evaluating all robots, apples on every move.

What seemed to work for me
Setup a move function that would try all valid moves and score the resulting game state.
I upped the score on a move for things like, moving in the direction of an apple I could actually reach. Killing the closest robot. Moving toward a dead robot. Moving toward the average point for robots on the same lines, and staying on the otherside of a deadrobot, and the closest live robot. Also added points for standing still.
Took the highest score and used that, otherwise teleported if the score was negative.
If there were no more teleports, then I made the move that would give me the most points, usually running into some robot.
I looked at a box around my guy and evaluated off of that to save time.

--Adam
Code at http://www.joannstevenson.com/robots/mine.phps

My original algorithm ended up being my last due to running out of time. Basically I had a recursive apple-searcher. It would find a path of a certain predefined depth that got the most apples in a row. Worked great for maps with too few robots, but with a depth greater than 3 apples, it just died... it was very depressing because it could have been better if I hadn't screwed up later on in trying to kill robots. The script I submitted doesn't even consider killing robots. In the end the old things I tweaked were some basic numbers for size of search and depth. For a map with lots of apples and few robots, it looked further away from player for viable apples. Not terribly useful, but it helped a bit.

My idea I worked on for like a week was to try and kill robots by using a dead robot. I ended up with an algorithm that first did a search for apples (as above), then if it couldn't find any it would simulate movements via a fake robotslib. It went two moves in the future, determined how many robots were killed in the best case, and chose that. If it ever found a dead robot within reach, it made a run for it and waited there until it was no longer safe.

I spent so much time on this algorithm that I didn't have time to do anything else once I found its huge flaw. For starters, just killing robots wasn't that good for determining a "best move". You guys had better ideas there - giving weights to getting nearer apples and whatnot. But my main mistake was thinking a dead robot would really be that useful. On maybe 1/10 the maps I messed with could I even get to a dead robot, and every time I did, I was able to get only a few kills before I got surrounded too badly and had to abandon it.

I will not win. But I did learn a bit.

it is easier for me to describe an algorithm by pointing to the code than using words but it might be fun to give it a go...

- initialization
- for each possible move
- if the move is safe and in-bounds consider it
- if an apple is found there commit to that move
- if I didn't find any safe moves, then teleport if I can and there is adequate time remaining or move wherever it causes the most live robots to collide
- else for each safe move see if I can walk safely to any apples within a 17 move diagonal
- if I find more than one safe apple path choose the path that leads toward the most apples
- if I don't find any safe apple paths then select the move that causes the most live robots to collide
- if I don't find any moves that cause collisions then select the move that takes me away from robots or edges and toward the most apples
- after each the move check to see if I am running out of time and if so quit checking for apples/collisions and walk toward the nearest live robot.

... I think that's it.