Engineering Projects/Poppit/Howard Community College/Fall2011/502 AZM

Problem Statement

Use math of various types to analyze poppit, and then try to use this new knowledge to devise strategies or algorithms to play the game better.

Team Members

ZThompso7635

mkhan4793: http://en.wikiversity.org/wiki/User:Mkhan4793

Tophat: http://en.wikiversity.org/wiki/User:Tophat

Summary

People can approach math in different ways in the game. It depends on how you look at it. You can look at the game as a matrix board and try to eliminate the rows and columns by matching the color of the balloons and eliminating them periodically.

team weekly reports.

Poster

Poppit Graphic

Story

Our project was to analyze poppit mathematically. The first step was to decide how to look at the game board itself. Determining the irrelevant information was the first obstacle. The shape of the balloons and the little prizes inside some them make the game more interesting visually, but they do not add to the math of trying to eliminated all the balloons.

Since none of us are mathematicians we went to see a math instructor at the college, Roger Hartman. He helped us come up with many ideas and paths of thought that may be of use in the project. We even discussed making each value of a matrix set to a sinusoidal wave-function which would interfere with the spaces around it, which would be out of phase with it due to their position. If the interference produced a zero due to destructive interference then the balloons were of the same color and could be popped. While interesting, this proved more complex than necessary.

Another interesting thing we came across was a theorem that proved that any map could be colored with only four colors, and none of the boundaries of the same color would touch. If applied to poppit, it means one could conceive of a board in which no moves were possible at all, because none of the balloons would be adjacent to each other (Poppit has five colors, but that just means this is even easier to accomplish). Since the board is randomly generated, unless there is an internal regulator against such things, this proves that statistically there will be an impossible poppit board eventually, i.e. not every board is winnable.

One way we decided to approach the game was as either a large matrix or as a series of interconnected sets. With the approach of the matrix, one can view balloons simply as numbers, one through five representing the different colors of balloons, and zero being the value of an empty space. This way you start off with a 10x15 matrix, where every space is a number between one and five. The goal was then to find mathematical operations one can perform to first search the matrix for numbers of equal value which were adjacent to each other, and then could "pop" those spaces by making them both zero. In addition to making just two of them zero, it would then also attempt to match any other spaces adjacent to the first adjacent one.

Another step in the algorithm would be to always check for zero spaces between spaces with nonzero values. This is how one would make sure the balloons rise up when ones above them are popped, or shift towards the center when whole columns are eliminated.

Strategy guides we found online here and here alluded to the fact that each poppit board that is generated is almost entirely random, so it is likely that some boards are winnable and others simply are impossible regardless of your strategy.

What we have done successfully is establish a way to view poppit mathematically, and potentially write some sort of program that could play poppit for you. We have also proved that unless there is something about the game we have not been told (i.e. something inside the program that keeps it from making an impossible game), it is in fact sometimes unwinnable.

Decision List

Our first decision was how to get in contact with someone from the math department to talk about what kind of math this project would involve. Next we just discussed ideas about moving forward with the math we had found.

Material List

Our work was more an intellectual exercise rather than a construction project. Our materials were essentially our engineering notebooks and the computer.

Software List

The only software we used was Google chrome to play Poppit in, and experiment with its parameters.

Time

It is difficult to say how long it would take to program a computer to beat poppit, because it is less a programming exercise and more a mathematical proof. With access to a program like Mathematica it should be possible to replicate playing poppit in a program using the types of maneuvers we thought of. This would probably take a few weeks to nail down the exact mathematical operations to go with our theories, and then to write a looping program to scan the randomly generated "poppit board" matrices.

Tutorials

Textbooks I consulted were about linear algebra and game theory. The primary ones I explored are below: "Decision Making Through Operations Research" by Robert J. Thierauf and Richard A. Grosse. "Discrete Mathematics with Game Theory" by Edgar G. Goodaire and Michael M. Parmenter. "Numerical Methods Using Mathcad" by Laurene Fausett.

Next Steps

The next thing yo do in this project would be to figure out how to perform these matrix operations that would clear rows, and move values around within the matrix. I do not believe it is possible to make a robot that always wins at poppit, due to the four color theorem, but through testing of the replicator one could fine tune its move order to potentially make one that wins some of the time.