by: Lewis Sykalski
CLASS: ECE 539
PROF: Yu Hen HU
SPACE INVADERS ADAPTIVE DIFFICULTY
A NEURAL NETWORK APPROACH
1
INTRODUCTION:
PROPOSAL:
HISTORY OF GAME:
HOW TO PLAY:
OVERVIEW OF DESIGN:
DESIGN PHASE I: IN DETAIL:
SCORING AND DIFFICULTY:
DESIGN PHASE II: IN DETAIL:
PLAYER SELECTION:
DATA GATHERING:
RESULTS:
CONCLUSION:
SCREEN CAPTURES FROM THE GAME:
APPENDIX: CODE:
REFERENCES:
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 1978and 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 <name> <difficulty> >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.
- Added code for difficulty feature.
- Added sound to the game via AudioManager Class.
- Wrote Highscore method and screen
- Wrote History method for keeping track of certain variables useful to the neural network.
Design Phase II(Space Invaders w/ Adaptive Difficulty):
- Downloaded and adapted Professor Hu’s MLP back propagation files to suit the type of network necessary for adaptive difficulty.
- Scaled inputs.
- Adapted to one hot method.
- Tested
Below is a flowchart showing the design flow.
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:
- 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.
- The bullets then are fired if the probability is met and if the specific type of alien can fire them.
- The method then checks for a shield and bullet intersection—indicating a hit. If so it removes the shield from the fleet of shields.
- Checking for a hero bullet and an alien now occurs. If the alien is dead - it will remove that alien from the fleet.
- 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:
- = move left –moves the hero one grid space to the left.
- = move right –moves the hero one grid space to the right.
- 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:
- Killing a wimpy type earns the 10 player points.
He dies in one hit. He can not fire.
- Killing a stubborn type earns the 20 player points.
He dies in two hits. He can not fire.
- Killing an aggressive type earns the 30 player points.
He dies in one hit. He can fire.
- Killing a titan type earns the player 150 points.
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)
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)
Conditions
/ Classification Rateh=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)
Configuration / Classification Rate5-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 SelectionLewis / Training Set.
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.
Monica / Training Set.
My girlfriend had better play a few dozen games.
Hobbies:
- Hockey
- Cooking
- Alien Zapping
Dave / Training Set
Good friend Dave. Down with his project!
Hobbies:
- Graphics
- Neural Network Computing
Greg / Training Set
Good Friend Greg. ECE Major
He is studying abroad next semester.
Hobbies:
- Worrying About Tests
- DSP
Chen / Testing Set
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 Difficulty1 / 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:
- More Samples
More Samples yields better results because you have more data to interpolate with.