With the recent release of AlphaBetaSearch it’s now much easier to compute relatively small proofs for determining the outcome of a combinatorial game assuming perfect play. Using a minimum branching heuristic (MBH), we now have an almost-one-liner to obtain a comparatively small proof for 4x4 Reversi:
In[]:=
With[{sg=ResourceFunction["AlphaBetaSearch"][iterateReversiUnique,initializeReversi[4],reversiPlayer,reversiResult,reversiMBH,Method->"Recursive",PerformanceGoal->"Quality"]},proof=Graph[sg,EdgeStyle->Gray,GraphLayout->"LayeredDigraphEmbedding",VertexSize->1,PerformanceGoal->"Quality",VertexShapeFunction->Function[{off,val,scale},Inset[displayBoard[val],off,Automatic,First[scale]]]]]
Out[]=
Since we haven’t used the extra-effort iterator, the canonical states aren’t as well aligned graphically as they could be. This does not affect the result that the winner is β., the second player to move:
In[]:=
AnnotationValue[{proof,initializeReversi[4]},VertexWeight]
Out[]=
β.
Comparing with our earlier result, we find that this proof is not strictly minimal:
In[]:=
VertexCount@proof
Out[]=
42
The advantage is that, without needing to compute the entire game graph, it takes less than a half-second to compute the solution:
In[]:=
RepeatedTiming[ResourceFunction["AlphaBetaSearch"][iterateReversiUnique,initializeReversi[4],reversiPlayer,reversiResult,reversiMBH]][[1]]
Out[]=
0.385106
The pruning method, which improves the result by only about 5%, first requires generating the entire graph. Now using FixedPointGraph from WFR, it takes about 15 seconds to run said computation:
In[]:=
AbsoluteTiming[gall=ResourceFunction["FixedPointGraph"][iterateReversiUnique,{initializeReversi[4]}];VertexCount[gall]]
Out[]=
{13.6059,9617}
By accepting a small loss in quality, we have improved our time by a large factor, over 30x. In the future (perhaps at summer school or summer camp) it will be fun to play with this new tool, and see how it reduces the complexity of difficult calculations.
game code
game code