Abstract
Abstract
For any kind of rule based updating systems with bidirectional rules, we can view all states in the multiway system as equivalent. Such perspective is useful for theorem proving, etc. In particular, there is a strong interest in finding general strategies to apply rules to simplify complex states, where the complexity can be the number of nodes or edges in a hypergraph, the number of letters in a string substitution system or the number of spiders and edges in a ZX diagram. Many simplification procedures require temporary added complexity to rearrange the state to a more desirable form, where simplifying rules can apply, limiting the power of simply descending along some heuristic. With infinite computational power, a multiway graph can be constructed and brute-force the optimal solution, which is impractical due to the exponential or even factorial growth in complexity with system sizes or generations of evolution.
We present a Monte-Carlo tree search (MCTS) based approach to reduce the computational need. An Upper-Confidence Bounds Applied to Trees (UCT) algorithm is used to balance the ‘exploration’ of new states and ‘exploitation’ of known states with high values are balanced. This is achieved by evaluating a ‘heuristic’ value of each state which contains information about the state itself and the extent of exploration. The heuristic function itself can also be based on a neural network.
We present a Monte-Carlo tree search (MCTS) based approach to reduce the computational need. An Upper-Confidence Bounds Applied to Trees (UCT) algorithm is used to balance the ‘exploration’ of new states and ‘exploitation’ of known states with high values are balanced. This is achieved by evaluating a ‘heuristic’ value of each state which contains information about the state itself and the extent of exploration. The heuristic function itself can also be based on a neural network.
Introduction
Introduction
For simplicity of understanding and reducing the complexity of computation, we study string substitution systems as an example. The goal of the algorithm is to ‘simplify’ a randomly chosen string using the rules given in order to reach the shortest string possible. Since we are dealing with a problem of proving equivalence of different strings and finding the shortest form, the rules applied are bidirectional. Simplifying rules are the half of all the rules that lead to a reduction in the length of the string.
One approach is to do a comprehensive tree search by applying all applicable rules to different parts of the string and do the same for their children. The shortest child string would be the desired outcome. However, the computational complexity of such an approach is huge, as many substitutions increase the length of the strings and lead to even more children per iteration. A simple fix to this issue is to limit the choice of rules applied to simplifying rules, which shortens the strings and reduces the space of search. The complexity is dramatically reduced, but many simplifying states are now impossible to reach. It is imaginable that for certain simplification to take place, strings need to become longer and be arranged to a new form that allows further simplification. Limiting the rules to simplifying rules eliminates such simplification routes.
It is therefore obvious that some kind of tree search is necessary and intelligent search algorithms are needed to reduce the complexity. The crux of our algorithm is to explore only worth-while states and not others. Two criterion are used to determine which states are worth exploring: that the state is likely to lead to simplification and that it is under-explored. This is presented to the algorithm as a ‘heuristic’ score of a state, where one part characterizes the potential to simplification and another characterize the extent of exploration. This approach constitutes an Upper-Confidence Bounds Applied to Trees (UCT) algorithm for Monte-Carlo tree search (MCTS).
We compare the following approaches for string simplification: brute-force tree search, brute-force tree search limited to simplifying rules, choose the shortest string after each two layer tree and our MCTS algorithm. brute-force tree search is computational infeasible, and the other two does not lead to longer simplified results compared to our MCTS algorithm.
One approach is to do a comprehensive tree search by applying all applicable rules to different parts of the string and do the same for their children. The shortest child string would be the desired outcome. However, the computational complexity of such an approach is huge, as many substitutions increase the length of the strings and lead to even more children per iteration. A simple fix to this issue is to limit the choice of rules applied to simplifying rules, which shortens the strings and reduces the space of search. The complexity is dramatically reduced, but many simplifying states are now impossible to reach. It is imaginable that for certain simplification to take place, strings need to become longer and be arranged to a new form that allows further simplification. Limiting the rules to simplifying rules eliminates such simplification routes.
It is therefore obvious that some kind of tree search is necessary and intelligent search algorithms are needed to reduce the complexity. The crux of our algorithm is to explore only worth-while states and not others. Two criterion are used to determine which states are worth exploring: that the state is likely to lead to simplification and that it is under-explored. This is presented to the algorithm as a ‘heuristic’ score of a state, where one part characterizes the potential to simplification and another characterize the extent of exploration. This approach constitutes an Upper-Confidence Bounds Applied to Trees (UCT) algorithm for Monte-Carlo tree search (MCTS).
We compare the following approaches for string simplification: brute-force tree search, brute-force tree search limited to simplifying rules, choose the shortest string after each two layer tree and our MCTS algorithm. brute-force tree search is computational infeasible, and the other two does not lead to longer simplified results compared to our MCTS algorithm.
Definition of Rules
Definition of Rules
To demonstrate the algorithm, we need to choose a rule with sufficient complexity such that brute-force algorithm is infeasible.
Since we are dealing with a problem of proving equivalence of different strings and finding the shortest form, the rules applied are bidirectional.
Simplifyingrules are the half of all the rules that lead to a reduction in the length of the string.
The experience is that when rules 0, 1, and 2 are not symmetrized (they are not simple replacement of letters to each other, i.e. rules1 and rules0 are the same with “A” replaced with “C”, but rules2 is not of that nature), the rules lead to a need for non-trivial simplification procedures.
Since we are dealing with a problem of proving equivalence of different strings and finding the shortest form, the rules applied are bidirectional.
Simplifyingrules are the half of all the rules that lead to a reduction in the length of the string.
The experience is that when rules 0, 1, and 2 are not symmetrized (they are not simple replacement of letters to each other, i.e. rules1 and rules0 are the same with “A” replaced with “C”, but rules2 is not of that nature), the rules lead to a need for non-trivial simplification procedures.
In[]:=
rules0={"A""AB","ABBA""A","BAAB""BB","ABAB""BAA","AA""ABA","BA""BBBB","AB""A","A""ABBA","BB""BAAB","BAA""ABAB","ABA""AA","BBBB""BA"};rules1={"C""CB","CBBC""C","BCCB""BB","CBCB""BCC","CC""CBC","BC""BBBB","CB""C","C""CBBC","BB""BCCB","BCC""CBCB","CBC""CC","BBBB""BC"};rules2={"A""ACC","AAC""CACC","CCAA""AAAAC","ACC""A","CACC""AAC","AAAAC""CCAA"};rules3={"ABC""ACBB","BAAACC""AACCB","ABCCA""ACCBBAAC","ACBB"->"ABC","AACCB""BAAACC","ACCBBAAC""ABCCA"};rules=Join[rules0,rules1,rules2,rules3];simplifyingrules0={"ABBA""A","BAAB""BB","ABAB""BAA","AB""A","ABA""AA","BBBB""BA"};simplifyingrules1={"CBBC""C","BCCB""BB","CBCB""BCC","CB""C","CBC""CC","BBBB""BC"};simplifyingrules2={"ACC""A","CACC""AAC","AAAAC""CCAA"};simplifyingrules3={"BAAACC""AACCB","ACBB""ABC","ACCBBAAC""ABCCA"}simplifyingrules=Join[simplifyingrules0,simplifyingrules1,simplifyingrules3];
Out[]=
{BAAACCAACCB,ACBBABC,ACCBBAACABCCA}
In[]:=
ResourceFunction["MultiwaySystem"][rules,"AB",2,"StatesGraph"]
The Monte-Carlo Tree Search Algorithm with Upper-Confidence Bounds Applied to Trees
The Monte-Carlo Tree Search Algorithm with Upper-Confidence Bounds Applied to Trees
The visits association object records how many times a state has been explored. The score association object records the potential to simplification of a state.
HeuristicValue calculates the heuristic value of a state to decide whether or not it should be explored. The possible states next step with the highest heuristic value is explored.
Record updates the score associated with the state as well as the number of times visited.
PlayoutValue calculates the score of a state based on a heuristic informed tree search
MonteCarloValue carries out PlayoutValue multiple times for a state.
HeuristicValue calculates the heuristic value of a state to decide whether or not it should be explored. The possible states next step with the highest heuristic value is explored.
Record updates the score associated with the state as well as the number of times visited.
PlayoutValue calculates the score of a state based on a heuristic informed tree search
MonteCarloValue carries out PlayoutValue multiple times for a state.
In[]:=
visits=<|"total"1|>;score=<||>;HeuristicValue[state_,c_]:=Do[Nt=visits["total"];Ni=If[KeyExistsQ[visits,state],visits[state],1];V=If[KeyExistsQ[score,state],score[state],1/StringLength[state]];(*Vdescribesthepotentialofastatetoleadtosimplification.Ifthestatehasnotbeenassignedascorebefore,takeVtobetheinverseofthestringlength.*)Return[If[V<0.8,V+c*(Log[Nt]/Ni),0]],(*Log[Nt]/NiisusedsuchthatwhenNi(totalnumberthestatehasbeenexplored)issmallrelativetototalexplorationNt,theheuristicishightoencourageexploration.IfVisgreaterthan0.8,itisprobablyareallyshortstateorastatewithclearsimplificationroutes.Settheheuristicto0tosavevaluableresourcestoexploreotherstates.*)1]record[state_,value_]:=Do[visits["total"]+=1;visits[state]=If[KeyExistsQ[visits,state],visits[state]+1,1];score[state]=If[KeyExistsQ[score,state],Max[score[state],value],value],(*Alwayskeepthemaximumscoresincewecanalmostensurethealgorithmtofollowthebestpaththatgavethehighscore.InperfectinformationgamealgorithmssuchasAlphaZero,aprobabilisticapproach(takingaverageofscores)isusedinsteadsincetheadversary'smveintroducessomeuncertainty.Movesthatcanleadtogoodadversaryperformanceareexploredoftensincetheadversarywilllikechoosethemove,andthisreducesthescoreforthestate.*)1]PlayoutValue[state_,it_,totit_,λ_]:=If[it>totit,(*Sincestringmanipulationisinfinite,wechooseaterminatingconditiondescribedbyatotalrecursiondepthtotit.*)1/StringLength[state],(*Ifthestateisthedeepestrecursionallowed,simplyreturntheinverselengthofthestring.*)Module[{value},currentvalue=1/StringLength[state];(*Inverseofstringlengthistheminimumvalueofthestate.Ifsimplificationroutesexist,thevaluecanbeevenhigher*)nextstates=Last[ResourceFunction["MultiwaySystem"][rules,state,1]];length=Length[nextstates];heuristictable=Table[HeuristicValue[nextstates[[a]],0.05],{a,1,length,1}];positiontable=Position[heuristictable,Max[heuristictable]];bestposition=positiontable[[RandomInteger[{1,Length[positiontable]}]]];newstate=nextstates[[bestposition]][[1]];value=Max[currentvalue,λ*PlayoutValue[newstate,it+1,totit,λ]];(*Thevalueisseletedasthemaximumbetweenthevalueofduetothelengthofthestateitselfandthefoundpaththatmightleadtosimplification.*)record[state,value];value]]MonteCarloValue[state_,m_,n_]:=Max[Table[PlayoutValue[state,0,m,0.98],{i,0,n,1}]]
Training
Training
The training takes quite some time. If you want to run the notebook without the training, run the cells in subsection “Training Results” to initialize the variables containing the results. No need to expand the cells as they are very long. Collect scores by running PlayoutValue for randomized initial strings of various lengths. Short length initial states require less iterations to find full simplification and also has less possible outcomes to exhaust. The string length the procedure is working on is printed. We start from length 5 strings and move to length 20 strings eventually. The training might take a few minutes and takes longer as string lengths increase.
In[]:=
n=5;While[n<20,n+=1;Print[n];m=0;While[m<500;m+=1;MonteCarloValue[ResourceFunction["RandomString"][{"A","B","C"},n],8*n,8*n];];]
6
7
Out[]=
$Aborted
Save the status of training.
In[]:=
Save["visits.m",visits];Save["score.m",score];
In[]:=
visits=Import["visits.m"];score=Import["score.m"];
Simplification Algorithm
Simplification Algorithm
FindShortestString uses the training results and the scores of states to optimize finding simplification routes. If mode==”Optimized”, the scores for states trained with MCTS is used. Else, only string lengths are used to search the tree.
tableofusedrules=Table[0,{i,1,Length[rules],1}];(*Thistablecountshowmanytimesarulehasbeenusedduringsimplification.*)
In[]:=
StateToScore[state_]:=If[KeyExistsQ[score,state],score[state],1/StringLength[state]](*Functionthatcomputesthescoreofastatebasedonlengthorsimplicationpotential.*)StateToScoreUnoptimized[state_]:=If[KeyExistsQ[score,state],score[state],1/StringLength[state]](*Lengthbasedonlyscorecomputation.*)FindShortestString[string_,mode_]:=Module[{currentstring,newstate=string,nextscore=1/StringLength[string],currentscore=0},While[nextscore>currentscore,(*Theloopterminateswhenthescoreofthecurrentstringislargerthanallpossiblechildrenintwogenerations.*)Print[currentstring];currentscore=nextscore;currentstring=newstate;firstlayer=Table[Last[ResourceFunction["MultiwaySystem"][rules[[rule]],currentstring,1,"PredecessorRulesList"]],{rule,1,Length[rules],1}];(*Returnsalistofchildrenandtheirparents.Thetableisstructuredsuchthatchildrenbyapplicationofdifferentrulesareputindifferentelements.Suchastrucutreishelpfulwhenfiguringoutwhichrulesareusedforsimplification.*)firstlayerstates=Table[Table[firstlayer[[rule]][[state]][[1]],{state,1,Length[firstlayer[[rule]]],1}],{rule,1,Length[rules],1}];(*Removetheparents.*)firstlayerscores=If[mode=="Optimized",Map[StateToScore,firstlayerstates,{2}],StateToScoreUnoptimized/@firstlayerstates];(*Computethescoreofchildrenwithoutchangingthestructure.Scoresafterdifferentrulesareindifferentelements.*)firstlayermaxscore=Max[firstlayerscores];(*Maximumscoreofgenerationonechildren.*)secondlayer=Table[Table[Table[Last[ResourceFunction["MultiwaySystem"][rules[[secondrule]],firstlayer[[rule]][[state]][[1]],1,"PredecessorRulesList"]],{state,1,Length[firstlayer[[rule]]],1}],{rule,1,Length[rules],1}],{secondrule,1,Length[rules],1}];(*Returnschildrenofeachfirstgenerationchildren.Eachelementstillcorrespondtothefirstappliedrules,andthenextlevelisseparatedbysecondappliedrules.Suchastrucutreishelpfulwhenfiguringoutwhichrulesareusedforsimplification.*)secondlayerstates=Table[Table[Table[Table[secondlayer[[secondrule]][[rule]][[secondstate]][[state]][[1]],{state,1,Length[secondlayer[[secondrule]][[rule]][[secondstate]]],1}],{secondstate,1,Length[secondlayer[[secondrule]][[rule]]],1}],{rule,1,Length[rules],1}],{secondrule,1,Length[rules],1}];secondlayerscores=If[mode=="Optimized",Map[StateToScore,secondlayerstates,{4}],StateToScoreUnoptimized/@secondlayerstates];secondlayermaxscore=Max[secondlayerscores];(*Thehighestscoreamongallchildren*)If[firstlayermaxscore>secondlayermaxscore,(*Choosethebeststringfromfirstgenerationchildrenifthefirstlayerhasthebestscore*)Do[positiontable=Position[firstlayerscores,firstlayermaxscore];bestposition=positiontable[[RandomInteger[{1,Length[positiontable]}]]];rule=bestposition[[1]];If[mode"Optimized",Do[tableofusedrules[[rule]]+=1,1],Skip];stateposition=bestposition[[2]];newstate=firstlayerstates[[rule]][[stateposition]],1],(*Choosethebeststringfromsecondgenerationchildrenifthesecondlayerhasthebestscore*)Do[positiontable=Position[secondlayerscores,secondlayermaxscore];bestposition=positiontable[[RandomInteger[{1,Length[positiontable]}]]];secondrule=bestposition[[1]];rule=bestposition[[2]];(*OnlyupdatetableofrulesifusingMCTS*)If[mode"Optimized",Do[tableofusedrules[[secondrule]]+=1;tableofusedrules[[rule]]+=1,1],Skip];secondstateposition=bestposition[[3]];stateposition=bestposition[[4]];newstate=secondlayerstates[[secondrule]][[rule]][[secondstateposition]][[stateposition]];(*Childstringwiththebestscore*),1]];nextscore=Max[firstlayermaxscore,secondlayermaxscore];];Print[currentstring];(*Whenallchildrenhavelowerscoresthantheparent,printtheparentastheendresult.*)]
Testing all algorithms.
It is clear that The MCTS algorithm is superior in that it simplifies the string to the fullest extent. The string length only tree search algorithm came in second place, and the brute force solution with simplifying rules only is the worst. Full tree search without the complete set of rules is not even feasible to compute.
If we want to see what rules are implemented most frequently, we can run the MCTS algorithm multiple times and examine the table of the frequency of rule usage.
If we want to see what rules are implemented most frequently, we can run the MCTS algorithm multiple times and examine the table of the frequency of rule usage.
Some notable example rules are (AAB)65, (AACCACC)65, (CCB)58, (AAABA)22, (BABBBB)19, (AABBA)20, (BAAABAB)19, (CCBBC)22. These rules increases the complexity on the surface, but are called many times to lead to further simplification. In the future, with causal graphs, we can systematically examine the causal relationship between these rules and further simplification rules.