Snake algorithm

[jondmml]

I am trying to create a multiplayer snake algorithm with a basic form of artificial intelligence for the enemy snakes. The goal of the game is to stay alive for as long as possible without crashing into a snake's tale. The game consists of a grid on which the snakes move.

I have created a minimax algorithm for the enemy snakes, however it is extremely slow and can calculate no more than three levels deep before making the program unbearably slow. The algorithm chooses a move for the snake that will keep the snake "alive" for the next three moves.

My question is whether anyone has any ideas for a better algorithm or strategy that that the enemies should follow. Currently, my goal is to have the computer snakes attempt to survive as long as possible.

Thanks,

Jon

[PaulButler]

Well, I guess the best way to figure out strategies would be to play the game and observe the strategies that work. Here are some things I would start with:

- Is there a snake or wall directly in front of me? If so, turn into the area [left or right] with the most open space.
- Are other snakes heading in my direction? Who is closer to our intersection? If it is me, keep going, if it is a tie or the other snake, change direction
- Is another snake near me moving in paralell to me? Who is ahead? If I am ahead, turn in the direction of that snake. If I am behind, turn away.
- Am I stuck in an enclosed space? If so, stick to the walls to better use the area I am left with.

The game you described is more like Tron than snake, if you havn't looked into Tron you should; there may be some strategies for humans or bots since it is up there with pong and tetris in terms of the number of times it has been cloned.

[jondmml]

Thanks for the advice. I've realized now that the game is called Tron and not snake. As to strategies, I came to the same general conclusion that you have. However, my problem is I do not know the best method to determine which direction will have the most open space. I do not know of a simple and efficient way to do this.

[PaulButler]

The first thing that comes to mind is to take the distance to the nearest snake or wall on each side, and go whichever direction this distance is farthest. There are still many cases where this will not be the ideal direction, but it will be a good start.

You could also do a flood-fill of the area on each side and count the area, but this would only be effective if one or both sides were closed.

Keep in mind that Tron is a bit of a reflex game unless it is really slow - if the computer could create an enclosed area and just stick to the walls, it could probably outlast a human because it would be able to have perfect timing. It is difficult for a human player to make 100% use of an enclosed space, whereas a computer player can do it quite easily.

[bugzpodder]

i know one snake algorithm that kicks ass in two player mode. maximize the difference between square you control minus square others control

[jondmml]

That's sounds like an interesting idea I just don't understand it fully. Do you mean maximize the space between the head of the snake and all other squares on the board? A little clarification would help a lot!

[bugzpodder]

you a control a square if you can get to it before the other snake can.

[Drakain Zeil]

Split the area's into left and right of the snake, and take a histogram of the pixels on both sides

Histograms: http://homepages.inf.ed.ac.uk/rbf/HIPR2/histgram.htm

May want to throw in some simple pathfinding to see if you actually CAN get to the 'better' histogram side. Tweak it I guess.