1 /*
2 * Copyright 2017-2018 Massimo Benerecetti, Fabio Mogavero, Daniele Dell'Erba
3 * Copyright 2018 Tom van Dijk
4 *
5 * Licensed under the Apache License, Version 2.0 (the "License");
6 * you may not use this file except in compliance with the License.
7 * You may obtain a copy of the License at
8 *
9 * http://www.apache.org/licenses/LICENSE-2.0
10 *
11 * Unless required by applicable law or agreed to in writing, software
12 * distributed under the License is distributed on an "AS IS" BASIS,
13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 * See the License for the specific language governing permissions and
15 * limitations under the License.
16 */
17
18 #include "npp.hpp"
19
20 namespace pg {
21
NPPSolver(Oink * oink,Game * game)22 NPPSolver::NPPSolver(Oink * oink, Game * game) :
23 Solver(oink, game),
24 totqueries(0), totpromos(0), maxqueries(0), maxpromos(0), queries(0), promos(0), doms(0),
25 maxprio(priority(nodecount() - 1)), strategy(game->strategy), inverse(new int[maxprio + 1]),
26 Top(0), End(0), Pivot(0)
27 {
28 uint resprio = maxprio / 20;
29 resprio = (resprio >= 500) ? resprio : 500;
30 outgame.resize(nodecount());
31 winzero.resize(nodecount());
32 Phase.reserve(resprio);
33 Supgame.reserve(resprio);
34 Heads.reserve(resprio);
35 Exits.reserve(resprio);
36 Entries.reserve(resprio);
37 R.resize(nodecount());
38 T.resize(nodecount());
39 E.resize(nodecount());
40 }
41
~NPPSolver()42 NPPSolver::~NPPSolver()
43 {
44 delete[] inverse;
45 delete Heads[0];
46 delete Exits[0];
47 delete Entries[0];
48 for (uint i = 1; i <= End; ++i)
49 {
50 delete Supgame[i];
51 delete Heads[i];
52 delete Exits[i];
53 delete Entries[i];
54 }
55 }
56
isplayerclosed(uint pos)57 _INLINE_ bool NPPSolver::isplayerclosed(uint pos)
58 {
59 for (auto curedge = outs(pos); *curedge != -1; curedge++) {
60 int to = *curedge;
61 if (R[to])
62 {
63 strategy[pos] = (!R[pos] || strategy[pos] == -1) ? to : strategy[pos];
64 return (true);
65 }
66 }
67 return (false);
68 }
69
isplayerclosedpromo(uint pos)70 _INLINE_ bool NPPSolver::isplayerclosedpromo(uint pos)
71 {
72 for (auto curedge = outs(pos); *curedge != -1; curedge++)
73 {
74 int to = *curedge;
75 if (R[to])
76 {
77 strategy[pos] = to;
78 return (true);
79 }
80 }
81 return (false);
82 }
83
isopponentclosedongame(uint pos)84 _INLINE_ bool NPPSolver::isopponentclosedongame(uint pos)
85 {
86 for (auto curedge = outs(pos); *curedge != -1; curedge++)
87 {
88 int to = *curedge;
89 if (outgame[to] || R[to])
90 {
91 continue;
92 }
93 else
94 {
95 return (false);
96 }
97 }
98 strategy[pos] = -1;
99 return (true);
100 }
101
isopponentclosedonsubgame(uint pos)102 _INLINE_ bool NPPSolver::isopponentclosedonsubgame(uint pos)
103 {
104 auto & supgame = *(Supgame[Top]);
105 for (auto curedge = outs(pos); *curedge != -1; curedge++)
106 {
107 int to = *curedge;
108 if (outgame[to] || R[to])
109 {
110 continue;
111 }
112 else if (supgame[to])
113 {
114 E.push(to);
115 }
116 else
117 {
118 E.clear();
119 return (false);
120 }
121 }
122 auto & exits = *(Exits[Pivot]);
123 while (E.nonempty())
124 {
125 exits[E.pop()] = true;
126 }
127 strategy[pos] = -1;
128 return (true);
129 }
130
isclosedongame(uint pos)131 _INLINE_ bool NPPSolver::isclosedongame(uint pos)
132 {
133 if ((uint) owner(pos) == alpha)
134 {
135 return (isplayerclosed(pos));
136 }
137 else
138 {
139 return (isopponentclosedongame(pos));
140 }
141 }
142
isclosedonsubgame(uint pos)143 _INLINE_ bool NPPSolver::isclosedonsubgame(uint pos)
144 {
145 if ((uint) owner(pos) == alpha)
146 {
147 return (isplayerclosed(pos));
148 }
149 else
150 {
151 return (isopponentclosedonsubgame(pos));
152 }
153 }
154
isclosedonsubgamepromo(uint pos)155 _INLINE_ bool NPPSolver::isclosedonsubgamepromo(uint pos)
156 {
157 if ((uint) owner(pos) == alpha)
158 {
159 return (isplayerclosedpromo(pos));
160 }
161 else
162 {
163 return (isopponentclosedonsubgame(pos));
164 }
165 }
166
pushinqueueongame(uint pos)167 _INLINE_ void NPPSolver::pushinqueueongame(uint pos)
168 {
169 for (auto curedge = ins(pos); *curedge != -1; curedge++)
170 {
171 int from = *curedge;
172 if (outgame[from] || R[from])
173 {
174 continue;
175 }
176 else if ((uint) owner(from) == alpha)
177 {
178 R[from] = true;
179 strategy[from] = pos;
180 T.push(from);
181 }
182 else
183 {
184 if (isopponentclosedongame(from))
185 {
186 R[from] = true;
187 T.push(from);
188 }
189 }
190 }
191 }
192
atrongame()193 bool NPPSolver::atrongame()
194 {
195 auto & entries = *(Entries[Top]);
196 auto lend = entries.end();
197 for (auto liter = entries.begin(); liter != lend; ++liter)
198 {
199 auto & rdeque = *liter;
200 auto dend = rdeque.end();
201 for (auto diter = rdeque.begin(); diter != dend; ++diter)
202 {
203 pos = *diter;
204 if (!R[pos] && isclosedongame(pos))
205 {
206 R[pos] = true;
207 T.push(pos);
208 }
209 }
210 }
211 if (T.nonempty())
212 {
213 do
214 {
215 pushinqueueongame(T.pop());
216 }
217 while (T.nonempty());
218 return (true);
219 }
220 else
221 {
222 return (false);
223 }
224 }
225
pushinqueueonsubgamedw(uint pos)226 _INLINE_ void NPPSolver::pushinqueueonsubgamedw(uint pos)
227 {
228 auto & supgame = *(Supgame[Top]);
229 auto & entries = *(Entries[Top]->begin());
230 for (auto curedge = ins(pos); *curedge != -1; curedge++)
231 {
232 int from = *curedge;
233 if (outgame[from])
234 {
235 continue;
236 }
237 else if (supgame[from])
238 {
239 entries.push_back(from);
240 continue;
241 }
242 else if ((uint) owner(from) == alpha)
243 {
244 if (!R[from])
245 {
246 R[from] = true;
247 strategy[from] = pos;
248 T.push(from);
249 }
250 else if (O[from])
251 {
252 O[from] = false;
253 strategy[from] = pos;
254 }
255 }
256 else if (!R[from])
257 {
258 if (isopponentclosedonsubgame(from))
259 {
260 R[from] = true;
261 T.push(from);
262 }
263 }
264 else if (O[from])
265 {
266 if (isopponentclosedonsubgame(from))
267 {
268 O[from] = false;
269 }
270 }
271 }
272 }
273
atronsubgamedw()274 void NPPSolver::atronsubgamedw()
275 {
276 auto & heads = *(Heads[Top]);
277 auto qend = heads.end();
278 for (auto qiter = heads.begin(); qiter != qend; ++qiter)
279 {
280 pushinqueueonsubgamedw(*qiter);
281 }
282 while (T.nonempty())
283 {
284 pushinqueueonsubgamedw(T.pop());
285 }
286 }
287
pushinqueueonsubgameup(uint pos)288 _INLINE_ void NPPSolver::pushinqueueonsubgameup(uint pos)
289 {
290 auto & supgame = *(Supgame[Top]);
291 auto & entries = *(Entries[Pivot]->begin());
292 for (auto curedge = ins(pos); *curedge != -1; curedge++)
293 {
294 int from = *curedge;
295 if (outgame[from] || R[from])
296 {
297 continue;
298 }
299 else if (supgame[from])
300 {
301 entries.push_back(from);
302 continue;
303 }
304 else if ((uint) owner(from) == alpha)
305 {
306 R[from] = true;
307 strategy[from] = pos;
308 T.push(from);
309 }
310 else
311 {
312 if (isopponentclosedonsubgame(from))
313 {
314 R[from] = true;
315 T.push(from);
316 }
317 }
318 }
319 }
320
atronsubgameup()321 bool NPPSolver::atronsubgameup()
322 {
323 auto & supgame = *(Supgame[Top]);
324 auto & entries = *(Entries[Pivot]);
325 auto lend = entries.end();
326 for (auto liter = entries.begin(); liter != lend; ++liter)
327 {
328 auto & rdeque = *liter;
329 auto dend = rdeque.end();
330 for (auto diter = rdeque.begin(); diter != dend; ++diter)
331 {
332 pos = *diter;
333 if (!supgame[pos] && !R[pos] && isclosedonsubgame(pos))
334 {
335 R[pos] = true;
336 T.push(pos);
337 }
338 }
339 }
340 if (T.nonempty())
341 {
342 do
343 {
344 pushinqueueonsubgameup(T.pop());
345 }
346 while (T.nonempty());
347 return (true);
348 }
349 else
350 {
351 return (false);
352 }
353 }
354
goup()355 _INLINE_ void NPPSolver::goup()
356 {
357 D = *(Supgame[Top]) - *(Supgame[Top - 1]);
358 p = priority(Heads[--Top]->front());
359 beta = p & 1;
360 }
361
newstackslot()362 _INLINE_ void NPPSolver::newstackslot()
363 {
364 Phase.push_back(true);
365 Supgame.push_back(new bitset(R | *(Supgame[Top])));
366 Pivot = End = ++Top;
367 Heads.push_back(new uideque());
368 Exits.push_back(new bitset(nodecount()));
369 Entries.push_back(new uidlist());
370 Entries[Top]->push_front(uideque());
371 }
372
clearstackslot()373 _INLINE_ void NPPSolver::clearstackslot()
374 {
375 Pivot = ++Top;
376 Phase[Top] = true;
377 *(Supgame[Top]) = *(Supgame[Top - 1]);
378 *(Supgame[Top]) |= R;
379 Heads[Top]->clear();
380 Exits[Top]->reset();
381 Entries[Top]->clear();
382 Entries[Top]->push_front(uideque());
383 }
384
nextpriopos()385 _INLINE_ void NPPSolver::nextpriopos()
386 {
387 auto & supgame = *(Supgame[Top]);
388 int pstar;
389 for (pstar = p - 1; inverse[pstar] == -1; --pstar)
390 {
391 }
392 for (p = pstar, pos = inverse[p]; supgame[pos]; p = priority(--pos))
393 {
394 }
395 alpha = p & 1;
396 R.reset();
397 }
398
godwdw()399 _INLINE_ void NPPSolver::godwdw()
400 {
401 Phase[Top] = false;
402 if (Top >= End) // A new stack slot needs to be allocated
403 {
404 newstackslot();
405 }
406 else // It can reuse some previous stack slot
407 {
408 clearstackslot();
409 }
410 nextpriopos();
411 }
412
godwup()413 _INLINE_ void NPPSolver::godwup()
414 {
415 Phase[Top] = false;
416 clearstackslot();
417 nextpriopos();
418 }
419
search()420 _INLINE_ void NPPSolver::search()
421 {
422
423 /* vv Resetting local statistics vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv */
424 queries = 0;
425 promos = 0;
426 /* ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ */
427
428 while (true)
429 {
430 if (Phase[Top])
431 {
432
433 /* vv Update of the statistic on the number of queries vvvvvvvvvvvvvvvv */
434 ++queries;
435 /* ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ */
436
437 /* vv Search of region heads vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv */
438 auto & supgame = *(Supgame[Top]);
439 auto & heads = *(Heads[Top]);
440 for (; pos >= 0 && (uint) priority(pos) == p; --pos) // Collect heads of the region
441 {
442 if (!supgame[pos])
443 {
444 R[pos] = true;
445 heads.push_front(pos);
446 }
447 }
448 O = R; // Mark the heads of the new region as open heads
449 /* ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ */
450
451 /* vv Region construction via attractor vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv */
452 atronsubgamedw();
453 /* ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ */
454
455 /* vv Determine the successor state vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv */
456 if (O.none()) // No heads of the region are open
457 {
458 if (Exits[Top]->none())
459 {
460 break; // Region closed in the whole game (i.e. it is dominion)
461 }
462 else
463 {
464 goup(); // Region closed in the subgame, look upward for the target of the promotion
465 }
466 }
467 else
468 {
469 godwdw(); // Region open, descend further
470 }
471 /* ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ */
472
473 }
474 else
475 {
476 auto & pivotexits = *(Exits[Pivot]);
477 if (alpha != beta || (D & pivotexits).none())
478 {
479 goup(); // Target D is of the opponent or R cannot enter D (i.e., BEP not found yet), go further up
480 }
481 else // Target of the promotion found (BEP)
482 {
483
484 /* vv Update of the statistics on the number of queries and promotions*/
485 ++queries;
486 ++promos;
487 /* ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ */
488
489 /* vv Region merging and maximization via attractor vvvvvvvvvvvvvvvvv */
490 R |= D;
491 atronsubgameup();
492 /* ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ */
493
494 /* vv Closure check vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv */
495 bool closed = true;
496 auto & heads = *(Heads[Top]);
497 while (!heads.empty())
498 {
499 pos = heads.front();
500 if (isclosedonsubgamepromo(pos))
501 {
502 heads.pop_front();
503 }
504 else
505 {
506 closed = false;
507 break;
508 }
509 }
510 /* ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ */
511
512 /* vv Update of promotion exists vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv */
513 pivotexits -= D;
514 *(Exits[Top]) |= pivotexits;
515 /* ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ */
516
517 /* vv Update of potential region entries vvvvvvvvvvvvvvvvvvvvvvvvvvvv */
518 auto & topentries = *(Entries[Top]);
519 auto & pivotentries = *(Entries[Pivot]);
520 topentries.splice(topentries.end(), pivotentries);
521 /* ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ */
522
523 /* vv Determine the successor state vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv */
524 Pivot = Top;
525 if (closed)
526 {
527 if (Exits[Top]->none())
528 {
529 break; // Region closed in the game (i.e. it is dominion)
530 }
531 else
532 {
533 goup(); // Region closed in the subgame, look upward for the target of the promotion
534 }
535 }
536 else
537 {
538 godwup(); // Region open, start new descent
539 }
540 /* ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ */
541
542 }
543 }
544 }
545
546 /* vv Update of the statistics on the number of queries and promotions vvvv */
547 totqueries += queries;
548 totpromos += promos;
549 if (queries > maxqueries)
550 {
551 maxqueries = queries;
552 }
553 if (promos > maxpromos)
554 {
555 maxpromos = promos;
556 }
557 /* ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ */
558
559 /* vv Dominion extension via attractor vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv */
560 atrongame();
561 /* ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ */
562
563 }
564
run()565 void NPPSolver::run()
566 {
567
568 /* vv Stack initialization vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv */
569 Phase.push_back(true);
570 Supgame.push_back(&outgame);
571 Heads.push_back(new uideque());
572 Exits.push_back(new bitset(nodecount()));
573 Entries.push_back(new uidlist());
574 Entries[0]->push_front(std::move(uideque()));
575 /* ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ */
576
577 /* vv Initialization of pos and maxprio vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv */
578 for (pos = nodecount() - 1;; --pos)
579 {
580 if (disabled[pos])
581 {
582 outgame[pos] = true;
583 }
584 else
585 {
586 maxprio = priority(pos);
587 break;
588 }
589 }
590 /* ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ */
591
592 /* vv Initialization of inverse, outgame, and strategy vvvvvvvvvvvvvvvvvvvv */
593 for (uint prt = 0; prt <= maxprio; ++prt)
594 {
595 inverse[prt] = -1;
596 }
597 for (int sop = 0; sop <= pos; sop++)
598 {
599 if (disabled[sop])
600 {
601 outgame[sop] = true;
602 }
603 else
604 {
605 inverse[priority(sop)] = sop;
606 strategy[sop] = -1;
607 }
608 }
609 /* ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ */
610
611 /* vv Main solution cycle vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv */
612 while (pos >= 0)
613 {
614
615 /* vv Update of the statistic on the number of dominions vvvvvvvvvvvvvvvv */
616 doms++;
617 /* ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ */
618
619 /* vv Setting of the initial priority and parity vvvvvvvvvvvvvvvvvvvvvvvv */
620 p = maxprio;
621 alpha = p & 1;
622 /* ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ */
623
624 /* vv Call to the search routine and update of the zero winning region vv */
625 search();
626 outgame |= R;
627 if (alpha == 0)
628 {
629 winzero |= R;
630 }
631 /* ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ */
632
633 /* vv Search for the new pos and maxprio vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv */
634 for (pos = inverse[maxprio]; pos >= 0 && outgame[pos]; --pos)
635 {
636 }
637 if (pos >= 0) maxprio = priority(pos);
638 /* ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ */
639
640 /* vv Stack and current region cleaning vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv */
641 Top = Pivot = 0;
642 Phase[0] = true;
643 Heads[0]->clear();
644 Exits[0]->reset();
645 Entries[0]->clear();
646 Entries[0]->push_front(std::move(uideque()));
647 R.reset();
648 // /* ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ */
649
650 }
651 /* ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ */
652
653 /* vv Setting of the final solution vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv */
654 for (pos = 0; pos < nodecount(); ++pos)
655 {
656 if (disabled[pos]) continue;
657 oink->solve(pos, !winzero[pos], strategy[pos]);
658 }
659 /* ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ */
660
661 /* vv Printing of statistics vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv */
662 logger << "solved with " << totqueries << " total queries and " << totpromos << " total promotions;" << std::endl;
663 logger << " " << maxqueries << " max queries and " << maxpromos << " max promotions;" << std::endl;
664 logger << " " << doms << " dominions." << std::endl;
665 /* ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ */
666 }
667
668 }
669