From: Michael Andreen Date: Tue, 28 Jun 2005 19:56:39 +0000 (+0000) Subject: much more advanced cop X-Git-Url: https://ruin.nu/git/?p=icfp05.git;a=commitdiff_plain;h=a76a0b3a94ab89c98135829d163a5fd303398f98 much more advanced cop --- diff --git a/copsrc/cop.cpp b/copsrc/cop.cpp index 8874574..fd40792 100644 --- a/copsrc/cop.cpp +++ b/copsrc/cop.cpp @@ -56,9 +56,14 @@ void Cop::preGamePreparations(){ banks.pop(); } for (hash_map::const_iterator player = _players.begin(); - player != _players.end() && banks2.size() > 0; ++player){ - if (player->first == _name || player->second.type == robber) + player != _players.end(); ++player){ + cerr << "Inital plan for player: " << player->first << endl; + if (player->second.type == robber){ + _robber = player->first; continue; + }else if (banks2.size() <= 0 || player->first == _name) + continue; + const pair& bank = banks2.top(); _copTargets[player->first].first = bank.second; //cerr << "Sending: " << player->first << " to: " << bank.second; @@ -70,20 +75,89 @@ void Cop::preGamePreparations(){ _winningPlans[player->first] = 0; banks2.pop(); } + _maybeRobber.push_back(hash_map()); } void Cop::sendInformation(){ + _maybeRobber.push_back(hash_map()); + hash_map& maybeRobber = _maybeRobber.back(); + int possibilities = 0; + if (_robberLocation.empty()){ + + hash_map::const_iterator intersection = _intersections.find(_location); + + for (hash_map::const_iterator adj = intersection->second.connections.begin(); + adj != intersection->second.connections.end(); ++adj){ + + if (_smell == 1){ + hash_map::iterator location = maybeRobber.find(adj->first); + if (location == maybeRobber.end()){ + hash_map::const_iterator intersection = _intersections.find(adj->first); + int neigh = maybeAtNeighbor(intersection->second); + if (neigh > -1){ + maybeRobber[adj->first] = 100 + neigh; + ++possibilities; + }else + maybeRobber[adj->first] = -100; + } + }else{ + if (_smell == 0) + maybeRobber[adj->first] = -100; + hash_map::const_iterator intersection = _intersections.find(adj->first); + for (hash_map::const_iterator adj = intersection->second.connections.begin(); + adj != intersection->second.connections.end(); ++adj){ + hash_map::iterator location = maybeRobber.find(adj->first); + if (location == maybeRobber.end()){ + if (_smell == 0) + maybeRobber[adj->first] = -100; + else { + hash_map::const_iterator intersection = _intersections.find(adj->first); + int neigh = maybeAtNeighbor(intersection->second); + if (neigh > -1){ + maybeRobber[adj->first] = 100 + neigh; + ++possibilities; + } + else + maybeRobber[adj->first] = -100; + } + } + } + } + } + } else { + maybeRobber[_robberLocation] = 100; + possibilities = 1; + hash_map::const_iterator intersection = _intersections.find(_location); + + for (hash_map::const_iterator adj = intersection->second.connections.begin(); + adj != intersection->second.connections.end(); ++adj){ + maybeRobber[adj->first] = -100; + for (hash_map::const_iterator adj = intersection->second.connections.begin(); + adj != intersection->second.connections.end(); ++adj){ + hash_map::iterator location = maybeRobber.find(adj->first); + if (location != maybeRobber.end()) + maybeRobber[adj->first] = -100; + } + + } + + + } cout << "inf\\" << endl; + for (hash_map::iterator location = maybeRobber.begin(); + location != maybeRobber.end(); ++location){ + if (location->second > 0) + location->second /= possibilities; + cout << "inf: " << _robber << " " << location->first << " " << _playerTypeNames[robber] << " " + << _world << " " << location->second << endl; + } cout << "inf/" << endl; } void Cop::getInformation(){ string input; - - if (false && _robberLocation.empty()){ //Disable for now, since it takes to long time, and does nothing - if (_smell > 0){ - //TODO: Calculate smell - } + if (_robberLocation.empty()){ + hash_map& maybeRobber = _maybeRobber.back(); while (true){ getline(cin, input); if (input == "from/") @@ -102,6 +176,10 @@ void Cop::getInformation(){ inf >> bot; string loc; inf >> loc; + string type; + inf >> type; + if (type != _playerTypeNames[robber]) + continue; int world; inf >> world; if (world != _world) @@ -109,7 +187,18 @@ void Cop::getInformation(){ int certainty; inf >> certainty; - //TODO: Calculate possibilties + hash_map::iterator location = maybeRobber.find(loc); + if (location == maybeRobber.end()){ + hash_map::const_iterator intersection = _intersections.find(loc); + if (intersection != _intersections.end()) + continue; //The intersection doesn't exist, so ignore it. + int neigh = maybeAtNeighbor(intersection->second); + if (neigh >= 0) + maybeRobber[loc] = certainty + neigh; + else + maybeRobber[loc] = -200; + }else if (location->second > 0) + location->second += certainty; } } }else{ @@ -117,34 +206,70 @@ void Cop::getInformation(){ getline(cin,input); }while(input != "from/"); } + _maybeRobber.pop_front(); + +} +int Cop::maybeAtNeighbor(const Intersection& intersection){ + int possibility = -1; + for (hash_map::const_iterator adj = intersection.connections.begin(); + adj != intersection.connections.end(); ++adj){ + hash_map::iterator oldLoc = _maybeRobber.front().find(adj->first); + if (oldLoc == _maybeRobber.front().end() || oldLoc->second > 0){ + if (possibility < 0){ + possibility = 0; + } + if (oldLoc != _maybeRobber.front().end()) + possibility += oldLoc->second; + } + } + return possibility; } void Cop::sendPlan(){ //cerr << "Planning" << endl; + string secondLocation = _robberLocation; if (_robberLocation.empty()){ - //Use information for plan. + priority_queue > positions; + for (hash_map::iterator location = _maybeRobber.front().begin(); + location != _maybeRobber.front().end(); ++location){ + if (location->second > 0) + positions.push(pair(location->second,location->first)); + + } + if (positions.size() > 0){ + _robberLocation = positions.top().second; + cerr << "Sending myself to: " << _robberLocation << ", probability of robber: " << positions.top().first << endl; + } + if (positions.size() > 1){ + positions.pop(); + secondLocation = positions.top().second; + cerr << "Sending another cop to: " << secondLocation << ", probability of robber: " << positions.top().first << endl; + } } - else{ + if (!_robberLocation.empty()){ //cerr << "Robber found at " << _robberLocation << endl; _copTargets[_name].first = _robberLocation; - list closestFootCop = shortestPath(_robberLocation, cop_foot, FindPlayer(_players, cop_foot), true); - list closestCarCop = shortestPath(_robberLocation, cop_car, FindPlayer(_players, cop_car, closestFootCop.size() - 1), true); - PlayerType copType = cop_foot; - string copLocation; - if (closestCarCop.size() > 0){ - copType = cop_car; - copLocation = closestCarCop.back(); - }else - copLocation = closestFootCop.back(); - - - for (hash_map::const_iterator player = _players.begin(); - player != _players.end(); ++player){ - if (player->first == _name || player->second.type == robber) - continue; - if (player->second.type == copType && player->second.location == copLocation) - _copTargets[player->first].first = _robberLocation; + + if (!secondLocation.empty()){ + list closestFootCop = shortestPath(_robberLocation, cop_foot, FindPlayer(_players, cop_foot), true); + list closestCarCop = shortestPath(_robberLocation, cop_car, FindPlayer(_players, cop_car, closestFootCop.size() - 1), true); + PlayerType copType = cop_foot; + string copLocation; + if (closestCarCop.size() > 0){ + copType = cop_car; + copLocation = closestCarCop.back(); + }else + copLocation = closestFootCop.back(); + + + for (hash_map::const_iterator player = _players.begin(); + player != _players.end(); ++player){ + if (player->first == _name || player->second.type == robber) + continue; + if (player->second.type == copType && player->second.location == copLocation) + _copTargets[player->first].first = _robberLocation; + } } } //cerr << "Sending plan." << endl; diff --git a/copsrc/cop.h b/copsrc/cop.h index 0cc2a64..3b1d3a1 100644 --- a/copsrc/cop.h +++ b/copsrc/cop.h @@ -16,10 +16,11 @@ class Cop : public Bot { void sendPlan(); void getPlans(); void vote(); + int maybeAtNeighbor(const Intersection& intersection); __gnu_cxx::hash_map > _copTargets; - std::vector _noRobber; - __gnu_cxx::hash_map _maybeRobber; + std::list<__gnu_cxx::hash_map > _maybeRobber; __gnu_cxx::hash_map _winningPlans; + std::string _robber; }; #endif diff --git a/copsrc/copsrc.pro b/copsrc/copsrc.pro index 3ef1292..f0edde6 100644 --- a/copsrc/copsrc.pro +++ b/copsrc/copsrc.pro @@ -5,7 +5,7 @@ TEMPLATE = app INCLUDEPATH += ../botsrc CONFIG -= qt -#CONFIG += debug +CONFIG += debug unix:LIBS += -lm TARGET = ../cop QMAKE_CFLAGS_RELEASE += -march=athlon-xp