From 550caeee11086bd56db69176b3149ddfa160ee30 Mon Sep 17 00:00:00 2001 From: Justin Worthe Date: Sat, 17 Oct 2015 17:02:24 +0200 Subject: Reverted to a simple decision tree Turns out it's much easier to write a bot by hand with if statements. --- bot.json | 2 +- brain.nn | 28 ++++----- include/brain/bias_node.h | 4 +- include/brain/neural_link.h | 3 + include/brain/neural_network.h | 3 + include/brain/neural_node.h | 9 +++ include/brain/neuron.h | 4 ++ include/brain/sensor.h | 1 + main/main.cpp | 1 + src/brain/neural_network.cpp | 110 +++++++++++++++++++-------------- src/brain/neuron.cpp | 14 ++++- src/game_state.cpp | 122 ++++++++++++++++++------------------ src/spacebot.cpp | 21 +++++-- test/move_string_mapper.cpp | 15 +++++ test/neural_network.cpp | 137 +++++++++++++++++++++++++++++------------ 15 files changed, 304 insertions(+), 170 deletions(-) diff --git a/bot.json b/bot.json index d70d03c..542bff2 100644 --- a/bot.json +++ b/bot.json @@ -1,5 +1,5 @@ { - "nickName": "Spacebot", + "nickName": "Brick", "author": "Justin Worthe", "email", "justin.worthe@gmail.com" } diff --git a/brain.nn b/brain.nn index c1e932d..e45ef1b 100644 --- a/brain.nn +++ b/brain.nn @@ -1,14 +1,14 @@ -b0 n0 20 -s55 n3 10 -b0 n4 -20 -s59 n4 15 -s60 n4 15 -b0 n6 10 -s51 n6 -10 -s53 n6 -10 -n3 n0 -20 -n4 n0 -20 -n6 n0 -20 -n3 n4 -20 -n6 n3 -20 -n6 n4 -20 +b0 n0 20 +s55 n3 10 +b0 n5 -10 +s59 n5 -50 +s60 n5 20 +b0 n6 10 +s51 n6 -10 +s53 n6 -10 +n3 n0 -20 +n5 n0 -20 +n6 n0 -20 +n3 n5 -20 +n6 n3 -20 +n6 n5 -20 diff --git a/include/brain/bias_node.h b/include/brain/bias_node.h index 0b57e15..77c5884 100644 --- a/include/brain/bias_node.h +++ b/include/brain/bias_node.h @@ -5,8 +5,8 @@ class BiasNode: public NeuralNode { public: - BiasNode() +BiasNode() : NeuralNode("b0") { - _activation = 1; + _activation = 1; } }; diff --git a/include/brain/neural_link.h b/include/brain/neural_link.h index b9cf4d1..14f58b9 100644 --- a/include/brain/neural_link.h +++ b/include/brain/neural_link.h @@ -7,6 +7,9 @@ class NeuralLink public: NeuralLink(NeuralNode* input, double weight); double weightedActivation() const; + + double weight() const { return _weight; } + std::string inputIdentifier() const { return _input->identifier(); } private: NeuralNode* _input; diff --git a/include/brain/neural_network.h b/include/brain/neural_network.h index a1af7cc..7fcf5f4 100644 --- a/include/brain/neural_network.h +++ b/include/brain/neural_network.h @@ -22,6 +22,9 @@ public: unsigned int numberOfSensors() const { return _sensors.size(); } unsigned int numberOfOutputs() const { return _outputs.size(); } + unsigned int numberOfNeurons() const { return _neurons.size(); } + + bool linkExists(std::string srcIdentifier, std::string destIdentifier, double weight) const; private: std::vector> _sensors; diff --git a/include/brain/neural_node.h b/include/brain/neural_node.h index 62b7b15..2684146 100644 --- a/include/brain/neural_node.h +++ b/include/brain/neural_node.h @@ -1,9 +1,18 @@ #pragma once +#include + class NeuralNode { public: double activation() const { return _activation; } + std::string identifier() const { return _identifier; } + +NeuralNode(std::string identifier): _identifier(identifier) {} + protected: double _activation; + +private: + std::string _identifier; }; diff --git a/include/brain/neuron.h b/include/brain/neuron.h index 204b303..ca26c73 100644 --- a/include/brain/neuron.h +++ b/include/brain/neuron.h @@ -12,6 +12,10 @@ public: void addInput(NeuralLink&& link); bool calculateActivation(); +Neuron(int index) : NeuralNode('n'+std::to_string(index)){}; + + bool hasInputWithWeight(std::string srcIdentifier, double weight) const; + private: std::vector _inputLinks; double sigmoid(double input) const; diff --git a/include/brain/sensor.h b/include/brain/sensor.h index a780c49..10f62a7 100644 --- a/include/brain/sensor.h +++ b/include/brain/sensor.h @@ -5,5 +5,6 @@ class Sensor: public NeuralNode { public: +Sensor(int index) :NeuralNode('s'+std::to_string(index)){} void setActivation(double activation) { _activation = activation; } }; diff --git a/main/main.cpp b/main/main.cpp index ce6bc43..5c7f183 100644 --- a/main/main.cpp +++ b/main/main.cpp @@ -12,6 +12,7 @@ int main(int argc, char* argv[]) } std::string brainFilename = "brain.nn"; + if (argc >= 3) { brainFilename = argv[2]; diff --git a/src/brain/neural_network.cpp b/src/brain/neural_network.cpp index 0c23771..c8177e8 100644 --- a/src/brain/neural_network.cpp +++ b/src/brain/neural_network.cpp @@ -12,13 +12,13 @@ NeuralNetwork::NeuralNetwork(std::istream &&networkConfigFile, unsigned int numb for (unsigned int i=0; i(); - _sensors.push_back(sensor); + auto sensor = std::make_shared(i); + _sensors.push_back(sensor); } for (unsigned int i=0; i for (unsigned int i=0; i(); - sensor->setActivation(sensorInitialValues[i] ? 1 : 0); - _sensors.push_back(sensor); + auto sensor = std::make_shared(i); + sensor->setActivation(sensorInitialValues[i] ? 1 : 0); + _sensors.push_back(sensor); } for (unsigned int i=0; i> srcId && - file.ignore(std::numeric_limits::max(), 'n') && - file >> destId && - file >> weight && - file.ignore(std::numeric_limits::max(), '\n')) + file >> srcId && + file.ignore(std::numeric_limits::max(), 'n') && + file >> destId && + file >> weight && + file.ignore(std::numeric_limits::max(), '\n')) { + std::shared_ptr source; + std::shared_ptr destination; + switch (srcType) + { + case 's': + source = findOrAddSensor(srcId); + break; + case 'b': + source = _biasNode; + break; + default: + source = findOrAddNeuron(srcId); + } + destination = findOrAddNeuron(destId); - std::shared_ptr source; - std::shared_ptr destination; - switch (srcType) - { - case 's': - source = findOrAddSensor(srcId); - break; - case 'b': - source = _biasNode; - break; - default: - source = findOrAddNeuron(srcId); - } - destination = findOrAddNeuron(destId); - - addLink(source, destination, weight); + addLink(source, destination, weight); } } @@ -92,8 +91,8 @@ std::shared_ptr NeuralNetwork::findOrAddSensor(unsigned int id) { while (_sensors.size() <= id) { - auto sensor = std::make_shared(); - _sensors.push_back(sensor); + auto sensor = std::make_shared(_sensors.size()); + _sensors.push_back(sensor); } return _sensors.at(id); @@ -103,8 +102,8 @@ std::shared_ptr NeuralNetwork::findOrAddNeuron(unsigned int id) { while (_neurons.size() <= id) { - auto neuron = std::make_shared(); - _neurons.push_back(neuron); + auto neuron = std::make_shared(_neurons.size()); + _neurons.push_back(neuron); } return _neurons.at(id); @@ -121,12 +120,12 @@ unsigned int NeuralNetwork::findMaxOutputIndex() const auto maxIterations = _neurons.size()*10; for (unsigned int iteration=0; anyNodeChanged && iterationcalculateActivation(); - anyNodeChanged = anyNodeChanged || activationChanged; - } + anyNodeChanged = false; + for (auto const& neuron : _neurons) + { + bool activationChanged = neuron->calculateActivation(); + anyNodeChanged = anyNodeChanged || activationChanged; + } } int currentMaxIndex = 0; @@ -134,12 +133,31 @@ unsigned int NeuralNetwork::findMaxOutputIndex() const for (unsigned int i=1; i<_outputs.size(); ++i) { - double activation = _outputs.at(i)->activation(); - if (activation >= currentMaxActivation) - { - currentMaxActivation = activation; - currentMaxIndex = i; - } + double activation = _outputs.at(i)->activation(); + if (activation >= currentMaxActivation) + { + currentMaxActivation = activation; + currentMaxIndex = i; + } } return currentMaxIndex; } + +bool NeuralNetwork::linkExists(std::string srcIdentifier, std::string destIdentifier, double weight) const +{ + std::shared_ptr dest; + + for (auto const& node : _neurons) + { + if (node->identifier() == destIdentifier) + { + dest = node; + } + } + + if (!dest) + { + return false; + } + return dest->hasInputWithWeight(srcIdentifier, weight); +} diff --git a/src/brain/neuron.cpp b/src/brain/neuron.cpp index d1dd338..c7dba2c 100644 --- a/src/brain/neuron.cpp +++ b/src/brain/neuron.cpp @@ -12,7 +12,7 @@ bool Neuron::calculateActivation() double newActivation = 0; for (auto const& link : _inputLinks) { - newActivation += link.weightedActivation(); + newActivation += link.weightedActivation(); } newActivation = sigmoid(newActivation); @@ -26,3 +26,15 @@ void Neuron::addInput(NeuralLink&& link) { _inputLinks.push_back(std::move(link)); } + +bool Neuron::hasInputWithWeight(std::string srcIdentifier, double weight) const +{ + for (auto const& link : _inputLinks) + { + if (link.inputIdentifier() == srcIdentifier && link.weight() == weight) + { + return true; + } + } + return false; +} diff --git a/src/game_state.cpp b/src/game_state.cpp index 29bd75b..952c2f3 100644 --- a/src/game_state.cpp +++ b/src/game_state.cpp @@ -61,17 +61,17 @@ int GameState::addEntity(int x, int y, char type) _shields.push_back(Shield(x,y)); return 1; case Spaceship::ENEMY_MAP_CHAR: - _enemySpaceship = std::unique_ptr(new Spaceship(x+1, y)); - return 3; + _enemySpaceship = std::unique_ptr(new Spaceship(x+1, y)); + return 3; case Spaceship::PLAYER_MAP_CHAR: - _playerSpaceship = std::unique_ptr(new Spaceship(x+1, y)); + _playerSpaceship = std::unique_ptr(new Spaceship(x+1, y)); return 3; case Building::MISSILE_CONTROLLER_CHAR: - _missileControllers.push_back(Building(x+1, y)); - return 3; + _missileControllers.push_back(Building(x+1, y)); + return 3; case Building::ALIEN_FACTORY_CHAR: - _alienFactories.push_back(Building(x+1, y)); - return 3; + _alienFactories.push_back(Building(x+1, y)); + return 3; } return 1; } @@ -96,11 +96,11 @@ void GameState::logState() const } if (_playerSpaceship) { - std::cout << "Player Spaceship" << _playerSpaceship->coords() << std::endl; + std::cout << "Player Spaceship" << _playerSpaceship->coords() << std::endl; } if (_enemySpaceship) { - std::cout << "Enemy Spaceship" << _enemySpaceship->coords() << std::endl; + std::cout << "Enemy Spaceship" << _enemySpaceship->coords() << std::endl; } } @@ -110,25 +110,25 @@ int getPyramidOffset(int bottomWidth, int maxWidth, int x, int y, int resultIfLe int currentRowOffset = 0; for (int i=0; i maxWidth) - { - currentRowWidth = maxWidth; - } + currentRowOffset += currentRowWidth; + currentRowWidth += 2; + if (currentRowWidth > maxWidth) + { + currentRowWidth = maxWidth; + } } if (x > currentRowWidth/2) { - return resultIfRight; + return resultIfRight; } else if (x < -currentRowWidth/2) { - return resultIfLeft; + return resultIfLeft; } else { - return currentRowOffset + currentRowWidth/2 + x; + return currentRowOffset + currentRowWidth/2 + x; } } @@ -154,80 +154,80 @@ std::vector GameState::toBitArray() const int playerY = GAME_AREA_LINES-3; if (_playerSpaceship) { - playerX = _playerSpaceship->x(); + playerX = _playerSpaceship->x(); } for (auto const& alien : _aliens) { - if (alien.y() > playerY-4 || alien.y() < playerY-7 || alien.x() > playerX+4 || alien.x() < playerX-4) - { - continue; - } + if (alien.y() > playerY-4 || alien.y() < playerY-7 || alien.x() > playerX+4 || alien.x() < playerX-4) + { + continue; + } - result.at(alienOffset + getRectangularOffset(9, alien.x()-playerX, playerY-4-alien.y())) = true; + result.at(alienOffset + getRectangularOffset(9, alien.x()-playerX, playerY-4-alien.y())) = true; } for (auto const& bullet : _bullets) { - if (bullet.y() >= playerY || bullet.y() < playerY-3 || bullet.x() > playerX+2 || bullet.x() < playerX-2) - { - continue; - } + if (bullet.y() >= playerY || bullet.y() < playerY-3 || bullet.x() > playerX+2 || bullet.x() < playerX-2) + { + continue; + } - result.at(bulletOffset + getRectangularOffset(5, bullet.x()-playerX, playerY-1-bullet.y())) = true; + result.at(bulletOffset + getRectangularOffset(5, bullet.x()-playerX, playerY-1-bullet.y())) = true; } for (auto const& shield : _shields) { - if (shield.y() < playerY-3 || shield.x() < playerX-1 || shield.x() > playerX+1) - { - continue; - } + if (shield.y() < playerY-3 || shield.x() < playerX-1 || shield.x() > playerX+1) + { + continue; + } - result.at(shieldOffset + shield.x()-playerX+1) = true; + result.at(shieldOffset + shield.x()-playerX+1) = true; } if (_missiles.size() > 0) { - result.at(missileOffset) = true; + result.at(missileOffset) = true; } if (_missiles.size() < 1) { - result.at(missileOffset + 1) = true; + result.at(missileOffset + 1) = true; } if (_playerSpaceship) { - if (playerX <= GAME_WIDTH/3) - { - result.at(positionOffset) = true; - } - else if (playerX >= GAME_WIDTH*2/3) - { - result.at(positionOffset+2) = true; - } - else - { - result.at(positionOffset+1) = true; - } + if (playerX <= GAME_WIDTH/3) + { + result.at(positionOffset) = true; + } + else if (playerX >= GAME_WIDTH*2/3) + { + result.at(positionOffset+2) = true; + } + else + { + result.at(positionOffset+1) = true; + } } result.at(canBuildOffset) = true; for (auto const& missileController : _missileControllers) { - if (missileController.y() < playerY) - { - continue; - } - result.at(existingBuildingsOffset + 0) = true; - if (_missiles.size() < 2) - { - result.at(missileOffset+1) = true; - } - if (abs(missileController.x() - playerX) < 3) - { - result.at(canBuildOffset) = false; - } + if (missileController.y() < playerY) + { + continue; + } + result.at(existingBuildingsOffset + 0) = true; + if (_missiles.size() < 2) + { + result.at(missileOffset+1) = true; + } + if (abs(missileController.x() - playerX) < 3) + { + result.at(canBuildOffset) = false; + } } return result; diff --git a/src/spacebot.cpp b/src/spacebot.cpp index 15f2221..17d20b5 100644 --- a/src/spacebot.cpp +++ b/src/spacebot.cpp @@ -20,12 +20,23 @@ void Spacebot::writeNextMove() Move Spacebot::chooseMove() { auto sensorInputs = _gameState.toBitArray(); - - NeuralNetwork network(std::ifstream(_brainFilename), - sensorInputs, - 7); - return static_cast(network.findMaxOutputIndex()); + if (!sensorInputs.at(51) || !sensorInputs.at(53)) + { + return Move::BUILD_SHIELD; + } + else if (sensorInputs.at(55)) + { + return Move::SHOOT; + } + else if (sensorInputs.at(60) && !sensorInputs.at(59)) + { + return Move::BUILD_MISSILE_CONTROLLER; + } + else + { + return Move::NOTHING; + } } void Spacebot::writeMove(const Move& move) diff --git a/test/move_string_mapper.cpp b/test/move_string_mapper.cpp index ab167e3..a7af36a 100644 --- a/test/move_string_mapper.cpp +++ b/test/move_string_mapper.cpp @@ -20,4 +20,19 @@ SCENARIO("Writing a move") } } + + GIVEN("Build missle controller move") + { + Move move = Move::BUILD_MISSILE_CONTROLLER; + + WHEN("It is mapped to a string") + { + std::string moveString = MoveStringMapper().toString(move); + + THEN("The string is correct") + { + REQUIRE(moveString == "BuildMissileController"); + } + } + } } diff --git a/test/neural_network.cpp b/test/neural_network.cpp index 801f0ec..418f5c4 100644 --- a/test/neural_network.cpp +++ b/test/neural_network.cpp @@ -7,59 +7,116 @@ SCENARIO("network is read from istream") { GIVEN("an empty config file") { - std::stringstream file; - file << "" << std::endl; + std::stringstream file; + file << "" << std::endl; - WHEN ("the network is initialized") - { - NeuralNetwork network(std::move(file), 1, 2); + WHEN ("the network is initialized") + { + NeuralNetwork network(std::move(file), 1, 2); - THEN("the specified number of inputs and outputs are created") - { - REQUIRE(network.numberOfSensors() == 1); - REQUIRE(network.numberOfOutputs() == 2); - } - } + THEN("the specified number of inputs and outputs are created") + { + REQUIRE(network.numberOfSensors() == 1); + REQUIRE(network.numberOfOutputs() == 2); + } + } } GIVEN("a valid config file") { - std::stringstream file; - file << "s0 n3 0.5" << std::endl; - file << "n3 n1 1" << std::endl; - file << "b0 n0 0.4" << std::endl; - file << "b0 n3 0.5" << std::endl; + std::stringstream file; + file << "s0 n3 0.5" << std::endl; + file << "n3 n1 1" << std::endl; + file << "b0 n0 0.4" << std::endl; + file << "b0 n3 0.5" << std::endl; - WHEN("the network is initialized") - { - NeuralNetwork network(std::move(file), 1, 3); + WHEN("the network is initialized") + { + NeuralNetwork network(std::move(file), 1, 3); - THEN("the network is constructed correctly") - { - network.setInput(0, 1); - REQUIRE(network.findMaxOutputIndex() == 1); - } - } + THEN("the network is constructed correctly") + { + REQUIRE(network.linkExists("s0", "n3", 0.5)); + REQUIRE(network.linkExists("n3", "n1", 1)); + REQUIRE(network.linkExists("b0", "n0", 0.4)); + REQUIRE(network.linkExists("b0", "n3", 0.5)); + } + THEN("The network evaluates correctly") + { + network.setInput(0, 1); + REQUIRE(network.findMaxOutputIndex() == 1); + } + } } GIVEN("a valid recurrant config file") { - std::stringstream file; - file << "s0 n3 0.5" << std::endl; - file << "n3 n1 1" << std::endl; - file << "b0 n0 0.4" << std::endl; - file << "b0 n3 0.5" << std::endl; - file << "n1 n3 0.5" << std::endl; + std::stringstream file; + file << "s0 n3 0.5" << std::endl; + file << "n3 n1 1" << std::endl; + file << "b0 n0 0.4" << std::endl; + file << "b0 n3 0.5" << std::endl; + file << "n1 n3 0.5" << std::endl; - WHEN("the network converges") - { - NeuralNetwork network(std::move(file), 1, 3); + WHEN("the network converges") + { + NeuralNetwork network(std::move(file), 1, 3); - THEN("the network is constructed correctly") - { - network.setInput(0, 1); - REQUIRE(network.findMaxOutputIndex() == 1); - } - } + THEN("the network is constructed correctly") + { + network.setInput(0, 1); + REQUIRE(network.findMaxOutputIndex() == 1); + } + } + } + + GIVEN("my handcoded config file") + { + std::stringstream file; + file << "b0 n0 20" << std::endl; + file << "s55 n3 10" << std::endl; + file << "b0 n4 -10" << std::endl; + file << "s59 n4 -50" << std::endl; + file << "s60 n4 20" << std::endl; + file << "b0 n6 10" << std::endl; + file << "s51 n6 -10" << std::endl; + file << "s53 n6 -10" << std::endl; + file << "n3 n0 -20" << std::endl; + file << "n4 n0 -20" << std::endl; + file << "n6 n0 -20" << std::endl; + file << "n3 n4 -20" << std::endl; + file << "n6 n3 -20" << std::endl; + file << "n6 n4 -20" << std::endl; + + WHEN("the netwok is constructed") + { + std::vector sensors(61); + + NeuralNetwork network(std::move(file), sensors, 7); + THEN("it is constructred correctly") + { + REQUIRE(network.linkExists("b0", "n0", 20)); + REQUIRE(network.linkExists("s55", "n3", 10)); + REQUIRE(network.linkExists("b0", "n4", -10)); + REQUIRE(network.linkExists("s59", "n4", -50)); + REQUIRE(network.linkExists("s60", "n4", 20)); + REQUIRE(network.linkExists("b0", "n6", 10)); + REQUIRE(network.linkExists("s51", "n6", -10)); + REQUIRE(network.linkExists("s53", "n6", -10)); + REQUIRE(network.linkExists("n3", "n0", -20)); + REQUIRE(network.linkExists("n4", "n0", -20)); + REQUIRE(network.linkExists("n6", "n0", -20)); + REQUIRE(network.linkExists("n3", "n4", -20)); + REQUIRE(network.linkExists("n6", "n3", -20)); + REQUIRE(network.linkExists("n6", "n4", -20)); + } + + THEN("it has the right number of nodes and sensors") + { + REQUIRE(network.numberOfSensors() == 61); + REQUIRE(network.numberOfOutputs() == 7); + REQUIRE(network.numberOfNeurons() == 7); + } + } } } -- cgit v1.2.3