1 /*
2 * File prepared by Paweł Parys
3 */
4
5 #include <stack>
6 #include <queue>
7 #include <cassert>
8 #include <climits>
9 #include <numeric> // for iota
10
11 #include "zlkpp.hpp"
12
13 namespace pg {
14
ZLKPPSolver(Oink * oink,Game * game,int variant)15 ZLKPPSolver::ZLKPPSolver(Oink *oink, Game *game, int variant) : Solver(oink, game), variant(variant) {}
16
get_attractor(int player,std::vector<int> & nodes)17 bool ZLKPPSolver::get_attractor(int player, std::vector<int> &nodes) {
18 // initially is_in_attractor[v] = 0 and num_successors[v] = -1 for all v
19
20 std::queue<int> Q;
21 std::vector<int> to_be_cleaned;
22 bool changed = false;
23
24 for (int v : nodes) {
25 is_in_attractor[v] = true;
26 Q.push(v);
27 }
28
29 while (!Q.empty()) {
30 int v = Q.front();
31 Q.pop();
32 for (const int *ptr2 = ins(v); *ptr2 >= 0; ++ptr2) {
33 int v2 = *ptr2; // predecessor of v
34 if (!cur_nodes_bm[v2] || is_in_attractor[v2])
35 continue;
36 if (owner(v2) != player) {
37 if (num_successors[v2] < 0) {
38 // initially num_successors is -1, so at the end v is automatically subtracted
39 for (const int *ptr3 = outs(v2); *ptr3 >= 0; ++ptr3)
40 if (cur_nodes_bm[*ptr3])
41 ++num_successors[v2];
42 assert(num_successors[v2] >= 0);
43 to_be_cleaned.push_back(v2);
44 }
45 else
46 --num_successors[v2];
47 if (num_successors[v2])
48 continue;
49 }
50 else
51 strategy[v2] = v;
52 is_in_attractor[v2] = true;
53 nodes.push_back(v2);
54 changed = true;
55 Q.push(v2);
56 }
57 }
58
59 // cleanup
60 for (int v : nodes)
61 is_in_attractor[v] = false;
62 for (int v : to_be_cleaned)
63 num_successors[v] = -1;
64
65 // returned value = have we added any nodes to the attractor
66 return changed;
67 }
68
remove_nodes(const std::vector<int> nodes)69 void ZLKPPSolver::remove_nodes(const std::vector<int> nodes) { // "nodes" need not to be sorted
70 for (int v : nodes) {
71 cur_nodes_bm[v] = false;
72 cur_nodes_next[cur_nodes_prev[v]] = cur_nodes_next[v];
73 cur_nodes_prev[cur_nodes_next[v]] = cur_nodes_prev[v];
74 if (v == cur_first_node)
75 cur_first_node = cur_nodes_next[v];
76 }
77 cur_num_nodes -= nodes.size();
78 }
79
restore_nodes(const std::vector<int> nodes)80 void ZLKPPSolver::restore_nodes(const std::vector<int> nodes) {
81 // we assume that "nodes" were previously removed by "remove_nodes" (and that they were not used in between, so links in these nodes are correct)
82 for (auto it = nodes.rbegin(); it != nodes.rend(); ++it) {
83 int v = *it;
84 cur_nodes_bm[v] = true;
85 cur_nodes_next[cur_nodes_prev[v]] = v;
86 cur_nodes_prev[cur_nodes_next[v]] = v;
87 if (cur_nodes_prev[v] >= v)
88 cur_first_node = v;
89 }
90 cur_num_nodes += nodes.size();
91 }
92
get_cur_nodes()93 std::vector<int> ZLKPPSolver::get_cur_nodes() {
94 std::vector<int> ret;
95 if (cur_num_nodes) {
96 int v = cur_first_node;
97 for (;;) {
98 ret.push_back(v);
99 v = cur_nodes_next[v];
100 if (v == cur_first_node)
101 break;
102 }
103 }
104 return ret;
105 }
106
set_cur_nodes(const std::vector<int> nodes)107 void ZLKPPSolver::set_cur_nodes(const std::vector<int> nodes) { // it assumes that the "current game" is a subset of "nodes", and that "nodes" are sorted
108 assert(!nodes.empty()); // we assume that "nodes" is nonempty
109 for (unsigned int a = 0; a < nodes.size(); ++a) {
110 int v = nodes[a], v2 = nodes[(a + 1) % nodes.size()];
111 cur_nodes_bm[v] = true;
112 cur_nodes_next[v] = v2;
113 cur_nodes_prev[v2] = v;
114 }
115 cur_first_node = nodes.front();
116 cur_num_nodes = nodes.size();
117 }
118
get_nodes_of_max_priority(int max_priority)119 std::vector<int> ZLKPPSolver::get_nodes_of_max_priority(int max_priority) {
120 std::vector<int> top;
121 if (!cur_num_nodes)
122 return top;
123 int v = cur_nodes_prev[cur_first_node];
124 while (priority(v) == max_priority) {
125 top.push_back(v);
126 const int *ptr2 = outs(v);
127 for (;; ++ptr2) {
128 assert(*ptr2 >= 0);
129 if (cur_nodes_bm[*ptr2])
130 break;
131 }
132 strategy[v] = *ptr2; // we can go to an arbitrary node that is currently in the game
133 if (v == cur_first_node)
134 break;
135 v = cur_nodes_prev[v];
136 }
137 return top; // the returned vector is sorted
138 }
139
do_step(int max_priority,int prec_cur,int prec_opo,int & num_nodes_in_h,bool & reached_bottom_cur,bool & reached_bottom_opo)140 bool ZLKPPSolver::do_step(int max_priority, int prec_cur, int prec_opo, int &num_nodes_in_h, bool &reached_bottom_cur, bool &reached_bottom_opo) {
141 num_nodes_in_h = INT_MAX;
142 if (!cur_num_nodes)
143 return false;
144 if (prec_opo < min_dominion) {
145 reached_bottom_opo = true;
146 return false;
147 }
148 ++iterations;
149 assert(cur_num_nodes); // we assume that the current game is nonempty
150 auto top = get_nodes_of_max_priority(max_priority);
151 get_attractor(max_priority % 2, top);
152 remove_nodes(top);
153 auto lose = solve(max_priority - 1, prec_opo, prec_cur, reached_bottom_opo, reached_bottom_cur);
154 num_nodes_in_h = cur_num_nodes;
155 restore_nodes(top);
156 bool changed = get_attractor((max_priority - 1) % 2, lose);
157 remove_nodes(lose);
158 return changed;
159 }
160
solve_liverpool(int max_priority,int prec_cur,int prec_opo,bool & reached_bottom_cur,bool & reached_bottom_opo)161 void ZLKPPSolver::solve_liverpool(int max_priority, int prec_cur, int prec_opo, bool &reached_bottom_cur, bool &reached_bottom_opo) {
162 int initial_num_nodes = cur_num_nodes, dummy;
163 if (prec_opo / 2 >= min_dominion)
164 solve_liverpool(max_priority, prec_cur, prec_opo / 2, reached_bottom_cur, reached_bottom_opo);
165 if (initial_num_nodes <= prec_opo / 2)
166 return;
167 if (do_step(max_priority, prec_cur, prec_opo, dummy, reached_bottom_cur, reached_bottom_opo) && prec_opo / 2 >= min_dominion)
168 solve_liverpool(max_priority, prec_cur, prec_opo / 2, reached_bottom_cur, reached_bottom_opo);
169 }
170
solve(int max_priority,int prec_cur,int prec_opo,bool & reached_bottom_cur,bool & reached_bottom_opo)171 std::vector<int> ZLKPPSolver::solve(int max_priority, int prec_cur, int prec_opo, bool &reached_bottom_cur, bool &reached_bottom_opo) {
172 if (!cur_num_nodes)
173 return std::vector<int>();
174 auto saved_nodes = get_cur_nodes();
175 int num_nodes_in_h;
176 switch (variant) {
177
178 case ZLK_STANDARD:
179 while (do_step(max_priority, prec_cur, prec_opo, num_nodes_in_h, reached_bottom_cur, reached_bottom_opo));
180 break;
181
182 case ZLK_WARSAW:
183 bool reached_bottom_opo_last, atr_greater;
184 atr_greater = true;
185 while (atr_greater) {
186 reached_bottom_opo_last = false;
187 atr_greater = do_step(max_priority, prec_cur, prec_opo / 2, num_nodes_in_h, reached_bottom_cur, reached_bottom_opo_last);
188 reached_bottom_opo |= reached_bottom_opo_last;
189 }
190 if (num_nodes_in_h <= prec_opo / 2 || !reached_bottom_opo_last)
191 break;
192 if (do_step(max_priority, prec_cur, prec_opo, num_nodes_in_h, reached_bottom_cur, reached_bottom_opo))
193 while (do_step(max_priority, prec_cur, prec_opo / 2, num_nodes_in_h, reached_bottom_cur, reached_bottom_opo));
194 break;
195
196 case ZLK_LIVERPOOL:
197 solve_liverpool(max_priority, prec_cur, prec_opo, reached_bottom_cur, reached_bottom_opo);
198 break;
199 }
200
201 // we should set strategy in nodes of maximal priority to an arbitrary node that remains in the subgame now:
202 get_nodes_of_max_priority(max_priority);
203
204 auto winning_region = get_cur_nodes();
205 set_cur_nodes(saved_nodes); // the current game remains unchanged at the end
206 return winning_region;
207 }
208
run()209 void ZLKPPSolver::run() {
210 min_dominion = 2;
211 for (int v = 0; v < nodecount(); ++v)
212 for (const int *ptr2 = outs(v); *ptr2 >= 0; ++ptr2)
213 if (*ptr2 == v) {
214 min_dominion = 1;
215 goto finish;
216 }
217 finish:
218
219 iterations = 0;
220
221 cur_nodes_bm = new bool[nodecount()];
222 std::fill(cur_nodes_bm, cur_nodes_bm + nodecount(), true);
223
224 cur_nodes_next = new int[nodecount()];
225 std::iota(cur_nodes_next, cur_nodes_next + nodecount() - 1, 1);
226 cur_nodes_next[nodecount() - 1] = 0;
227
228 cur_nodes_prev = new int[nodecount()];
229 std::iota(cur_nodes_prev + 1, cur_nodes_prev + nodecount(), 0);
230 cur_nodes_prev[0] = nodecount() - 1;
231
232 cur_first_node = 0;
233
234 cur_num_nodes = nodecount();
235
236 num_successors = new int[nodecount()];
237 std::fill(num_successors, num_successors + nodecount(), -1);
238
239 is_in_attractor = new bool[nodecount()];
240 std::fill(is_in_attractor, is_in_attractor + nodecount(), 0);
241
242 strategy = new int[nodecount()];
243
244 // remove disabled nodes (they could be disabled by preprocessing)
245 for (int v = 0; v < nodecount(); ++v)
246 if (disabled[v])
247 remove_nodes(std::vector<int>(1, v));
248
249 assert(cur_num_nodes);
250 int max_priority = priority(cur_nodes_prev[cur_first_node]);
251 int pow2 = 0;
252 while ((1 << pow2) - 1 < nodecount())
253 ++pow2;
254 bool reached_bottom_cur, reached_bottom_opo;
255 auto win = solve(max_priority, (1 << pow2) - 1, (1 << pow2) - 1, reached_bottom_cur, reached_bottom_opo);
256
257 int player = max_priority % 2;
258 for (int v = cur_nodes_prev[cur_first_node];;) {
259 int who;
260 if (!win.empty() && win.back() == v) {
261 who = player;
262 win.pop_back();
263 } else
264 who = !player;
265 oink->solve(v, who, strategy[v]);
266 if (v == cur_first_node)
267 break;
268 v = cur_nodes_prev[v];
269 }
270
271 logger << "solved with " << iterations << " iterations." << std::endl;
272
273 delete[] cur_nodes_bm;
274 delete[] cur_nodes_next;
275 delete[] cur_nodes_prev;
276 delete[] num_successors;
277 delete[] is_in_attractor;
278 delete[] strategy;
279 }
280
281 }
282