fork(25) download
  1. #include <iostream>
  2. #include <string>
  3. #include <vector>
  4. #include <bitset>
  5. #include <math.h>
  6. #include <algorithm>
  7.  
  8. using namespace std;
  9.  
  10. class Map
  11. {
  12. public:
  13. Map();
  14. Map(string seed);
  15. int width;
  16. int height;
  17. string values;
  18. char value_at(int x, int y);
  19. void set_value_at(int x, int y, char val);
  20. bitset<24> observe(int x, int y);
  21. };
  22.  
  23. Map::Map(string seed)
  24. {
  25. string delim = ":";
  26. int start = 0U;
  27. int end = seed.find(delim);
  28. string rows = seed.substr(start, end - start);
  29.  
  30. height = stoi(rows);
  31.  
  32. start = end + delim.length();
  33. end = seed.find(delim, start);
  34. string cols = seed.substr(start, end-start);
  35.  
  36. width = stoi(cols);
  37.  
  38. start = end + delim.length();
  39. end = seed.find(delim, start);
  40.  
  41. values = seed.substr(start, end);
  42. }
  43.  
  44. void Map::set_value_at(int x, int y, char val)
  45. {
  46. if (x < 0 || y < 0 || x >= height || y >= width){
  47. return;
  48. }
  49. values[x*width + y] = val;
  50. return;
  51. }
  52.  
  53. char Map::value_at(int x, int y)
  54. {
  55. if (x < 0 || y < 0 || x >= height || y >= width){
  56. char temp = '*';
  57. return temp;
  58. }
  59. return values.at(x*width + y);
  60. }
  61.  
  62. bitset<24> Map::observe(int x, int y)
  63. {
  64. /*
  65. *
  66. * There are 8 zones around the rat, four close zones and four far zones
  67. * The close zones are the squares in a given quadrant that are 1 away
  68. * (e.g. to my left, to my top-left, and above me are the one away squares in
  69. * the -x, -y or NW quadrant)
  70. * The far zones are the squares from each quadrant that are 2 or 3 moves away
  71. * (e.g. the squares with distance (-3,0), (0, -3), (-3, -3) are the outer
  72. * corners of the NW quadrant.
  73. * The quadrants are always ordered NW then NE then SW then SE first
  74. * close and then far.
  75. * This method outputs 24 0/1 values, first the 8 zones are asked if they have
  76. * an obstacle "*" those 8 answers will be senses[0] through senses[7] in the
  77. * above mentioned order
  78. * Then each of the 8 zones is asked is they have food, "$", again 8 answers.
  79. * Finally each zone is asked if it contains a pit "X".
  80. * These will act as the rat's "senses".
  81. */
  82. string targets = "*$X";
  83. string close[4] = {"","","",""};
  84. string far[4] = {"","","",""};
  85. int quadrant[4][2] = {{-1,-1},{-1,1},{1,-1},{1,1}};
  86. for (int dx = 0; dx < 4; dx++)
  87. {
  88. for (int dy = 0; dy < 4; dy++)
  89. {
  90. for (int qi = 0; qi < 4; qi++)
  91. {
  92. int sign_x = quadrant[qi][0];
  93. int sign_y = quadrant[qi][1];
  94. if (dx == 0 && dy == 0){
  95. break;
  96. } else if (dx > 1 || dy > 1){
  97. far[qi] += value_at(x + sign_x*dx, y + sign_y*dy);
  98. } else {
  99. close[qi] += value_at(x + sign_x*dx, y + sign_y*dy);
  100. }
  101. }
  102. }
  103. }
  104. int counter = 0;
  105. bitset<24> senses;
  106. bool bit_value = 0;
  107. size_t found;
  108. for (int i = 0; i < 3; i++)
  109. {
  110. char target = targets.at(i);
  111. for (int qi = 0; qi < 4; qi++)
  112. {
  113. bit_value = 0;
  114. found = close[qi].find(target);
  115. if (string::npos != found)
  116. {
  117. bit_value = 1;
  118. }
  119. senses.set(counter, bit_value);
  120. counter++;
  121. }
  122. for (int qi = 0; qi < 4; qi++)
  123. {
  124. bit_value = 0;
  125. found = far[qi].find(target);
  126. if (string::npos != found)
  127. {
  128. bit_value = 1;
  129. }
  130. senses.set(counter, bit_value);
  131. counter++;
  132. }
  133. }
  134. return senses;
  135. }
  136.  
  137. class NeuralNet
  138. {
  139. public:
  140. NeuralNet();
  141. void setWeights(vector<double> weights);
  142. static vector<double> translateGenome(string genome);
  143. static string translateWeights(vector<double> weights);
  144. static const int n_i = 25;
  145. static const int n_h = 10;
  146. static const int n_o = 4;
  147. bitset<n_o> makeChoices(bitset<n_i> inputs);
  148. double W_ih[n_i][n_h];
  149. double W_ho[n_h][n_o];
  150. };
  151.  
  152. NeuralNet::NeuralNet(){};
  153.  
  154. void NeuralNet::setWeights(vector<double> weights)
  155. {
  156. /*
  157. * Takes in n_i*n_h + n_h*n_o double values where n_i is the number of input
  158. * neurons (25 in our case the first is "pain" (did the rat just hit an obstacle?)
  159. * the other 24 are explained above in Map::observe)
  160. * The n_h (10 by my settings) hidden neurons are there for complex behavior,
  161. * they can kind of be thought of as emotional states.
  162. * The n_o outputs will be an encoding of the rat's next movement choice.
  163. */
  164. int pos = 0;
  165. int tpos = 0;
  166. int W_ih_size = n_i*n_h;
  167. int x, y;
  168. for (vector<double>::iterator it = weights.begin(); it != weights.end(); ++it){
  169. if (pos < W_ih_size){
  170. x = int(pos/n_h);
  171. y = int(pos % n_h);
  172. W_ih[x][y] = *it;
  173. pos++;
  174. } else {
  175. tpos = pos - W_ih_size;
  176. x = int(tpos / n_o);
  177. y = int(tpos % n_o);
  178. W_ho[x][y] = *it;
  179. pos++;
  180. }
  181. }
  182. }
  183.  
  184. bitset<4> NeuralNet::makeChoices(bitset<25> inputs)
  185. {
  186. bitset<n_h> hidden;
  187. for (int i = 0; i < n_h; i++)
  188. {
  189. double res = 0.0;
  190. for (int j = 0; j < n_i; j++)
  191. {
  192. double tval = double(inputs[j])*double(W_ih[j][i]);
  193. res += tval;
  194. }
  195. /* After checking which weights from inputs affect a given hidden neuron
  196. * If there is more positive than negative we fire it.
  197. */
  198. hidden[i] = res > 0;
  199. }
  200. bitset<n_o> output;
  201. for (int i = 0; i < n_o; i++)
  202. {
  203. double res = 0.0;
  204. for (int j = 0; j < n_h; j++)
  205. {
  206. double tval = double(hidden[j])*double(W_ho[j][i]);
  207. res += tval;
  208. }
  209. output[i] = res > 0;
  210. }
  211. return output;
  212. }
  213.  
  214. vector<double> NeuralNet::translateGenome(string genome)
  215. {
  216. vector<double> temp(0);
  217. for (int i = 0; i < genome.length(); i++)
  218. {
  219. char c = genome.at(i);
  220. double temp_val = double(c) - 82.0;
  221. temp.push_back(temp_val/40.0);
  222. }
  223. return temp;
  224. }
  225.  
  226. string NeuralNet::translateWeights(vector<double> weights){
  227. string answer = "";
  228. int pos = 0;
  229. double temp = 0.0;
  230. for (vector<double>::iterator it = weights.begin(); it != weights.end(); ++it){
  231. temp = *it;
  232. temp *= 40;
  233. temp += 82;
  234. temp = round(temp);
  235. answer += char(temp);
  236. }
  237. return answer;
  238. }
  239.  
  240. class Rat
  241. {
  242. public:
  243. Rat(int start_x, int start_y, string genome);
  244. int isDead();
  245. void changeEnergy(int delta);
  246. bitset<24> observeWorld(Map world);
  247. bitset<4> makeChoices(bitset<24> senses);
  248. void enactChoices(bitset<4> choices);
  249. int x, y;
  250. bool hit_obstacle;
  251. int speed_y, speed_x, energy;
  252. private:
  253. string genome;
  254. NeuralNet brain;
  255. };
  256.  
  257. Rat::Rat(int start_x, int start_y, string genome)
  258. {
  259. x = start_x;
  260. y = start_y;
  261. speed_x = 1;
  262. speed_y = 1;
  263. energy = 30;
  264. hit_obstacle = 0;
  265. genome = genome;
  266. brain.setWeights(NeuralNet::translateGenome(genome));
  267. }
  268.  
  269. int Rat::isDead()
  270. {
  271. if (energy <= 0){
  272. return 1;
  273. } else {
  274. return 0;
  275. }
  276. }
  277.  
  278. void Rat::changeEnergy(int delta)
  279. {
  280. energy = energy + delta;
  281. }
  282.  
  283. void Rat::enactChoices(bitset<4> choices)
  284. {
  285. speed_x = choices[0] - choices[1];
  286. speed_y = choices[2] - choices[3];
  287. }
  288.  
  289. bitset<24> Rat::observeWorld(Map world)
  290. {
  291. bitset<24> observations = world.observe(x, y);
  292. return observations;
  293. }
  294.  
  295. bitset<4> Rat::makeChoices(bitset<24> observations)
  296. {
  297. bitset<25> pain_and_observations;
  298. for (int i = 1; i < 25; i++)
  299. {
  300. pain_and_observations[i] = observations[i-1];
  301. }
  302. pain_and_observations[0] = hit_obstacle;
  303. bitset<4> choices = brain.makeChoices(pain_and_observations);
  304.  
  305. /* To see input observations and output decisions uncomment the below code
  306. cout << "observed "<< pain_and_observations.template to_string<char,
  307.   std::char_traits<char>,
  308.   std::allocator<char> >() << endl;
  309. cout << "chose to do: "<< choices.template to_string<char,
  310.   std::char_traits<char>,
  311.   std::allocator<char> >() << endl;*/
  312. /* choices[0] is the choice to move down by 1, choices[1] is to move up by 1,
  313. * choices[2] is to move right by 1, choices[3] is to move left by 1
  314. * if all four are 1 then the rat doesn't move for example, while if it is
  315. * choices[0] = 1, choices[1] = 0, choices[2] = 0 and choices[3] = 1 then it moves
  316. * down and left */
  317. return choices;
  318. }
  319.  
  320. int simulator(string mapseed, string genome, int start_x, int start_y)
  321. {
  322. Map board(mapseed);
  323. Rat arat(start_x, start_y, genome);
  324. int cur_x, cur_y;
  325. int target_x, target_y;
  326. int dx, dy;
  327. char next_spot;
  328. int moves = 0;
  329. while (!arat.isDead())
  330. {
  331. moves++;
  332. cur_x = arat.x;
  333. cur_y = arat.y;
  334. cout << "rat at "<< cur_x << " by " << cur_y << " on move " << moves << endl;
  335. arat.enactChoices(arat.makeChoices(arat.observeWorld(board)));
  336. target_x = cur_x + arat.speed_x;
  337. target_y = cur_y + arat.speed_y;
  338. next_spot = board.value_at(target_x, target_y);
  339. arat.hit_obstacle = 0;
  340. if (char(next_spot) == char('$'))
  341. {
  342. arat.changeEnergy(10);
  343. board.set_value_at(target_x, target_y, '.');
  344. } else if (char(next_spot) == char('X'))
  345. {
  346. arat.energy = 0;
  347. } else if (char(next_spot) == char('*'))
  348. {
  349. arat.hit_obstacle = 1;
  350. arat.changeEnergy(-10);
  351. target_x = cur_x;
  352. target_y = cur_y;
  353. }
  354. arat.changeEnergy(-1);
  355. arat.x = target_x;
  356. arat.y = target_y;
  357. }
  358. return moves;
  359. }
  360.  
  361. int main(void){
  362. string mapseed = "25:25:..$.$.X.............X....$X.X*..X$..X...*X$..$...X$.$......X.$.X...XX.$.X*.*.*..X..X.**.......X..$$$...........XX.....................$...X...*.$..X..$X..........$.*..X.....$.X..$*.$X......$...X.*X$......$.**.X.X..XX$X..*....*..X.X....$...X...X........$.X....$...*...X$*........X..$*$$......$$...$*..X.$.$......$.$.$...$..X.*.....X..$......$.XX*..X.$.X......X$*.**.....X*...$..XX..X.....$....X....X...X....X.$X$..X..........$...*.X$..X...$*...........*....XXX$$.$.$..*$XX..XX..*.....$......X.XX$..$$..X$.XX.$$..X.*..*......X......$..$.$$..*...X.........$X....$X.$$.*.$.$.$..**.....X.$.$X.*.$.........$**..X.X.X$X.$.*X.X*..$*.";
  363. string genome = "Sfz2smu:zej,9j:R\\[thR73RzRdP0U.v2TF9-X/PTlOPdYF+k1N;o3`[uTfT>RTq:rsTBk:gYlNq-[@OmMrvVo^U\\z=JV>l.tAq*\\BLM3vJQLfnnpr_mN-7RN;^.-9j4ddZKXN,gvH;x:qYAgPz+tb29Li[qJ/jH+UepmPpV0qC^u2tpvl_/Z-`OTmijR@XW5iJRk0/\\ztnzDHBu+HmsY*,AlZy`aJZ?WFQf*?>3`z6\\TiU+O,MvIH\\7zL?:=/.w^V/XH-`[X+8L7.+zxDBEm;jwW29jp/oj<Y";
  364. /*Note the escaped backslashes \\ as opposed to just ascii \*/
  365. int start_row = 12;
  366. int start_col = 12;
  367. cout << "Length of genome: " << genome.length() << endl;
  368.  
  369. int moves = simulator(mapseed, genome, start_row, start_col);
  370. /* NOTE that I mistakenly use x for row and y for column throughout the code*/
  371. cout << "This rat lasted " << moves << " moves." << endl;
  372.  
  373. return 0;
  374. }
Success #stdin #stdout 0s 3440KB
stdin
Standard input is empty
stdout
Length of genome: 290
rat at 12 by 12 on move 1
rat at 11 by 13 on move 2
rat at 10 by 14 on move 3
rat at 9 by 15 on move 4
rat at 8 by 16 on move 5
rat at 7 by 17 on move 6
rat at 6 by 18 on move 7
rat at 5 by 19 on move 8
rat at 4 by 20 on move 9
rat at 3 by 21 on move 10
This rat lasted 10 moves.