1 /* 2 * Copyright 2017-2018 Massimo Benerecetti, Fabio Mogavero, Daniele Dell'Erba 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 #ifndef NPP_HPP 18 #define NPP_HPP 19 20 #include <list> 21 #include <deque> 22 #include <vector> 23 24 #include "oink.hpp" 25 #include "solver.hpp" 26 #include "uintqueue.hpp" 27 28 namespace pg 29 { 30 31 #define _INLINE_ __attribute__((always_inline)) 32 33 class NPPSolver : public Solver 34 { 35 public: 36 /******************************************************************************/ 37 /* Constructor and destructor */ 38 /******************************************************************************/ 39 40 NPPSolver(Oink * oink, Game * game); 41 42 virtual ~NPPSolver(); 43 44 /******************************************************************************/ 45 46 /******************************************************************************/ 47 /* Main method */ 48 /******************************************************************************/ 49 50 // Main solver function 51 virtual void run(); 52 53 /******************************************************************************/ 54 55 protected: 56 57 /******************************************************************************/ 58 /* Typedefs */ 59 /******************************************************************************/ 60 61 typedef unsigned int uint; 62 63 typedef std::deque<uint> uideque; 64 65 typedef std::list<uideque> uidlist; 66 67 typedef std::vector<bool> bvector; 68 69 typedef std::vector<uideque *> uidvector; 70 71 typedef std::vector<bitset *> bsvector; 72 73 typedef std::vector<uidlist *> uidlvector; 74 75 /******************************************************************************/ 76 77 /******************************************************************************/ 78 /* Statistic fields */ 79 /******************************************************************************/ 80 81 uint totqueries; // Total number of queries needed for the game solution 82 uint totpromos; // Total number of promotions needed for the game solution 83 84 uint maxqueries; // Maximal number of queries needed for finding a dominion 85 uint maxpromos; // Maximal number of promotions needed for finding a dominion 86 87 uint queries; // Current number of queries 88 uint promos; // Current number of promotions 89 90 uint doms; // Number of dominions found 91 92 /******************************************************************************/ 93 94 /******************************************************************************/ 95 /* Game fields */ 96 /******************************************************************************/ 97 98 uint maxprio; // Maximal priority 99 100 int * strategy; // Strategies of the players 101 102 int * inverse; // Maximal positions associated with the priorities 103 104 bitset outgame; // Positions whose winner has been already determined 105 106 bitset winzero; // Positions already won by player zero 107 108 /******************************************************************************/ 109 110 /******************************************************************************/ 111 /* Stack fields */ 112 /******************************************************************************/ 113 114 uint Top; // Index of the current element within the vectors 115 uint End; // Index of the last element within the vectors 116 uint Pivot; // Index of the element associated with the region variables 117 118 bvector Phase; // Stack of phases 119 120 bsvector Supgame; // Stack of supgames 121 122 uidvector Heads; // Stack of region heads 123 124 bsvector Exits; // Stack of region promotion exits 125 126 uidlvector Entries; // Stack of region potential entriers 127 128 /******************************************************************************/ 129 130 /******************************************************************************/ 131 /* Current region fields */ 132 /******************************************************************************/ 133 134 bitset R; // Positions in the current region 135 136 uint alpha; // Player of the current region R 137 138 /******************************************************************************/ 139 140 /******************************************************************************/ 141 /* Previous region fields */ 142 /******************************************************************************/ 143 144 bitset D; // Positions in the previous region upward along the stack 145 146 uint beta; // Previous region player (player of region D) 147 148 /******************************************************************************/ 149 150 /******************************************************************************/ 151 /* Accessory region fields */ 152 /******************************************************************************/ 153 154 int pos; // Working position 155 156 uint p; // Working priority 157 158 bitset O; // Bitset of open heads of the current region R 159 160 uintqueue T; // Tail queue for positions waiting for attraction 161 162 uintqueue E; // Exits queue for positions waiting for inclusion as exits 163 164 /******************************************************************************/ 165 166 /******************************************************************************/ 167 /* Accessory methods */ 168 /******************************************************************************/ 169 170 // Attractor functions 171 virtual bool atrongame(); 172 virtual void atronsubgamedw(); 173 virtual bool atronsubgameup(); 174 175 /******************************************************************************/ 176 177 /******************************************************************************/ 178 /* Solver method */ 179 /******************************************************************************/ 180 181 // Search function 182 inline virtual void search(); 183 184 /******************************************************************************/ 185 186 private: 187 188 /******************************************************************************/ 189 /* Accessory methods */ 190 /******************************************************************************/ 191 192 // Go up/down functions 193 inline void goup(); 194 inline void godwdw(); 195 inline void godwup(); 196 197 // Top stack handler functions 198 inline void newstackslot(); 199 inline void clearstackslot(); 200 201 // Next priority and position function 202 inline void nextpriopos(); 203 204 // Push in queue functions 205 inline void pushinqueueongame(uint pos); 206 inline void pushinqueueonsubgamedw(uint pos); 207 inline void pushinqueueonsubgameup(uint pos); 208 209 // Is closed functions 210 inline bool isclosedongame(uint pos); 211 inline bool isclosedonsubgame(uint pos); 212 inline bool isclosedonsubgamepromo(uint pos); 213 inline bool isplayerclosed(uint pos); 214 inline bool isplayerclosedpromo(uint pos); 215 inline bool isopponentclosedongame(uint pos); 216 inline bool isopponentclosedonsubgame(uint pos); 217 218 /******************************************************************************/ 219 }; 220 221 } 222 223 #endif 224