-
Notifications
You must be signed in to change notification settings - Fork 0
/
AIVenceDummys.cc
executable file
·331 lines (300 loc) · 10.2 KB
/
AIVenceDummys.cc
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
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
#include "Player.hh"
/**
* Write the name of your player and save this file
* with the same name and .cc extension.
*/
#define PLAYER_NAME VenceDummys
struct PLAYER_NAME : public Player {
/**
* Factory: returns a new instance of this class.
* Do not modify this function.
*/
static Player* factory () {
return new PLAYER_NAME;
}
/**
* Types and attributes for your player can be defined here.
*/
enum CellContent {
cWaste, // Waste is in the cell
cDead, // A dead unit is in the cell
cFood, // Food is in the cell
cZombie, // A zombie is in the cell
cEnemy, // An enemy is in the cell
cUnit, // A friendly unit is in the cell
cEmptyOwned, // Cell is empty and owned by me
cEmptyNotOwned, // Cell is empty and not owned by me (owned by another player or not owned by anyone)
};
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<bool> VB;
typedef vector<VB> VVB;
typedef pair<int, int> P;
typedef vector<P> VP;
typedef vector<VP> VVP;
typedef vector<CellContent> VC;
typedef vector<VC> VVC;
const int n = 60;
vector<Dir> dirs = {Up, Down, Left, Right};
VI units; // Vector that contains my units
set<int> set_units; // Set that contains my units (from units)
VVC mapC = VVC(n, VC(n)); // Matrix that contains all cells content
/**
* Play method, invoked once per each round.
*/
CellContent cellToCellContent(const Cell& cell) {
if (cell.type == Waste) return cWaste;
if (cell.food) return cFood;
// An empty cell
if (cell.id == -1) {
if (cell.owner != me()) return cEmptyNotOwned;
return cEmptyOwned;
}
Unit u = unit(cell.id);
if (u.type == Zombie) return cZombie;
if (u.type == Dead) return cDead;
if (u.player == me()) return cUnit;
return cEnemy;
}
void getMapContent() {
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
mapC[i][j] = cellToCellContent(cell(i, j));
}
}
}
void getMyUnits() {
set_units.clear();
units = alive_units(me());
for (auto id : units) set_units.insert(id);
}
void getRoundData() {
getMapContent();
getMyUnits();
}
struct targetPosition {
Pos p;
Dir d;
int dist;
};
// Returns Dir and Pos to the closest Food, Zombie or Enemy.
// If it does not find any, returns Dir and Pos of first available cell or first empty not owned cell.
Dir findClosestUnit(const Unit& u, const VVI& distances, VVB& visited, queue<targetPosition>& q, Pos& targetPos, int& targetDist) {
// bool isInfected = u.rounds_for_zombie != -1;
// int stepsPossibleAsZombie = u.rounds_for_zombie;
int max_bfs = 20;
int str = strength(me());
// if (isInfected) max_bfs = 10;
// If we don't find anything, go to the first available cell or first empty not owned cell
bool found = false;
targetPos = q.front().p;
Dir dirToEmptyCell = q.front().d;
targetDist = q.front().dist;
while (not q.empty() and (max_bfs != q.front().dist or not found)) {
Pos p = q.front().p;
Dir d = q.front().d;
int dist = q.front().dist;
q.pop();
if (visited[p.i][p.j]) continue;
visited[p.i][p.j] = true;
if (mapC[p.i][p.j] == cWaste) continue;
// If it is already targeted, only go if your distance is less
if (distances[p.i][p.j] != -1) {
if (dist < distances[p.i][p.j]) {
targetPos = p;
targetDist = dist;
return d;
}
continue;
}
if (mapC[p.i][p.j] == cFood or mapC[p.i][p.j] == cZombie) {
targetPos = p;
targetDist = dist;
return d;
}
if (mapC[p.i][p.j] == cEnemy) {
int enemyStrength = strength(unit(cell(p).id).player);
// If more than 28,6% chance of winning the fight, GO. If I attack first, would have 0.3+0.7*chance of winning. Rn is at 50%.
double chance = 0.286;
if ((1-chance)*str >= chance*enemyStrength) {
targetPos = p;
targetDist = dist;
return d;
}
// Should I reconsider to always attacking? If I go to a position close to the enemy, I would be killed 100% bc he attacks first and has more chances of winning the fight
continue;
}
// At the moment, we do not follow our infected units
// if (mapC[p.i][p.j] == cUnit) {
// // If it's infected, go
// if (unit(cell({p.i, p.j}).id).rounds_for_zombie != -1 and dist >= unit(cell({p.i, p.j}).id).rounds_for_zombie) {
// targetPos = p;
// targetDist = dist;
// return d;
// }
// continue;
// }
if (mapC[p.i][p.j] == cDead) {
// If we arrive 1 step early, just at time, or later, GO
if (dist >= unit(cell({p.i, p.j}).id).rounds_for_zombie) {
targetPos = p;
targetDist = dist;
return d;
}
continue;
}
// if (isInfected) {
// if (map[p.i][p.j] == cDead) {
// if (dist >= unit(cell({p.i, p.j}).id).rounds_for_zombie and dist <= stepsPossibleAsZombie) {
// targetPos = p;
// return d;
// }
// else continue;
// }
// else if (map[p.i][p.j] == cFood) {
// if (dist <= stepsPossibleAsZombie) {
// targetPos = p;
// return d;
// }
// }
// else if (map[p.i][p.j] == cZombie or map[p.i][p.j] == cEnemy) {
// targetPos = p;
// return d;
// }
// }
// else {
// // Dead unit
// if (map[p.i][p.j] == cDead) {
// // If we arrive 1 step early, just at time, or later, GO
// if (dist >= unit(cell({p.i, p.j}).id).rounds_for_zombie) {
// targetPos = p;
// return d;
// }
// // If we arrive 2 or more steps early, go to another direction
// else continue;
// }
// // If we found what we want, go there
// if (map[p.i][p.j] == cFood or map[p.i][p.j] == cZombie) {
// targetPos = p;
// return d;
// }
// }
// Find first empty not owned cell
if (not found and mapC[p.i][p.j] == cEmptyNotOwned) {
dirToEmptyCell = d;
targetPos = p;
targetDist = dist;
found = true;
}
// Check all four directions in a random order: Up, Down, Left and Right
random_shuffle(dirs.begin(), dirs.end());
for (auto dir : dirs) {
Pos newPos = p + dir;
if (pos_ok(newPos) and not visited[newPos.i][newPos.j]) q.push({newPos, d, dist + 1});
}
}
return dirToEmptyCell;
}
// Mark position as Targeted and return the direction to go there
Dir findNextMove(const Unit& u, const VVI& distances, Pos& targetPos, int& targetDist) {
VVB visited(n, VB(n, false));
queue<targetPosition> q;
visited[u.pos.i][u.pos.j] = true;
// Initial movements
random_shuffle(dirs.begin(), dirs.end());
for (auto d : dirs) {
Pos newPos = u.pos + d;
if (pos_ok(newPos) and mapC[newPos.i][newPos.j] != cWaste) {
// If there's an enemy next to us, prioritize movement to kill him.
if (mapC[newPos.i][newPos.j] == cEnemy) {
targetPos = newPos;
targetDist = 1;
return d;
}
q.push({newPos, d, 1});
}
}
// If only one direction is possible, go there
if (q.size() == 1) {
targetPos = q.front().p;
targetDist = q.front().dist;
return q.front().d;
}
return findClosestUnit(u, distances, visited, q, targetPos, targetDist);
}
struct Movement {
int id;
Dir d;
int dist;
};
struct Compare {
bool operator() (const Movement& a, const Movement& b) const {
if (a.dist != b.dist) return a.dist > b.dist;
return a.id < b.id;
}
};
void moveUnits() {
// Contains first movements to perform
vector<Movement> priorityMovements;
// Contains last movements to perform
vector<Movement> lastMovements;
// Contains movements to performs with no priority
map<int, Dir> nextMovements;
// Contains the id of the unit planning to go to that position
VVI ids = VVI(n, VI(n, -1));
// If value is -1, no unit plans to go to that position
// Else, there is a unit planning to go to that position and the value is the steps it has to take to get there
VVI distances = VVI(n, VI(n, -1));
while (not set_units.empty()) {
auto it = set_units.begin();
int id = *it;
set_units.erase(it);
Unit u = unit(id);
Pos targetPos;
int targetDist;
Dir d = findNextMove(u, distances, targetPos, targetDist);
if (targetDist == 1 and (mapC[targetPos.i][targetPos.j] == cEnemy or mapC[targetPos.i][targetPos.j] == cFood)) {
Movement m;
m.d = d;
m.id = id;
m.dist = targetDist;
priorityMovements.push_back(m);
}
else if (targetDist == 2 and mapC[targetPos.i][targetPos.j] == cEnemy) {
Movement m;
m.d = d;
m.id = id;
m.dist = targetDist;
lastMovements.push_back(m);
}
// If we are going to an already targeted position, recalculate the movement to the unit that was going there
else if (distances[targetPos.i][targetPos.j] != -1) {
nextMovements.erase(ids[targetPos.i][targetPos.j]);
set_units.insert(ids[targetPos.i][targetPos.j]);
nextMovements.insert({id, d});
}
else nextMovements.insert({id, d});
// Update values
ids[targetPos.i][targetPos.j] = id;
distances[targetPos.i][targetPos.j] = targetDist;
}
// First commands where dist == 1 and target is food or enemy
for (auto movement : priorityMovements) move(movement.id, movement.d);
// Next commands
for (auto movement : nextMovements) {
int id = movement.first;
Dir d = movement.second;
move(id, d);
}
// Last commands where dist == 2 and target is enemy. Used to counterattack
for (auto movement : lastMovements) move(movement.id, movement.d);
}
virtual void play () {
getRoundData();
moveUnits();
}
};
/**
* Do not modify the following line.
*/
RegisterPlayer(PLAYER_NAME);