/*
* Copyright (c) 2010 Daniel Hartmeier <daniel@benzedrine.ch>
* All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
*
* - Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
* - Redistributions in binary form must reproduce the above
* copyright notice, this list of conditions and the following
* disclaimer in the documentation and/or other materials provided
* with the distribution.
*
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
* "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
* LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
* FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
* COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
* INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
* BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
* LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
* CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
* LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
* ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
* POSSIBILITY OF SUCH DAMAGE.
*
*/
#include <errno.h>
#include <fcntl.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/time.h>
#include <list>
#include <map>
#include <deque>
#include <queue>
#include <stack>
#include <set>
#include <string>
#include "Map.h"
#include "board.h"
#include "node.h"
#include "graph.h"
#include "expand.h"
#include "maxsteps.h"
#ifdef DEBUG
FILE *logfile = 0;
#endif
/* called whenever idle, spend at most t us spawning new nodes
* return depth of tree, or 0 if tree is complete
*/
static unsigned
Spawn(unsigned long timeout)
{
if (!root)
return 0;
while (!nodes.empty() && usec() < timeout)
nodes.front()->spawn(timeout);
if (nodes.empty())
return 0;
unsigned depth = 0;
for (Node *n = nodes.front(); n; n = n->parent)
depth++;
return depth;
}
#ifdef DEBUG
static void
printChildren(const Node *p, unsigned ident, unsigned max)
{
if (ident >= max)
return;
for (int m = 0; m < 4; ++m) {
for (int o = 0; o < 4; ++o) {
for (unsigned i = 0; i < ident; ++i)
debug(" ");
if (!p->children[m][o]) {
debug("child m %s o %s NULL\n", dname[m], dname[o]);
continue;
}
debug("child m %s o %s %s", dname[m],
dname[o], rname[p->children[m][o]->best]);
if (p->children[m][o]->best == LOSS)
debug(" movesToLoss %d", p->children[m][o]->movesToLoss);
if (p->children[m][o]->best == DRAW)
debug(" movesToDraw %d", p->children[m][o]->movesToDraw);
if (p->children[m][o]->best == WIN)
debug(" movesToWin %d", p->children[m][o]->movesToWin);
if (p->children[m][o]->best == UNDECIDED)
debug(" area %d", p->children[m][o]->area);
if (p->children[m][o]->isolated)
debug(" isolated");
else {
if (p->children[m][o]->leaf)
debug(" leaf");
}
debug("\n");
if (!p->children[m][o]->leaf && !p->children[m][o]->isolated)
printChildren(p->children[m][o], ident + 1, max);
}
}
}
#endif
/* called when a move must be made within one second */
static string
MakeMove(const Map &map) {
unsigned long t0 = usec();
Board b(map);
static DIR dir = NORTH;
static bool first = true;
static vector<DIR> path;
debug("========================================\n\n");
if (!root) {
debug("got initial map, creating root node\n");
root = new Node(b);
} else {
Node *newroot = NULL;
/* dir contains my previous move */
/* find opponent's previous move */
for (int o = 0; o < 4; ++o) {
if (step(root->board.getOpPos(), (DIR)o) == b.getOpPos()) {
newroot = root->children[dir][o];
root->children[dir][o] = NULL;
break;
}
}
if (newroot) {
debug("new root found in children\n");
} else {
debug("newroot not found, creating new root\n");
newroot = new Node(b);
if (!newroot->isolated) {
debug("ERROR: newroot NOT isolated\n");
#ifdef DEBUG
exit(0);
#endif
}
}
delete root;
root = newroot;
root->parent = NULL;
}
#if DEBUG
debug("%lu nodes, %u unspawned\n", treesize, (unsigned)nodes.size());
#endif
if (!root->isolated && !nodes.empty()) {
debug("start spawning after %lu us\n", usec() - t0);
unsigned depth = Spawn(usec() + (first ? 2900000 : 940000));
debug("%s: treesize %lu, %u nodes, depth %u\n", !depth ? "COMPLETE" :
"INCOMPLETE", treesize, (unsigned)nodes.size(), depth);
}
#ifdef DEBUG
root->board.print();
debug("root: %s%s", rname[root->best], root->isolated ?
" ISOLATED" : "");
if (root->best == WIN)
debug(" movesToWin %d", root->movesToWin);
if (root->best == DRAW)
debug(" movesToDraw %d", root->movesToDraw);
if (root->best == LOSS)
debug(" movesToLoss %d", root->movesToLoss);
if (root->best == UNDECIDED)
debug(" area %d", root->area);
debug("\n");
if (!root->isolated)
printChildren(root, 0, 1);
#endif
debug("starting decision after %lu us\n", usec() - t0);
if (root->isolated) {
if (root->path.size() > path.size())
path = root->path;
unsigned max = root->floodFill(false);
unsigned min = root->floodFill(true);
if (path.size() > min) {
debug("MakeMove: old path size %u > min %u, winning!\n",
(unsigned)path.size(), min);
} else {
vector<DIR> v;
root->rateIsolation(max, min, v,
usec() + (first ? 2900000 : 900000));
debug("MakeMove: rateIsolation() v.size %u\n",
(unsigned)v.size());
if (!v.size())
goto usepath;
#ifdef DEBUG
root->board.checkPath(root->board.getMyPos(), v);
#endif
if (v.size() > path.size()) {
debug("MakeMove: v.size %u > path.size %u, "
"taking new path\n", (unsigned)v.size(),
(unsigned)path.size());
path = v;
} else {
debug("MakeMove: v.size %u <= path.size %u, "
"keeping old path\n", (unsigned)v.size(),
(unsigned)path.size());
}
}
usepath:
if (!path.size()) {
debug("MakeMove: this is my dying move\n");
/* this is not possible, unless there are bugs ;) */
for (int d = 0; d < 4; ++d) {
pair<int, int> m = step(root->board.getMyPos(),
(DIR)d);
if (!root->board.read(m.first, m.second)) {
dir = (DIR)d;
break;
}
}
} else {
dir = (DIR)path[0];
path.erase(path.begin());
}
} else {
int r;
switch (root->best) {
case WIN:
r = root->nearestWin(dir);
debug("%s WIN in at most %d moves\n", dname[dir], r);
break;
case DRAW:
r = root->farthestDraw(dir);
debug("%s DRAW for at least %d moves\n", dname[dir], r);
break;
case LOSS:
r = root->farthestLoss(dir);
debug("%s LOSS for at least %d moves\n", dname[dir], r);
break;
case UNDECIDED:
r = root->bestUndecided(dir);
debug("%s best UNDECIDED (out of %d)\n",
dname[dir], r);
break;
}
}
if (first)
first = false;
debug("returning %s after %lu us\n", dname[dir], usec() - t0);
return dname[dir];
}
int
main(int argc, char *argv[]) {
int r;
fd_set readfds;
struct timeval tv;
#ifdef DEBUG
unsigned count = 0;
#endif
#ifdef DEBUG
if (!(logfile = fopen("bot.log", "w"))) {
debug("fopen: %s\n", strerror(errno));
return 1;
}
#endif
srand(time(NULL));
if (!((r = fcntl(STDIN_FILENO, F_GETFL)) & O_NONBLOCK))
fcntl(STDIN_FILENO, r | O_NONBLOCK);
while (true) {
FD_ZERO(&readfds);
FD_SET(STDIN_FILENO, &readfds);
tv.tv_sec = tv.tv_usec = 0;
r = select(STDIN_FILENO + 1, &readfds, 0, 0, &tv);
if (r < 0) {
if (errno != EINTR) {
debug("main: select: %s\n", strerror(errno));
break;
}
continue;
}
if (r > 0) {
#ifdef DEBUG
unsigned long t = usec();
#endif
Map map;
Map::MakeMove(MakeMove(map));
#ifdef DEBUG
t = usec() - t;
if (t < (count++ ? 1000000 : 3000000)) {
debug("main: reply %u sent in %lu us\n",
count, t);
} else {
debug("==========================================\n");
debug("!!! ERROR: TIME LIMIT EXCEEDED: %lu us !!!\n", t);
debug("==========================================\n");
// return 0;
}
#endif
continue;
}
/* spend at most 1/10th of a second spawning */
// if (!nodes.empty())
// Spawn(100000);
}
return 0;
}