Elegant Report .edu



by: Lewis Sykalski

CLASS: ECE 539

PROF: YU HEN HU

[pic]

SPACE INVADERS ADAPTIVE DIFFICULTY

A NEURAL NETWORK APPROACH

INTRODUCTION: 3

PROPOSAL: 4

HISTORY OF GAME: 4

HOW TO PLAY: 5

OVERVIEW OF DESIGN: 6

DESIGN PHASE I: IN DETAIL: 7

SCORING AND DIFFICULTY: 8

DESIGN PHASE II: IN DETAIL: 9

PLAYER SELECTION: 11

DATA GATHERING: 13

RESULTS: 13

CONCLUSION: 14

SCREEN CAPTURES FROM THE GAME: 15

APPENDIX: CODE: 18

REFERENCES: 18

SPACE INVADERS ADAPTIVE DIFFICULTY

A NEURAL NETWORK APPROACH

INTRODUCTION

It’s a cold Christmas Eve. You are walking home from a satisfying dinner with your family who live just down the block. Suddenly, you hear a noise above you. Looking up, you see nothing. You turn back towards the road and begin walking. There it is, you hear it again. You look up and see 8 shadows in the distance of outer-space moving horizontal to the horizon. What could it be? You don’t know what it is, buts it’s moving quickly towards earth. Suddenly, 8 extra-terrestrial creatures come into view, moving in the same horizontal pattern as before. It is obvious they are hostile. As you look around for a suitable weapon to battle with, you notice it is not just 8 aliens who are intruding into the atmosphere of your home planet, it is an entire fleet. You happen to find a laser blaster lying in a ditch on the side of the road amidst some leaves. You grab it, putting forward into motion a surely epic battle. As you blast alien upon alien out of the sky, you realize this is just way too easy. You could enjoy 5 Christmas dinners in the time it takes for the alien fleet to inch 100 feet closer to you! You throw your laser blaster to the ground only to abandon your home planet in its time of need.

The previous scenario I described, as you may have guessed, isn’t very realistic. Aliens coming out of the sky to invade earth? Ludicrous! A laser blaster lying amidst some leaves? Unrealistic! While one may question the integrity of the situation, one can not dispute the last few sentences. Difficulty is a major problem with games. An easy game is a boring game, a game which no one wants to play.

That's why there is the miracle of difficulty setting.  It breathes new life into video games by allowing the user to specify a level (e.g. easy, medium, hard) that he will find challenging but at the same time not too difficult.  He must be able to progress in the game, while still finding the game demanding.  This difficulty setting is often hard to discover.  Most often it comes from experiment.  The player must keep retrying via trial and error to find his "optimum" difficulty setting. This is, however, sometimes a long and tedious process.

PROPOSAL

Wouldn't it be cool if the computer could solve the difficulty problem work for you?  By keeping track of the player's history, the computer can assess your skills and find your "optimum" difficulty setting.

The Game:

I intend to demonstrate and apply adaptive difficulty to a game near and dear to all gaming enthusiasts--Space Invaders. One needs know only a little about the history of arcade machines to know that it was the first video game machine ever built.

I will create my own version of space invaders to ease with integration. I intend to add player recognition, score tallying, and statistic calculation abilities. I will also add the difficulty feature to it and distribute the difficulties amongst 10 settings.

Method:

I will use a MLP network to solve the difficulty problem.  The features will be various player statistics(avg. score, games played, highest score, etc. ) on varying difficulty setting.  The classes will be the 10 different difficulty settings in a one-hot style encoding.  

The training data will come from real statistics generated by multiple players who are relatively new to the game of space invaders with data sampled at various stages of their Space Invaders evolution.  The testing data will come from a mutually exclusive set of other players. Now as one may have already guessed, there are two different ways to generate the target output(difficulty) for the players, since it is somewhat arbitrary: I can assess their skills myself or I can let them choose what they deem a good setting.  I will use the latter approach in my implementation.

  To evaluate the performance of the neural network-generated difficulty setting, I will use test players at varying experience levels to determine if the outputs of the neural network match their chosen difficulty. I will be expecting a moderate classification error due to built-in noise in the measurement, which is described in the results section as well as the conclusion.

All neural network programming will be done in Matlab because of its ease of matrix manipulation.

HISTORY OF GAME

Space Invaders was designed and programmed by Toshihiro Nishikado for Taito, Japan in 1978 and remains one of the most popular arcade games ever made. The only way you can get the game today is through ebay where it goes for approximately $1000 or even more.

So the story goes…the idea for this game actually came from a dream Mr. Nishikado had in 1977. In his dream, it was Christmas Eve. A bunch of Japanese children were sitting, waiting for Santa to appear in the sky above Hokkaido. Suddenly they saw row upon row of aliens advancing slowly from Venus. The clever kids realized the threat to Earth and quickly strung together a laser blaster from the hubcap, spark-plugs and battery of a nearby parked car. They moved left and right, blasting aliens out of the sky. After about four waves, the aliens gave up and the Earth was saved. The next morning in his dream (Christmas Day) the kids were rewarded with extra presents and figgy pudding (a fitting reward for saving the earth!)

Space Invaders was the first arcade game to work it's way out of seedy arcades and into pizza parlors and ice cream shops.

The game was so amazingly popular in Japan that it caused a coin shortage until the country's Yen supply was quadrupled. Entire arcades were opened in Japan specifically for this game.

After, the arcade version was made, the game was licensed from Taito by Midway for production in the US. The United States now had a taste of this popular game, and the phenomenon raged on.

The Space Invaders phenomenon stuned conservative adults who were certain the game soured the minds of their youngsters. Residents of Mesquite, Texas pushed the issue all the way to the Supreme Court in their efforts to ban the illicit machines from their Bible-belt community.

In 1980, the game was licensed by Atari for the 2600 game system and was the first arcade game ever adapted for Atari's home system. This is when its popularity in home consoles grew. The Space Invaders franchise has flourished for more than 20 years and according to Taito, the game has generated more than $500 million in revenues over multiple platforms including coin-op, the Atari 2600 and the Nintendo.

HOW TO PLAY

The game-play is described in detail below for anyone who’s not familiar with the game:

OVERVIEW OF DESIGN

The first step in the design process was making the game. This would be necessary because data manipulation would be necessary if I wanted to build such a history of past games. I could not find java source code for such a game so I had to work from scratch. We had discussed the creation of the game in a previous class of mine—CS 302, but we hadn’t actually engaged in writing the game.

The structure of the program is detailed below. The appendix contains the code itself.

There are 10 classes for this program, two text files, and many image files associated with this program. The Spaceinvaders class contains the main method.

The command line parameter must look like the following in order to correctly run the program:

java Spaceinvaders >highscores.

Design Phase I(Space Invaders):

1. Wrote SpaceInvaders main() to interface with keyboard class. Wrote Board class. Loaded an image and attempted to move

2. Wrote Settings Class, attempted to load different images.

3. Wrote intro() method. Developed “play space invaders” screen and title screen.

4. Wrote thing class, hero class, and bullet class. Attempted to shoot one bullet with our hero.

5. Wrote bulletvector class to handle multiple bullets.

6. Wrote Alien class. Tried Moving a single alien in a snakelike pattern.

7. Wrote Fleet class. Developed pattern for movement.

8. Wrote play method of Spaceinvaders class.

9. Added shields to the screen by using the thing class.

10. Added different formations for different boards.

11. Added code for difficulty feature.

12. Added sound to the game via AudioManager Class.

13. Wrote Highscore method and screen

14. Wrote History method for keeping track of certain variables useful to the neural network.

Design Phase II(Space Invaders w/ Adaptive Difficulty):

1. Downloaded and adapted Professor Hu’s MLP back propagation files to suit the type of network necessary for adaptive difficulty.

2. Scaled inputs.

3. Adapted to one hot method.

4. Tested

Below is a flowchart showing the design flow.

[pic]

DESIGN PHASE I: IN DETAIL

The code was authored in its entirety by me with the exception of the Audio Manager class.

Execution enters through main when the command to begin execution is issued. The main method begins by loading the images, and initializing the hero, his and the aliens bullets, as well as the fleet itself. Execution now enters the play method where the intros occur and the high scores are loaded. The bulk of the execution then takes place—the game itself.

The GUI begins the game and each subsequent iteration of the game by clearing the board. It then draws all applicable items to the GUI. A little explanation of the GUI is required here for a base understanding of the game. The GUI is a very simplistic GUI. It consists of a X x Y grid where images can be loaded and a text box at the top for displaying text (such as score). For example, look below I have drawn in a few lines to demonstrate the grid:

[pic]

1. The method then moves every alien via the fleet.move() method. A method which moves the whole fleet in a snake-like fashion down the screen.

2. The bullets then are fired if the probability is met and if the specific type of alien can fire them.

3. The method then checks for a shield and bullet intersection—indicating a hit. If so it removes the shield from the fleet of shields.

4. Checking for a hero bullet and an alien now occurs. If the alien is dead - it will remove that alien from the fleet.

5. Finally it checks to see if a bullet from the aliens hit the hero or if the fleet has reached the bottom of the screen. If so the number of lives are decremented.

At any time during the play() method the hero(the player) can interrupt the method via pushing a key. The hero has the following options:

1. ( = move left –moves the hero one grid space to the left.

2. ( = move right –moves the hero one grid space to the right.

3. SPACEBAR = FIRE - creates a hero’s bullets

Difficulty and Scoring are looked at in the following section.

SCORING AND DIFFICULTY

The difficulty and scoring algorithms need more treatment and are detailed in this section.

Difficulty is represented as a value 1-10. As difficulty get harder, the starting speed of the enemies gets faster. Also more enemies will fire more often.

Scoring is detailed as follows:

1. Killing a wimpy type earns the 10 player points.

[pic] He dies in one hit. He can not fire.

2. Killing a stubborn type earns the 20 player points.

[pic] He dies in two hits. He can not fire.

3. Killing an aggressive type earns the 30 player points.

[pic] He dies in one hit. He can fire.

4. Killing a titan type earns the player 150 points.

[pic] He dies in two hits. He can fire.

Each level has different configurations of these baddies. Adding up to a unique point total.

DESIGN PHASE II: IN DETAIL

The training file for this neural network is produced by the Java code. Each time the game is run the Java code updates the history file accordingly.

The feature space I chose is:

• Games Played – the total number of games played by this player

• Total Score- the total combined score of all games played by this player

• Avg. Score – the average score the player has reached over all games played

• Level Reached – the level reached on the last game played by this player

• High Score – the highest score the player has ever reached

The sole class is:

• Difficulty – the difficulty for the next game

The neural network described in this section was created by Professor Hu and was modified to model a complex function that fit my configuration best.

As we have done in the past, I will examine different configurations to determine the best fit model.

Determination of correlation of learning rate, momentum, # of hidden nodes, and # of layers:

Results of TEN trialS each h=5, 3 layers, 500 epochs or converge)

| |[pic] |

|Conditions | |

|Classification Rate | |

| | |

|(=0.01, µ=0 | |

|85.7143 | |

| | |

|(=0.1, µ=0 | |

|94.0476 | |

| | |

|(=0.2, µ=0 | |

|84.5538 | |

| | |

|(=0.4, µ=0 | |

|84.5138 | |

| | |

|(=0.8, µ=0 | |

|84.5028 | |

| | |

|(=0.01, µ=0.8 | |

|92.8571 | |

| | |

|(=0.1, µ=0.8 | |

|95.2381 | |

| | |

|(=0.2, µ=0.8 | |

|85.7643 | |

| | |

|(=0.4, µ=0.8 | |

|84.5238 | |

| | |

|(=0.8, µ=0.8 | |

|83.3333 | |

| | |

| | |

Results of TEN trialS each(Default L=3, (=0.1, µ=0.8, 500 epochs or converge)

| |[pic] |

| | |

|Conditions | |

|Classification Rate | |

| | |

|h=2 | |

|94.0476 | |

| | |

|h=5 | |

|95.2381 | |

| | |

|h=8 | |

|95.0232 | |

| | |

|h=11 | |

|96.4286 | |

| | |

|h=14 | |

|95.4422 | |

| | |

|h=17 | |

|96.0404 | |

| | |

|h=20 | |

|85.7143 | |

| | |

Results of TEN trialS each(Default h=11, (=0.1, µ=0.8, 500 epochs or converge)

| |[pic] |

| | |

|Configuration | |

|Classification Rate | |

| | |

|5-11-1 | |

|96.4092 | |

| | |

|5-11-11-1 | |

|95.2257 | |

| | |

|5-11-11-11-1 | |

|97.6056 | |

| | |

| | |

Fine tuning of learning rate was performed with no change in alpha.

Final Configuration Selected:

Format: 5-11-11-11-1

Parameters: (=0.10, µ=0.8

Classification Rate for Training Samples: 97.6190

The testing of this neural network is detailed in the results section.

PLAYER SELECTION

Player selection also became an important part of the process. Choice of players for each set was crucial because this choice would adversely effect my results if done poorly. Because of limited resources-players-I could not really afford the luxury of looking around for players who have never played the game space invaders(unbiased inputs). I also could not select as many players to play my game as I would like because it was around exam time, and also not many people want to play a not-so-fun terrible implementation of Space Invaders. There were 4 players that were used for the training set and one player that was reserved for the testing set. The player’s selected for training and testing of the adaptive difficulty network are shown below.

|Player |Description of Player/Set Selection |

|[pic] |Training Set. |

|Lewis |It was easiest for myself to be allocated to both sets. |

| |After all, I must have time to do my own project. |

| |Hobbies: |

| |Neural Network Computing |

| |Computer Architecture. |

|[pic] |Training Set. |

|Monica |My girlfriend had better play a few dozen games. |

| |Hobbies: |

| |Hockey |

| |Cooking |

| |Alien Zapping |

|[pic] |Training Set |

|Dave |Good friend Dave. Down with his project! |

| |Hobbies: |

| |Graphics |

| |Neural Network Computing |

|[pic] |Training Set |

|Greg |Good Friend Greg. ECE Major |

| |He is studying abroad next semester. |

| |Hobbies: |

| |Worrying About Tests |

| |DSP |

|[pic] |Testing Set |

|Chen |One of the coolest guys I know. Completely untainted in|

| |terms of Space Invaders (never has played the game). |

| |Hobbies: |

| |Table Tennis |

| |Operating Systems |

DATA GATHERING

Each player played a total of 21 games. They were forced to choose the lowest difficulty on their first game. From then on they could choose whatever difficulty they felt most comfortable with. They were told to “focus on the difficulty level while playing the game.” They were also required to think for 15 seconds between games and think about what difficulty they would choose next. This forced them into not making just a random choice but a more educated one.

RESULTS

Here is a listing of my testing results.

|Test Vector |Target Difficulty |Acquired Difficulty |

|1 |1 |3 |

|2 |1 |2 |

|3 |1 |3 |

|4 |3 |3 |

|5 |3 |4 |

|6 |3 |4 |

|7 |3 |5 |

|8 |5 |5 |

|9 |5 |5 |

|10 |5 |5 |

|11 |5 |5 |

|12 |5 |5 |

|13 |4 |5 |

|14 |5 |5 |

|15 |6 |6 |

|16 |6 |6 |

|17 |7 |6 |

|18 |6 |6 |

|19 |5 |5 |

|20 |6 |4 |

|21 |5 |5 |

The neural network was right: 12/21 times =57%. There was error, as I expected there would be. This is due to the simple fact that everyone likes their games differently, and all we can hope to do is get a feel for what an average person would choose for difficulty. To get the feel for what an individual person would choose for difficulty you would have to train the neural network while they are playing which completely defeats the purpose in the first place.

CONCLUSION

My neural network can predict with reasonable accuracy. As I stated earlier, in doing this project I was not looking for 100% accuracy, I did not have the amount of data samples necessary nor unbiased players. People choosing what difficulty they want introduces a bias as well, which was probably the dominating source of the error in the network- (a variance issue).

The results could be made better through:

1. More Samples

More Samples yields better results because you have more data to interpolate with.

2. Larger Feature Space (ie. Time from start of game to end of game, Player ID, etc. )

More inputs yields better results because you are adding a dimension of data to the problem.

3. Introducing Feedback(Possibility)

I wanted my results to be untainted by feedback of old difficulty as an input into the neural network. I thought that perhaps the classification would be dominated by the old difficulty and thus an accurate fit could never be made. But it is a possibility that you could find a model that fits this feature along with all other features.

Overall I think the project was a large success. I’ve never heard of adaptive difficulty in gaming before. Maybe someone else has proposed such an idea. But I think it is definitely an idea worth looking into if a company has the time and money to implement such an idea.

SCREEN CAPTURES FROM THE GAME

|[pic] |[pic] |

|(1) Title Screen Animation |(2) Blinking Title Screen(waiting for user to start) |

|[pic] |[pic] |

|(3) High Score Screen |(4) Score Table Screen |

|[pic] |[pic] |

|(5) 1st board |(6) 1st board (almost dead) |

|[pic] |[pic] |

|(7) 2nd board |(8) 3rd board |

|[pic] |[pic] |

|(9) 3rd board |(10) 4th board |

APPENDIX: CODE

This code is given open source. Please don’t take and replicate without my or Professor Hu’s expressed permission.

[pic] Professor Yu Hen Hu: hu@engr.wisc.edu

Matlab Source:

In the project attachment is the matlab source for the program. These files were initially created by Professor Hu. Please see for a listing of these files. (I adapted his initial files to suit the needs of my application.)

Java Source:

The java source is made available in the project attachment as well. Don’t replicate without my permission (it isn’t hard to get...just ask me first).

I wouldn’t really use the files for learning purposes, as there are probably countless better ways to make this game. My version is slow and a bit buggy. I have not taken a graphics course, so I was going off my knowledge in elementary Java, data structures, and operating systems when making this game.

REFERENCES

(1) The Classic Arcade Games Shrine-SpaceInvaders: website:



(2) Yu Hen Hu; ECE/CS/ME 539 class notes: Introduction to Artificial Neural Network and Fuzzy Systems; Department of Electrical and Computer Engineering, UW-Madison Fall 2001.

(3) Neural Networks: A Comprehensive Foundation, Simon Haykin, Prentice Hall, New Jersey, second edition, 1999.

(4) Neural Network Design: An Object Oriented Approach Williams, J. (1992) PC AI, 6(3), 23.

(5) Applying Neural Networks: Part V: Integrating A Trained Neural Network Into An Application Klimasauskas, C. (1991) PC AI, 5(5), 36.

(6) B. Widrow, et. al, “Adaptive Noise Canceling: Principles and Applications, “ Proc. IEEE, vol 63. pp. 1692-1716 Dec 1975

-----------------------

•Move your base left or right to shoot the endless waves of aliens marching towards earth.

•There are four buildings (shields) that you can hide behind, but eventually they will be destroyed either by enemy missiles or by the enemies themselves.

•The aliens' descent quickens as you eliminate them.

•You have 3 lives (3 tries to eliminate the aliens). If these lives run out the game is over.

•The Aliens may or may not shoot at you depending on their capabilities. Certain aliens have these capabilities.

•It may take multiple hits to destroy an enemy again depending on the alien’s capabilities.

•A life is expended when the alien fleet reach the final row and have thus invaded earth. A life is also expended when an enemy touches you or when an enemy hits you with a projectile.

•Shoot the flying saucer for extra points.

-----------------------

.

.

.

.

.

.

.

.

.

................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download