Snake Game Artificial Intelligence -

i developing snake game ios: https://github.com/scottbouloutian/snake

my goal have ai complete game of snake optimally (have snake fill board).

i using ida* find path snake's current location food. works. however, algorithm doesn't take account fact may need more food in future. result, tends box in.

i.e. snake's goal @ given time find food, whereas it's goal should fill board (finding food along way).

how can add or modify approach make ai win game of snake? there better approach should use instead? i'm trying come ideas. thanks!

if board static rectangle (not torus - no crossing though borders) optimal strategy find set of longest closed paths through board, such each point in board in @ least 1 path.

if board empty (there no obstacles) there exists "ultimate" path in form

 16|.1|.6|.7  15|.2|.5|.8  14|.3|.4|.9  13|12|11|10 

which goes through tiles, snake following pattern eat food, , fill whole board

if there obstacles, such path not have exist, should find set of such longest paths, , switch between them, when food appears in unreachable spot of current path.

for example

####### #.....# #.#.#.# #.....# ####### 

here have 2 paths have consider, one-longest, going around whole board, missing central spot, , 1 small loop going through it. long food not appear in center, should use outer loop. hopefully, if food appears in center when fill remaining blocks - "win". if appears there sooner - have eat (switch other loop) , depending on current length - best loop, or hit tail , "lose". in each case, score best possible achieve on board locations of foods.

non a* based approach find optimum, different problem, should longest closed path, not shortest.