-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathREADME
181 lines (139 loc) · 8.31 KB
/
README
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
University of Eastern Finland
Artificial Intelligence 2022
"Stefan's group"
██████╗ ██████╗ ██████╗ ██╗███████╗ ██████╗████████╗
██╔══██╗██╔══██╗██╔═══██╗ ██║██╔════╝██╔════╝╚══██╔══╝
██████╔╝██████╔╝██║ ██║ ██║█████╗ ██║ ██║
██╔═══╝ ██╔══██╗██║ ██║██ ██║██╔══╝ ██║ ██║
██║ ██║ ██║╚██████╔╝╚█████╔╝███████╗╚██████╗ ██║
╚═╝ ╚═╝ ╚═╝ ╚═════╝ ╚════╝ ╚══════╝ ╚═════╝ ╚═╝
███╗ ██╗███████╗██╗ ██╗██████╗ █████╗ ██╗ ██╗███████╗██████╗
████╗ ██║██╔════╝██║ ██║██╔══██╗██╔══██╗██║ ██║██╔════╝██╔══██╗
██╔██╗ ██║█████╗ ██║ ██║██████╔╝███████║██║ ██║█████╗ ██████╔╝
██║╚██╗██║██╔══╝ ██║ ██║██╔══██╗██╔══██║██║ ██║██╔══╝ ██╔══██╗
██║ ╚████║███████╗╚██████╔╝██████╔╝██║ ██║╚██████╔╝███████╗██║ ██║
╚═╝ ╚═══╝╚══════╝ ╚═════╝ ╚═════╝ ╚═╝ ╚═╝ ╚═════╝ ╚══════╝╚═╝ ╚═╝
██████╗ ██████╗ ██████╗ ██████╗ ██╗ ██████╗██╗ ██╗
██╔══██╗██╔══██╗██╔═══██╗██╔══██╗██║██╔════╝╚██╗ ██╔╝
██████╔╝██████╔╝██║ ██║██║ ██║██║██║ ███╗╚████╔╝
██╔═══╝ ██╔══██╗██║ ██║██║ ██║██║██║ ██║ ╚██╔╝
██║ ██║ ██║╚██████╔╝██████╔╝██║╚██████╔╝ ██║
╚═╝ ╚═╝ ╚═╝ ╚═════╝ ╚═════╝ ╚═╝ ╚═════╝ ╚═╝
+--------------+
| Team members |
+--------------+
Štefan Kando - lead developer, team leader
Quazi Shahidul Islam - pair programmer, documentation
Samina Yasmin - documentation
+----------+
| Abstract |
+----------+
In our group, we found interest in artificial intelligence playing games.
We see the idea of a machine playing a game meant for a human as fascinating.
For this project, we have decided to make an artificial intelligence for
one of the best-selling games in the world - Tetris.
Jonas Neubauer was a seven-time champion in Classic Tetris World Championship (CTWC).
He died from sudden cardiac arrest in 2021 at the age of 39.
This project is meant to be a tribute to him.
Although at the current state, the AI is not half as good as him,
but with further development, it has the potential to get close to his skill.
This project focuses on the NES version of Tetris, released in 1984.
This version is one of the most popular and recognizable among the Tetris
community and has been selected as the version on which the CTWC is played
yearly even now, after nearly 40 years.
This application is capable of reading the data from an NES emulator running
NES Tetris, figure out an "optimal" placement and send the output as
keystrokes to the emulator.
+------------+
| How to use |
+------------+
To run the application in this state, you need a Windows 10 machine
with a 1920x1080 screen on a 100% scale (not enlarged).
You also need a Mesen NES emulator: https://www.mesen.ca/
running NES Tetris: https://www.emulatorgames.net/roms/nintendo/tetris/
The controls need to be as follows:
D-pad - WASD
B - J
A - L
Start - I
Run the emulator fullscreen windowed, and get to the level selection.
Scroll with D-pad to level 5 and run main.py.
You have 3 seconds to return to the emulator.
After 3 seconds, the algorithm will battle to its last breath for the world record.
Demo video: https://www.youtube.com/watch?v=VEWS5IWhJ1E
+-------------------+
| How does it work? |
+-------------------+
CV:
In this state, the CV works by analysing exact pixels.
It has a defined anchor point in the top left corner of the playing field,
from where it analyses the centre of each box in a 10x20 grid.
If the box is empty, the centre of an empty box will have a grayscale value of 0 exactly.
Any grayscale value higher than 0 is marked as a taken box.
CV algorithm also analyses the first two rows to determine what Tetromino (piece) is being held.
It also analyses the "NEXT" piece box and determines what piece goes next.
"NEXT" box analysis works based on distinguisher pixels.
Each piece has 1-3 distinguisher pixels. If all are active for one piece,
the algorithm is certain that this piece is in the "NEXT" box.
In this state, this does not have other use than telling the algorithm
what piece it holds if it fails to find out from the first two rows (not catching the exact frame).
If the first two rows have any boxes active in them, it tells the AI to "do stuff".
AI:
The artificial intelligence algorithm takes the current field
state and the currently held piece as input.
Then it tries every possible position for the piece by brute force,
taking both rotation and position into account. For every position,
it calculates the reverse fitness and this way it finds out the rotation
and position with the lowest reverse fitness (called "badness" in the code).
The reversed fitness is calculated by these factors:
- height of the field
- N of holes in the field
- N of blocks above holes
- "bumpiness" of the field - mean of difference between heights of each column
Each factor has its own multiplier, which was only set manually at the moment.
A genetic algorithm can be implemented to improve these multipliers,
but we did not manage to make it in the given time. :(
The algorithm then rotates the piece as needed. Every Tetromino has its own anchor point,
so the algorithm can calculate how much it has to move the piece to get it to the desired position.
It then sends the amount of keystrokes to the emulator and waits for the next input from the CV.
+----------------+
| Used libraries |
+----------------+
- opencv-python (cv2) - for computer vision
- pyautogui - for making a screenshot
- win32api, win32con - for output functions
- json - for loading and writing to json files
- random (for generating random pieces for debug)
- array
- math
- time
- numpy
+-------+
| Files |
+-------+
main.py
- Main file, run this script to run the algorithm
- Check and edit parameters in this file
train.py
- File where the genetic algorithm would have been implemented :(
gamemanager.py
- File containing GameManager class with main
game mechanics and functions implemented
tetromino.py
- File containing Tetromino class, with attributes and functions
regarding a Tetromino (Tetris piece)
ai.py
- File containing AI class and functions
cv.py
- File containing CV class and functions
output.py
- File containing output (keystroke) functions
distinguishers.json
- File containing pixel distinguishers for the "NEXT" box
- Keys are Tetromino IDs, content is the distinguisher pixel
coordinates ([x,y])
multipliers.json
- File containing reverse fitness multipliers
- Keys are reverse fitness factors, values are the multipliers
- Used for loading the multipliers to the AI, would be used
to save them during training