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