Created
April 17, 2016 20:51
-
-
Save AlexEne/701494660cc9e72242168af513527a4c to your computer and use it in GitHub Desktop.
WIP
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <iostream> | |
#include <string> | |
#include <vector> | |
#include <algorithm> | |
#include <iomanip> | |
#include <deque> | |
#include <set> | |
#include <map> | |
#include <chrono> | |
using namespace std; | |
class Timer | |
{ | |
public: | |
Timer(const char* name) : beg_(clock_::now()), name_(name) {} | |
void reset() { beg_ = clock_::now(); } | |
double elapsed() const { | |
return std::chrono::duration_cast<ms_> | |
(clock_::now() - beg_).count(); | |
} | |
void print_elapsed() | |
{ | |
fprintf(stderr, "%s: %.2f\n", name_.c_str(), elapsed()); | |
} | |
~Timer() | |
{ | |
print_elapsed(); | |
} | |
private: | |
string name_; | |
typedef std::chrono::high_resolution_clock clock_; | |
typedef std::chrono::duration<double, std::milli> ms_; | |
std::chrono::time_point<clock_> beg_; | |
}; | |
struct Cell | |
{ | |
float weight; | |
int occupant; //-1 if free | |
}; | |
const int Width = 30; | |
const int Height = 20; | |
void ClearPlayer(Cell board[Height][Width], int playerID) | |
{ | |
for(int i = 0; i < Height; ++i) | |
{ | |
for(int j = 0; j < Width; ++j) | |
{ | |
//Clear occupant since the guy died. | |
if(board[i][j].occupant == playerID+1) | |
board[i][j].occupant = 0; | |
} | |
} | |
} | |
void AddPlayerPosition(Cell board[Height][Width], int playerID, int x, int y) | |
{ | |
board[y][x].occupant = playerID+1; | |
} | |
void PrintBoard(Cell board[Height][Width]) | |
{ | |
//cerr << setiosflags(ios::left); | |
//cerr << setfill(' '); | |
//cerr << setw(2); | |
for(int i = 0; i < Height; ++i) | |
{ | |
for(int j = 0; j < Width; ++j) | |
cerr << setw(2) << board[i][j].occupant << " "; | |
cerr << endl; | |
} | |
cerr << endl << "Weights:" << endl; | |
for(int i = 0; i < Height; ++i) | |
{ | |
for(int j = 0; j < Width; ++j) | |
cerr << setw(2) << (int)board[i][j].weight << " "; | |
cerr << endl; | |
} | |
cerr << resetiosflags(ios::left); | |
} | |
void GenerateWeights(Cell board[Height][Width]) | |
{ | |
for(int i = 0; i < Height; ++i) | |
for(int j = 0; j < Width; ++j) | |
board[i][j].weight = 0.0f; | |
for(int i = 0; i < Height; ++i) | |
{ | |
for(int j = 0; j < Width; ++j) | |
{ | |
if(board[i][j].occupant != 0 || (i == Height-1) || (j == Width-1) || j == 0 || i == 0) | |
{ | |
//start decay of weights | |
float weight = 16.0f; | |
int step = 0; | |
while(step < 3) | |
{ | |
weight = weight/3; | |
//Top side | |
int row = i - step; | |
if(row >= 0 && row < Height) | |
{ | |
for(int x = j + step; x >= j - step; x--) | |
if(x >= 0 && x < Width ) | |
board[row][x].weight += weight; | |
} | |
//Left side | |
int column = j - step; | |
if(column >= 0 && column < Width) | |
{ | |
for(int y = i - step + 1; y <= i + step - 1; y++) | |
if(y >= 0 && y < Height) | |
board[y][column].weight += weight; | |
} | |
//Bottom side | |
row = i + step; | |
if(row >= 0 && row < Height) | |
{ | |
for(int x = j - step; x <= j + step; x++) | |
if( x >= 0 && x < Width ) | |
board[row][x].weight += weight; | |
} | |
//Right side | |
column = j + step; | |
if( column >= 0 && column < Width ) | |
{ | |
for(int y = i - step + 1; y <= i + step - 1; y++) | |
if( y >= 0 && y < Height ) | |
board[y][column].weight += weight; | |
} | |
step++; | |
} | |
} | |
} | |
} | |
/* float weight = 8.0f; | |
for(int x = 0; x < Width; ++x) | |
{ | |
for(int offset = 0; offset < 3; ++ offset) | |
{ | |
board[offset][x].weight += weight; | |
board[Height-offset][x].weight += weight; | |
weight /= 2.0f; | |
} | |
} | |
weight = 8.0f; | |
for(int y = 0; y < Height; ++y) | |
{ | |
for(int offset = 0; offset < 3; ++offset) | |
{ | |
board[y][offset].weight += weight; | |
board[y][Width-offset].weight += weight; | |
weight /= 2.0f; | |
} | |
} | |
*/ | |
} | |
struct Point | |
{ | |
Point() | |
{ | |
x = y = 0; | |
cost = 0.0f; | |
} | |
Point(int _x, int _y) | |
{ | |
x = _x; | |
y = _y; | |
cost = 0.0f; | |
} | |
Point(int _x, int _y, float _cost) | |
{ | |
x = _x; | |
y = _y; | |
cost = _cost; | |
} | |
Point(const Point& other) | |
{ | |
x = other.x; | |
y = other.y; | |
cost = other.cost; | |
} | |
int x; | |
int y; | |
float cost; | |
}; | |
Point LastResortDestination(Cell board[Height][Width], Point myPosition); | |
vector<Point> g_BannedPositions; | |
std::ostream& dump(std::ostream &o, const Point& p) | |
{ | |
return o << " (" << p.x << ", " << p.y << ")"; | |
} | |
inline bool operator==(const Point& lhs, const Point& rhs) | |
{ | |
return lhs.x == rhs.x && lhs.y == rhs.y; | |
} | |
inline Point operator+(const Point& lhs, const Point& rhs) | |
{ | |
return Point(lhs.x+rhs.x, lhs.y+rhs.y); | |
} | |
inline Point operator-(const Point& lhs, const Point& rhs) | |
{ | |
return Point(lhs.x-rhs.x, lhs.y-rhs.y); | |
} | |
void Print(const Point& p) | |
{ | |
fprintf(stderr, "(%d, %d)", p.x, p.y); | |
} | |
void Print(const char* name, const vector<Point>& arr) | |
{ | |
fprintf(stderr, "%s size=%d: ", name, arr.size()); | |
for(const Point& p : arr) | |
{ | |
fprintf(stderr, "(%d, %d) ", p.x, p.y); | |
} | |
fprintf(stderr, "\n"); | |
} | |
#define USE_DIJ | |
vector<Point> GetPath(Cell board[Height][Width], Point start, Point dest) | |
{ | |
float Cost[Height][Width]; | |
for(int i = 0; i < Height; i++) | |
for(int j = 0; j < Width; ++j) | |
Cost[i][j] = 99999; | |
vector<Point> visited; | |
vector<Point> openList; | |
openList.reserve(100); | |
visited.reserve(100); | |
openList.push_back(start); | |
visited.push_back(start); | |
typedef pair<int, int> Key; | |
map< Key, Point > parents; | |
bool foundPath = false; | |
while(!openList.empty()) | |
{ | |
Point current = Point(0, 0, 1000.0f); | |
int min_idx = -1; | |
for(int i = 0; i < openList.size(); ++i) | |
{ | |
Point p = openList[i]; | |
if( p.cost < current.cost ) | |
{ | |
current = p; | |
min_idx = i; | |
} | |
} | |
if(min_idx != -1) | |
openList.erase(openList.begin() + min_idx); | |
if(current == dest) | |
{ | |
//cerr<<"Found path" << endl; | |
//Print("OpenList", openList); | |
foundPath = true; | |
break; | |
} | |
vector<Point> candidates = { Point(current.x, current.y-1), Point(current.x, current.y+1), | |
Point(current.x-1, current.y), Point(current.x+1, current.y) }; | |
//random_shuffle(candidates.begin(), candidates.end()); | |
for(Point& child : candidates) | |
{ | |
if( board[child.y][child.x].occupant == 0 | |
&& child.x >= 0 && child.y >= 0 && child.x < Width && child.y < Height) | |
{ | |
float testCost = board[child.y][child.x].weight + current.cost; | |
if( testCost< Cost[child.y][child.x]) | |
{ | |
Cost[child.y][child.x] = testCost; | |
parents[Key(child.x, child.y)] = current; | |
} | |
if(find(visited.begin(), visited.end(), child) == visited.end()) | |
{ | |
visited.push_back(child); | |
openList.push_back(child); | |
} | |
/* | |
cerr << "Current: "; Print(current); cerr << " Child: "; Print(child); cerr << endl; | |
cerr << "parents" << endl; | |
for(auto& p : parents) | |
{ | |
cerr << "(" << p.first.first << ", " << p.first.second << ") "; | |
cerr << "->"; | |
Print(p.second); | |
cerr << endl; | |
} | |
cerr << endl; | |
*/ | |
} | |
} | |
//Print("OpenList", openList); | |
//Print("Visited", visited); | |
} | |
vector<Point> path; | |
map<Key, Point>::iterator it; | |
if(foundPath) | |
{ | |
path.push_back(dest); | |
Point node = dest; | |
while( (it = parents.find(pair<int, int>(node.x, node.y))) != parents.end() ) | |
{ | |
path.push_back(it->second); | |
node = it->second; | |
} | |
} | |
reverse(path.begin(), path.end()); | |
return path; | |
} | |
const char* GenerateMove(const Point& start, const Point& dest) | |
{ | |
if(dest.x - start.x > 0) | |
return "RIGHT"; | |
if(dest.x - start.x < 0) | |
return "LEFT"; | |
if(dest.y - start.y < 0) | |
return "UP"; | |
if(dest.y - start.y > 0) | |
return "DOWN"; | |
return nullptr; | |
} | |
//Random valid path of minimum cost. | |
vector<Point> GetRandomPath(Cell board[Height][Width], Point myPosition) | |
{ | |
cerr<<"Getting random path" << endl; | |
int tries = 0; | |
vector<Point> path; | |
int minSize = 50000; | |
while(tries < 25) | |
{ | |
Point dest = Point(rand()%Width, rand()%Height); | |
vector<Point> test_path = GetPath(board, myPosition, dest); | |
if(test_path.size() > 1 && test_path.size() < minSize) | |
{ | |
minSize = test_path.size(); | |
path = test_path; | |
} | |
tries++; | |
} | |
return path; | |
} | |
bool IsValidMove(Cell board[Height][Width], Point pos) | |
{ | |
return pos.y >= 0 && pos.y < Height && pos.x >= 0 && pos.x < Width && board[pos.y][pos.x].occupant == 0 && find(g_BannedPositions.begin(), g_BannedPositions.end(), pos) == g_BannedPositions.end(); | |
} | |
bool visited[Height][Width]; | |
int DFS(Cell board[Height][Width], Point startPos, int currentDepth, int max = 10000, bool debug = false) | |
{ | |
Point directions[] = { Point(0, -1), Point(0, 1), Point(-1, 0), Point(1, 0)}; | |
int maxDepth = currentDepth; | |
if(currentDepth == 0) | |
{ | |
for(int i = 0; i < Height; ++i) | |
for(int j = 0; j < Width; ++j) | |
visited[i][j] = false; | |
} | |
#ifdef DEBUG_PRINT | |
cerr << maxDepth << endl; | |
#endif | |
visited[startPos.y][startPos.x] = true; | |
if (maxDepth > max) | |
return maxDepth; | |
for( Point& d : directions) | |
{ | |
Point p = startPos+d; | |
#ifdef DEBUG_PRINT | |
cerr << "Trying pos "; Print(p); cerr << endl; | |
#endif | |
if(IsValidMove(board, p) && visited[p.y][p.x] == false) | |
{ | |
//visited[p.y][p.x] = true; | |
int depth = DFS(board, p, currentDepth + 1, max, debug); | |
if( depth > maxDepth ) | |
maxDepth = depth; | |
} | |
} | |
//cerr << maxDepth << endl; | |
return maxDepth; | |
} | |
//Number of nodes reachable from startPos; | |
unsigned int BFS(Cell board[Height][Width], Point startPos, unsigned int maxNodes = 100000) | |
{ | |
deque<Point> openList; | |
openList.push_back(startPos); | |
int distance[Height][Width]; | |
for(int i = 0; i < Height; ++i) | |
for(int j = 0; j < Width; ++j) | |
distance[i][j] = -1; | |
distance[startPos.y][startPos.x] = 0; | |
unsigned int count = 0; | |
while(!openList.empty()) | |
{ | |
Point node = openList.front(); | |
openList.pop_front(); | |
Point directions[] = {Point(0, -1), Point(0, 1), Point(-1, 0), Point(1, 0)}; | |
for( Point& d : directions) | |
{ | |
Point p = node + d; | |
if(IsValidMove(board, p) && distance[p.y][p.x] == -1) | |
{ | |
distance[p.y][p.x] = distance[node.y][node.x] + 1; | |
count += 1; | |
if(count >= maxNodes) | |
return count; | |
openList.push_back(p); | |
} | |
} | |
} | |
return count; | |
} | |
int ChoosePathIdx(Cell board[Height][Width], const vector< vector<Point> >& paths, const vector<Point>& players) | |
{ | |
int min_idx = -1; | |
int min_len = 9999; | |
for(int i = 0; i < paths.size(); ++i) | |
{ | |
const vector<Point>& path = paths[i]; | |
//Print("CandidatePath", paths[i]); | |
if(path.size() < min_len) | |
{ | |
min_len = path.size(); | |
min_idx = i; | |
} | |
} | |
return min_idx; | |
} | |
int ChoosePathIdx3(Cell board[Height][Width], const vector< vector<Point> >& paths, const vector<Point>& players) | |
{ | |
int min_idx = -1; | |
int max_len = -1; | |
for(int i = 0; i < paths.size(); ++i) | |
{ | |
const vector<Point>& path = paths[i]; | |
//Print("CandidatePath", paths[i]); | |
if(path.size() > max_len) | |
{ | |
max_len = path.size(); | |
min_idx = i; | |
} | |
} | |
return min_idx; | |
} | |
inline bool CompareSizes(const vector<Point>& a, const vector<Point>& b) | |
{ | |
return a.size() < b.size(); | |
} | |
inline bool IsOnBoard(Point p) | |
{ | |
return p.x >= 0 && p.x < Width && p.y < Height && p.y >= 0; | |
} | |
int ChoosePathIdx2(Cell board[Height][Width], const vector< vector<Point> >& paths, const vector<Point>& players) | |
{ | |
Timer t("ChoosePathIdx2"); | |
int idx = -1; | |
int maxCount = -1; | |
Point possibleDirs[] = {Point(1, 0), Point(0, 1), Point(0, -1), Point(-1, 0)}; | |
for(int i = 0; i < paths.size(); ++i) | |
{ | |
const vector<Point>& path = paths[i]; | |
//Print("Candidate path", path); | |
if(path.size() <= 1) | |
continue; | |
int minCount = 99999; | |
for(const Point& player : players) | |
{ | |
for(const Point& dir : possibleDirs) | |
{ | |
Point p = player + dir; | |
if(IsOnBoard(p)) | |
{ | |
int prevOccupant = board[p.y][p.x].occupant; | |
int pathSpace = board[path[1].y][path[1].x].occupant; | |
board[p.y][p.x].occupant = 1; | |
board[path[1].y][path[1].x].occupant = 1; | |
int count = BFS(board, path[1]); | |
// fprintf(stderr, "path search BFS count (idx=%d): %d\n", i, count); | |
if(count < minCount) | |
{ | |
minCount = count; //Just take the minimum that we are left with if the enemy plays perfectly. | |
if( minCount < 10 ) | |
g_BannedPositions.push_back(p); | |
} | |
board[p.y][p.x].occupant = prevOccupant; | |
board[path[1].y][path[1].x].occupant = pathSpace; | |
} | |
} | |
} | |
if(minCount > maxCount) | |
{ | |
//Best of the worse choices. | |
maxCount = minCount; | |
idx = i; | |
} | |
} | |
fprintf(stderr, "Free cells: %d \n", maxCount); //best choice no matter if enemy plays perfectly. | |
if(maxCount < 10) | |
return -1; | |
return idx; | |
} | |
//Returns a path to annoy the closest player and kill him. | |
vector<Point> GetAnoyingPath(Cell board[Height][Width], vector<Point>& players, Point myPosition, const vector<Point>& candidateDestinations) | |
{ | |
Timer T("Destination Path search"); | |
vector< vector<Point> > paths; | |
for(const Point& p : candidateDestinations) | |
{ | |
if(!IsValidMove(board, p)) | |
continue; | |
//if(reachableNodes < 300) | |
{ | |
int prevOcupant = board[p.y][p.x].occupant; | |
board[p.y][p.x].occupant = 1; | |
int reachableNodes = BFS(board, myPosition); | |
int depth = BFS(board, p); | |
//fprintf(stderr, "MyReachableCount: %d, ReachableCount: %d\n", reachableNodes, depth); | |
board[p.y][p.x].occupant = prevOcupant; | |
if(depth < reachableNodes) | |
continue; | |
} | |
vector<Point> path = GetPath(board, myPosition, p); | |
if(path.size() > 1) | |
paths.push_back(path); | |
} | |
T.print_elapsed(); | |
sort(paths.begin(), paths.end(), CompareSizes); | |
int pathIdx = ChoosePathIdx2(board, paths, players); | |
fprintf(stderr, "PathIdx= %d\n", pathIdx); | |
if(pathIdx == -1) | |
{ | |
vector<Point> tmp; | |
tmp.push_back(myPosition); | |
tmp.push_back(LastResortDestination(board, myPosition)); | |
return tmp; | |
} | |
return paths[pathIdx]; | |
} | |
Point LastResortDestination(Cell board[Height][Width], Point myPosition) | |
{ | |
int maxDepth = 0; | |
Point dest; | |
Point candidates[] = {Point(1, 0), Point(0, 1), Point(0, -1), Point(-1, 0)}; | |
for(Point& c : candidates) | |
{ | |
Point p = myPosition+c; | |
if(!IsValidMove(board, p)) | |
continue; | |
int depth = DFS(board, p, 0); | |
//cerr << "Trying point: "; Print(p); cerr << " Depth: " << depth << endl; | |
if(depth > maxDepth) | |
{ | |
maxDepth = depth; | |
dest = p; | |
} | |
} | |
cerr << "Trying random shit. Max depth: " << maxDepth << " Dest: "; Print(dest); cerr << " " << GenerateMove(myPosition, dest) << endl; | |
return dest; | |
} | |
bool IsStuck(Cell board[Height][Width], Point player, Point movePos) | |
{ | |
Point directions[] = {Point(0, -1), Point(0, 1), Point(1, 0), Point(-1, 0)}; | |
int failed = 0; | |
bool killed = false; | |
for(Point& dir : directions) | |
{ | |
Point move = dir + player; | |
if(move == movePos) | |
{ | |
if(!IsValidMove(board, move)) | |
failed++; | |
killed = true; | |
} | |
} | |
return failed == 4 && killed; | |
} | |
bool IsStuck2(Cell board[Height][Width], Point player, Point movePos, Point myPos) | |
{ | |
if(IsValidMove(board, movePos)) | |
{ | |
int prevCount = DFS(board, player, 0); | |
int myPrevCount = DFS(board, myPos, 0); | |
board[movePos.y][movePos.x].occupant = 1; | |
int afterCount = DFS(board, player, 0); | |
int myAfterCount = DFS(board, myPos, 0); | |
board[movePos.y][movePos.x].occupant = 0; | |
fprintf(stderr, "prevCount: %d, afterCount: %d, myPrevCount: %d, myAfterCount: %d\n", prevCount, afterCount, myPrevCount, myAfterCount); | |
return afterCount < prevCount-15 && abs(myAfterCount-myPrevCount) < 20; | |
} | |
return false; | |
} | |
/** | |
* Auto-generated code below aims at helping you parse | |
* the standard input according to the problem statement. | |
**/ | |
int main() | |
{ | |
Cell Board[Height][Width]; | |
for(int i = 0; i < Height; ++i) | |
for(int j = 0; j < Width; ++j) | |
Board[i][j].occupant = 0; | |
Point destination(0, 0, 10000.0f); | |
srand(42); | |
bool firstTime = true; | |
vector<Point> prevPlayers; | |
// game loop | |
while (1) | |
{ | |
Timer t("Turn time"); | |
g_BannedPositions.clear(); | |
int N; // total number of players (2 to 4). | |
int P; // your player number (0 to 3). | |
Point myPosition; | |
vector<Point> players; | |
cin >> N >> P; cin.ignore(); | |
for (int i = 0; i < N; i++) | |
{ | |
int X0; // starting X coordinate of lightcycle (or -1) | |
int Y0; // starting Y coordinate of lightcycle (or -1) | |
int X1; // starting X coordinate of lightcycle (can be the same as X0 if you play before this player) | |
int Y1; // starting Y coordinate of lightcycle (can be the same as Y0 if you play before this player) | |
cin >> X0 >> Y0 >> X1 >> Y1; cin.ignore(); | |
fprintf(stderr, "X0=%d Y0=%d X1=%d Y1=%d\n", X0, Y0, X1, Y1); | |
if(X1 == -1) | |
ClearPlayer(Board, i); | |
else | |
{ | |
if(firstTime) | |
AddPlayerPosition(Board, i, X0, Y0); | |
AddPlayerPosition(Board, i, X1, Y1); | |
} | |
GenerateWeights(Board); | |
//PrintBoard(Board); | |
if(i == P) | |
myPosition = Point(X1, Y1); | |
else | |
players.push_back(Point(X1, Y1)); | |
} | |
firstTime = false; | |
Print("PrevPositions", prevPlayers); | |
Print("Positions", players); | |
cerr << "Finding path: "; Print(myPosition); cerr << endl; | |
vector<Point> directions = {Point(0, -1), Point(0, 1), Point(1, 0), Point(-1, 0)};//, Point(-1, -1), Point(1, 1), Point(1, -1), Point(-1, 1)}; | |
vector<Point> candidateDestinations; | |
for(const Point& p : players) | |
{ | |
for(const Point& d : directions) | |
{ | |
Point dest = p + d; | |
if(IsValidMove(Board, dest) && (find(candidateDestinations.begin(), candidateDestinations.end(), dest) == candidateDestinations.end())) | |
candidateDestinations.push_back(dest); | |
} | |
} | |
const int MaxPredictionDistance = 6; | |
if(players.size() == prevPlayers.size()) | |
{ | |
for(int i = 0; i < players.size(); ++i) | |
{ | |
if(!IsOnBoard(players[i]) || !IsOnBoard(prevPlayers[i])) | |
continue; | |
Point newDir = players[i] - prevPlayers[i]; | |
for(int distance = 2; distance <= MaxPredictionDistance; ++distance) | |
{ | |
Point dir_tmp = newDir; | |
Point p = players[i]+dir_tmp; | |
vector<Point>::iterator it = find(candidateDestinations.begin(), candidateDestinations.end(), p); | |
if(it != candidateDestinations.end()) | |
{ | |
fprintf(stderr, "Removing destination: (%d, %d)\n", p.x, p.y); | |
candidateDestinations.erase(it); | |
} | |
dir_tmp.x *= distance; | |
dir_tmp.y *= distance; | |
dir_tmp = players[i] + dir_tmp; | |
if(IsValidMove(Board, dir_tmp) && (find(candidateDestinations.begin(), candidateDestinations.end(), dir_tmp) == candidateDestinations.end())) | |
candidateDestinations.push_back(dir_tmp); | |
else | |
break; | |
} | |
} | |
} | |
const char* move = nullptr; | |
bool done = false; | |
for(const Point& dir : directions) | |
{ | |
if (done) | |
break; | |
Point newPos = dir + myPosition; | |
for(const Point& player: players) | |
{ | |
if(IsStuck2(Board, player, newPos, myPosition)) | |
{ | |
move = GenerateMove(myPosition, newPos); | |
fprintf(stderr, "Found killer move: (%d, %d)->(%d, %d) Killing(%d, %d): %s\n;", myPosition.x, myPosition.y, newPos.x, newPos.y, player.x, player.y, move); | |
cout << move << endl; | |
done = true; | |
break; | |
} | |
} | |
} | |
if(done) | |
continue; | |
Print("Candidate destinations", candidateDestinations); | |
vector<Point> path = GetAnoyingPath(Board, players, myPosition, candidateDestinations); | |
prevPlayers = players; | |
//Print("Path", path); | |
float totalCost = 0.0f; | |
for(const Point& p : path) | |
totalCost += p.cost; | |
cerr << "Total path cost: " << totalCost << endl; | |
if(path.size() > 1) | |
{ | |
move = GenerateMove(myPosition, path[1]); | |
} | |
else | |
{ | |
//PrintBoard(Board); | |
cerr <<"LAST RESORT!" << endl; | |
move = "LEFT"; | |
Point dest = LastResortDestination(Board, myPosition); | |
move = GenerateMove(myPosition, dest); | |
} | |
cout << move << endl; | |
// Write an action using cout. DON'T FORGET THE "<< endl" | |
// To debug: cerr << "Debug messages..." << endl; | |
//cout << "LEFT" << endl; // A single line with UP, DOWN, LEFT or RIGHT | |
} | |
} | |
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// | |
//MTCS stuff - start with minimax | |
typedef vector<Point> PointArray; | |
const Point directions[] = {Point(-1, 0), Point(1, 0), Point(0, 1), Point(0, -1)}; //Possible directions of expansion | |
const vector<PointArray> dirOptions; | |
/* | |
void GenerateDirCombinations() | |
{ | |
for(const Point& d1 : directions) | |
for(const Point& d2: directions) | |
for(const Point& d3: directions) | |
{ | |
PointArray dirs = {d1, d2, d3); | |
dirOptions.push_back(dirs); | |
} | |
} | |
*/ | |
class GameState | |
{ | |
public: | |
GameState(): parent(nullptr), m_MaxState(true){} | |
void GenerateChildren() | |
{ | |
//Expand m_MaxPlayer | |
Point player = m_MaxPlayer; | |
if(!m_MaxState) | |
player = m_MinPlayer; //Min state, expant m_MinPlayer | |
for(const Point& dir : directions) | |
{ | |
Point candidate = dir + player; | |
if(!IsValidMove(m_Board, candidate)) | |
continue; | |
GameState* newState = new GameState(); | |
newState->parent = this; | |
for(int y = 0; y < Height; y++) | |
for(int x = 0; x < Width; x++) | |
newState->m_Board[y][x].occupant = m_Board[x][y].occupant; | |
//occupy it | |
newState->m_Board[candidate.y][candidate.x].occupant = 1; | |
newState->m_MaxState = !m_MaxState; | |
if(m_MaxState) | |
{ | |
//Max got to move to a new position. | |
newState->m_MaxPlayer = candidate; | |
newState->m_MinPlayer = m_MinPlayer; | |
} | |
else | |
{ | |
//Min got to move to a new position. | |
newState->m_MaxPlayer = m_MaxPlayer; | |
newState->m_MinPlayer = candidate; | |
} | |
newState->m_Depth = m_Depth + 1; | |
m_Children.push_back(newState); | |
} | |
} | |
int Evaluate() | |
{ | |
m_MaxDestination = m_MaxPlayer; | |
m_MinDestination = m_MinPlayer; | |
if(m_MaxState) | |
return EvaluateMaxState(); | |
else | |
return EvaluateMinState(); | |
} | |
int EvaluateMinState() | |
{ | |
int min = 9999; | |
if(CanGenerateChildren()) | |
{ | |
GenerateChildren(); | |
for(GameState* child : m_Children) | |
{ | |
if(!child) | |
continue; | |
int val = child->Evaluate(); | |
if(val < min) | |
{ | |
min = val; | |
m_MinDestination = child->m_MinDestination; | |
} | |
} | |
} | |
else | |
{ | |
//Heuristics | |
return DFS(m_Board, m_MinPlayer, 0) - DFS(m_Board, m_MaxPlayer, 0); | |
} | |
return min; | |
} | |
int EvaluateMaxState() | |
{ | |
int max = -1; | |
if(CanGenerateChildren()) | |
{ | |
GenerateChildren(); | |
for(GameState* child : m_Children) | |
{ | |
if(!child) | |
continue; | |
int val = child->Evaluate(); | |
if(val > max) | |
{ | |
m_MaxDestination = child->m_MaxPlayer; | |
max = val; | |
} | |
} | |
} | |
else | |
{ | |
//Heuristics | |
return DFS(m_Board, m_MaxPlayer, 0) - DFS(m_Board, m_MinPlayer, 0); | |
} | |
} | |
bool CanGenerateChildren() | |
{ | |
return m_Depth < 4; | |
} | |
~GameState() | |
{ | |
for(GameState* child : m_Children) | |
delete child; | |
} | |
public: | |
Point m_MaxDestination; | |
Point m_MinDestination; | |
int m_Depth; | |
bool m_MaxState; | |
Cell m_Board[Height][Width]; | |
Point m_MaxPlayer; //End positions where the players are now. | |
Point m_MinPlayer; | |
GameState* parent; | |
vector<GameState*> m_Children; | |
}; | |
//Gets us a score based on if players die and we stay alive. maxDepth on each branch !!! | |
int EvaluateState(Cell board[Height][Width], GameState* state, int maxDepth = 50, bool max_turn = true) | |
{ | |
return 0; | |
}; | |
void ConstructTree(Cell board[Height][Width], Point myPosition, const PointArray& enemies) | |
{ | |
//I move first (now), since it's my update... Assume enemies move in the order from the array. | |
} | |
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment