This project is part of the ENGF0034 Design and Professional Skills module at UCL.
The goal is to write an AI player for a modified version of Tetris which can automatically play the game and perform well against other student' bots on the offical UCL server.
This version of Tetris is slightly different to the normal version:
- 400 Tetrominoes
- 10 discards
- 5 bombs (to clear surrounding blocks)
1 point for each step in the Tetris game (where a block moves down a space)
| Lines Cleared | Points |
|---|---|
| 1 | 25 |
| 2 | 100 |
| 3 | 400 |
| 4 | 1600 |
Code I wrote is in player.py, genetic_algorithm.py and headless.py. All other files existed already to model and render the game.
- Heurstic-based board evaluation
- Beam Search (width = 4)
- Genetic Algorithm to find optimal weights
I intially used 4-5 heuristics and weights alongside the real scores (i.e. 25 points for one line...) to reward line clears. This worked fairly well for an intial implementation.
I then introduced a few more weights and made a novel one that returned the number of points total if as many 'I' shaped blocks came in a row as needed. This meant that board states that gave opportunity for highly scoring Tetrises would be favoured and the score was likely achievable. By this I mean, if there were 3 almost cleared lines a line with multiple gaps then an almost cleared line, this would not be anywhere near as favourable as 4 almost cleared lines. This hueristic really helped the AI 'understand' the relevance and importance of lining up for a Tetris. I started playing around with the line clear weights at this point and found that discouraging 1 or 2 line clears also helped Tetris setups.
I then included a genetic algorithm to tune weights better than I could by hand which boosted my score further. I intially ran this with a population of 10 but I increased this to 40 for more variation. I had to include some features like stagnation detection (and management) as well as random wild mutations every few generations to prevent the algorithm from settling on something moderately good but not incredible.
Finally, I implemented a beam search which took the best n boards from a first block placement and then simulated next block placement for each board and then took the best combined set of moves and played the first move. I had to rerun my genetic algorithm (which took a considerate amount longer) but it really helped my score.
This version of Tetris can be played manually by running:
python visual.py -m↑ - rotate clockwise
→ - move right
← - move left
↓ - move down
Space - drop the block
z - rotate anticlockwise
x - rotate clockwise
b - switch next piece for bomb
d - discard current piece
Esc - exit game