1. Invent a heuristic for the 8-puzzle that is not admissable. Describe why it can lead to a suboptimal solution to a particular 8-puzzle (hint, consider n 8 puzzlethat is really easy to solve).

A heuristic where the squares are ranked by how many of the squares around them are supposed to be around them, given the solution, then chooses the highest ranked (worst) square possible to move would be non-admissable.  If there were two squares with the same rank, it would choose at random.  In addition to being very slow, it would often generate suboptimal solutions. Given this puzzle:

-1 4 2
 1 3 5
 6 7 8  

the program could easily choose to do this 

4 -1 2
1  3 5
6  7 8

instead of this

1  4 2
-1 3 5
6  7 8

leading to a more complicated solution than necessary.

2. Describe a some relatively common 2 player game that is not zero sum.

One example is the cooperative mode in We Love Katamari, a sequel to  a popular Play Station II game called Katamari Damashii.  The basic premise on the two games is that the Prince (controlled by the player) must roll a katamari (something like a ball) around various locations, collecting objects to increase the katamari's width. When the katamari is large enough, it is turned into a star.  While the main game involves a single player, there are also two-player modes.

The first, battle mode, is a zero-sum game.  It has the same goals as the single-player game, but two players are competing against one another.  Even before the end, the success of one player is a detriment to the other player.  One player can collect all the objects in one area, forcing the other player to find somewhere else.  If one player becomes two big, the world scales up to accommodate the larger katamari.  This generates objects that are two big for the smaller player to collect and that hinder her movement.  There is also the simple fact that at the end of the game, one player wins and one player looses.

Specifically in We Love Katamari, there is a cooperative mode.  This is not a zero-sum game.  Instead of battling one another, both players control a single katamari.  One player controls when and how quickly the katamari moves whle the other controls the direction it takes.  The success of the players depends entirely on how well they can communicate their intentions to one another and how intimately they know the controls.  This means that the more successful one player is, the more successful they both are.