package ĠRe ver si Ċ Ċ import Ġca . aq tech . m ctree search 4 j . State Node Ċ import Ġjava . awt . Point Ċ Ċ class ĠRe ver si Solver He uristic Sim ( initialState : ĠRe ver si State ) ĊĠĠĠ Ġ: ĠRe ver si Solver ( initialState ) Ġ{ ĊĊĠĠĠ Ġoverride Ġfun Ġrun Tree Search Iteration () Ġ{ Ċ // ĠĠĠĠĠĠĠ Ġdisplay Tree ( 4 ) ĊĠĠĠĠĠĠĠ Ġsuper . run Tree Search Iteration () ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġprivate Ġval Ġhe uristic Weight Ġ= ĠarrayOf ( ĊĠĠĠĠĠĠĠ ĠarrayOf ( 1 0 0 , Ġ- 1 0 , Ġ 1 1 , Ġ 6 , Ġ 6 , Ġ 1 1 , Ġ- 1 0 , Ġ 1 0 0 ), ĊĠĠĠĠĠĠĠ ĠarrayOf (- 1 0 , Ġ- 2 0 , Ġ 1 , Ġ 2 , Ġ 2 , Ġ 1 , Ġ- 2 0 , Ġ- 1 0 ), ĊĠĠĠĠĠĠĠ ĠarrayOf ( 1 0 , Ġ 1 , Ġ 5 , Ġ 4 , Ġ 4 , Ġ 5 , Ġ 1 , Ġ 1 0 ), ĊĠĠĠĠĠĠĠ ĠarrayOf ( 6 , Ġ 2 , Ġ 4 , Ġ 2 , Ġ 2 , Ġ 4 , Ġ 2 , Ġ 6 ), ĊĠĠĠĠĠĠĠ ĠarrayOf ( 6 , Ġ 2 , Ġ 4 , Ġ 2 , Ġ 2 , Ġ 4 , Ġ 2 , Ġ 6 ), ĊĠĠĠĠĠĠĠ ĠarrayOf ( 1 0 , Ġ 1 , Ġ 5 , Ġ 4 , Ġ 4 , Ġ 5 , Ġ 1 , Ġ 1 0 ), ĊĠĠĠĠĠĠĠ ĠarrayOf (- 1 0 , Ġ- 2 0 , Ġ 1 , Ġ 2 , Ġ 2 , Ġ 1 , Ġ- 2 0 , Ġ- 1 0 ), ĊĠĠĠĠĠĠĠ ĠarrayOf ( 1 0 0 , Ġ- 1 0 , Ġ 1 1 , Ġ 6 , Ġ 6 , Ġ 1 1 , Ġ- 1 0 , Ġ 1 0 0 ), ĊĠĠĠĠĠĠĠ Ġ) ĊĊĠĠĠ Ġoverride Ġfun Ġsimulate ( node : ĠState Node < Re ver si State , ĠPoint >): ĠDouble Ġ{ ĊĠĠĠĠĠĠĠ Ġtr ac eln (" Simulation :") ĊĊĠĠĠĠĠĠĠ Ġ// ĠIf Ġstate Ġis Ġterminal , Ġthe Ġreward Ġis Ġdefined Ġby ĠM DP ĊĠĠĠĠĠĠĠ Ġif Ġ( node . is Terminal ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġtr ac eln (" Terminal Ġstate Ġreached ") ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġm dp . reward ( node . parent ?. state , Ġnode . ind uc ing Action , Ġnode . state ) ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġvar Ġdepth Ġ= Ġ 0 ĊĠĠĠĠĠĠĠ Ġvar Ġcurrent State Ġ= Ġnode . state ĊĠĠĠĠĠĠĠ Ġvar Ġdiscount Ġ= Ġreward Discount Factor ĊĊĠĠĠĠĠĠĠ Ġwhile ( true ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġvalid Actions Ġ= Ġm dp . actions ( currentState ) ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġbest Action Score Ġ= ĠInt . MIN _ VALUE ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġbest Actions Ġ= Ġmutable ListOf < Point >() ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġfor Ġ( action Ġin Ġvalid Actions ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġscore Ġ= Ġhe uristic Weight [ action . x ][ action . y ] ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( score Ġ> Ġbest Action Score ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġbest Action Score Ġ= Ġscore ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġbest Actions Ġ= Ġmutable ListOf ( action ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( score Ġ== Ġbest Action Score ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġbest Actions . add ( action ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġrandom Action Ġ= Ġbest Actions . random () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval ĠnewState Ġ= Ġm dp . transition ( currentState , Ġrandom Action ) ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( verbose ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġtrace (" -> Ġ$ random Action Ġ") ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġtrace (" -> Ġ$ newState Ġ") ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( md p . is Terminal ( newState )) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġreward Ġ= Ġm dp . reward ( currentState , Ġrandom Action , ĠnewState ) Ġ* Ġdiscount ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( verbose ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġtr ac eln (" -> ĠTerminal Ġstate Ġreached Ġ: Ġ$ reward ") ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġreward ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġcurrent State Ġ= ĠnewState ĊĠĠĠĠĠĠĠĠĠĠĠ Ġdepth ++ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġdiscount Ġ*= Ġreward Discount Factor ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( depth Ġ> Ġsimulation Depth Limit ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġreward Ġ= Ġm dp . reward ( currentState , Ġrandom Action , ĠnewState ) Ġ* Ġdiscount ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( verbose ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġtr ac eln (" -> ĠDepth Ġlimit Ġreached : Ġ$ reward ") ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġreward ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġoverride Ġfun Ġformat Node ( node : ĠState Node < Re ver si State , ĠPoint >): ĠString Ġ{ ĊĠĠĠĠĠĠĠ Ġreturn Ġ" Depth : Ġ${ node . depth } ĠAction : Ġ${ node . ind uc ing Action }, ĠMax ĠRew ard : Ġ${ "% . 5 f ". format ( node . max Reward )}" ĊĠĠĠ Ġ} Ċ } Ċ