This project made possible by notepad.exe and SICStus Prolog evaluation version 3.8.5

Nibbles

Nibbles is an old game from back in the dos days that ran in a qbasic interpreter.  Microsoft was kind enough to give the game away for FREE with dos.  Hidden deep in the recesses of one's c:\dos directory there was endless hours of enjoyment.

The game consists of one or two 'snakes' on a rectangular board.  Also on this board was some kind of goal, or food, which was designated by a number (this was an ansi text game, the 'graphics' were cursors and numbers).  A screenshot of this is depicted below.  Since we couldn't find a screenshot of the original ms-dos version, a mac clone shot will have to suffice.

The snake(s) are always in motion.  The player(s) decide where to steer the snake.  The primary goals are obviously to get the food, yet avoid the other snakes and any walls/obstacles, as these are losing conditions.  The snake is not allowed to double back on itself (ie, if the snake is moving right, to go left, you have to go up or down first, then turn left.  You could choose the speed of the snake when you start the game, and also decide if you want the game's difficulty to increase as you play (the game would automatically speed up the speed up the snake as you played, forcing you to think faster.

Some of the challenges of the game were to navigate the snake quickly while not having a lot of time to think about your moves.   Also, it was all to easy to wrap yourself up into a ball, blocking your movement with your own body.  This was actually a pretty big challenge for us to overcome.

Other games of note from this sorely missed era:

•     King's Quest 5:  Mike's first adventure game

•     Test Drive 3: Mike's first driving game

•     Gorillas:  The counterpart to nibbles.  Had real 'graphics', not just next

•     All of the Leisure Suit Larry games.  Sierra's foray into sex-based games.

Nibbzilla!™

We decided it would be nice to reminisce back to the old game of nibbles and model our agent after it.  The nibzilla agent handles two players in the nibbles board.  Given two snakes (a snake consists of a name, length, and all of the positions it occupies), the location of the goal, and the snake that we're interested in, the agent will determine which path it should take to attempt to reach the food.  Depending on the opening position, this may prove to be impossible (if the other snake is closer to the food).

We started the project much like the path-finding homework, creating a data structure to represent the snake. A snake is denoted as the following:

        snake(mike, 3, [(1, 1), (1, 2), (1, 3)])

where you have the name, the length, and the positions it occupies as the parameters.

We first had the crazy idea that we would be able to use the built-in search behavior inherent to prolog to find the best 'way' to get to the food.  This was accomplished the way we had initially done the shortest path homework:  by explicitly defining what it means to have a good path to the food.  Then we tried to just give that definition two snakes, and have it fill in the path.  Prolog went into 'never return an answer mode'.  In hindsight, there were a few reasons why this happened:

• Prolog is examining a search space that grows exponentially with the size of the board.  Finding a solution could take forever.

• This is a very 'dumb' way of searching.  It did not take into account the movement of the snakes.  In other words, it's like the head detaches off the snake and goes looking for a path to the food.

We then decided that a solution similar to that of the homework was needed, where we generate the shortest path for the snake.  We started with our homework solutions and went from there.  First, we adapted the shortest path tree to the nature of our agent, taking into account obstacles placed on the board and other syntactical differences of our 'world'.  We then decided on an algorithm to decide a move which involved taking intersection of the first move of the shortest path and the snake's available freemove list (places that don't put it on top of any snake body parts and avoids obstacles).  If the shortest path and the freemove list don't match, then we'd take any freemove available as the next move.  There was a big problem with this in that the shortest path didn't take into account the snake's body.  The snake tended to wrap itself up in its body if it was blocking the shortest path with its own body.  After we had thought that we were really close to being done, we had to redesign how the snake determined its next move.

What we concluded is that we needed to look into the future and determine how 'good' the next possible moves were.  Different end scenarios have different goodness factors: for example, the best move to make leads the snake to finding the food. The worst move leads the snake to trapping itself. If one snake made a move that trapped the other, this was considered less desirable than finding food but still a win condition.  The goodness algorithm assumed that each snake would always move towards the food when replying to another snake's action. This algorithm ended up working extremely well, and we were actually able to throw at it some pretty interesting setups.  To show the result in some form other than just the lists that prolog returns, we conjured up a few animated gifs to show the path of the snakes.  Those appear below:

Pictures of Output

In this first picture, red is wrapped up in such a way that the first algorithms that we tried resulted in the snake winding itself up and trapping itself. This is because using the orignal algorithm didn't look ahead, and so the snake didn't see a way out of its own winding body.  However, once we used the future lookahead method, the snake was able to see that its tail clears itself in time to get to the food.

In this second picure, two snakes are in an obstacle course of sorts, both trying to find a way to the food.