mcts_game_play

create_ucb_node(LogNi,Node,ucb(UCB,Node)) :- ucb(Node,LogNi,UCB).

eval_animation_expression(NodeID,STR,Val) :-
    eval_animation_expression(NodeID,STR,Val,mandatory).

eval_animation_expression(NodeID,STR,Val,_) :-
    b_get_machine_animation_expression(STR,TExpr),!,
    visited_expression(NodeID,State),
    state_corresponds_to_fully_setup_b_machine(State,BState),
    b_interpreter:b_compute_expression_nowf(TExpr,[],BState,Val,'MCTS',0).

eval_animation_expression(NodeID,STR,Val,Mandatory) :- xtl_mode,!,
    visited_expression(NodeID,State),
    (xtl_game_info(STR,State,Res) -> Val=Res
    ; Mandatory=mandatory,
    add_warning(mcts_game_play,'Add definition for prob_game_info(Key,State,Val) with Key = ',STR),fail).

eval_animation_expression(_,STR,_,_) :-
    b_get_definition(STR,DefType,_Args,_Body,_Deps),!,
    (DefType = expression
    -> add_warning(mcts_game_play,'Please rewrite DEFINITION to use no arguments: ',STR)
    ; add_warning(mcts_game_play,'Please rewrite DEFINITION to return an expression and use no arguments: ',STR)
    ),
    fail.

eval_animation_expression(_,STR,_,mandatory) :-
    add_warning(mcts_game_play,'Please add DEFINITION for: ',STR),fail.

game_move(FromID,Action,TransID,DestID) :-
    compute_all_transitions_if_necessary(FromID,true),
    transition(FromID,Action,TransID,DestID).

gen_dot(Tree,MaxDepth) :-
    %trace,
    gen_dot_graph('mcts_tree.dot',mcts_node(Tree,MaxDepth),mcts_trans(Tree,MaxDepth)).

get_animation_expression_nr(State,DEFNAME,Default,Res) :-
    (eval_animation_expression(State,DEFNAME,R,not_mandatory)
    -> (get_number(R,Res), Res >= 0 -> true
    ; add_warning(mcts_game_play,'GAME_MCTS_RUNS/GAME_MCTS_TIMEOUT should return positive integer: ',R),
    Res=Default
    )
    ; Res = Default).

get_best_mcts_move(node(_,_,_,Children),MaxV,Target) :-
    maplist(get_visits,Children,Visits),
    max_member(MaxV,Visits),
    member(N,Children),
    get_visits(N,MaxV),
    get_node(N,Target).

get_child(node(_,_,_,C),Child) :- nonvar(C),member(Child,C).

get_max_ucb([],_,_,Child,Rest,Child,Rest).

get_max_ucb([Node|T],LogNi,CurMax,BestChildSoFar,RestSoFar,BestChild,Rest) :-
    ucb(Node,LogNi,UCB),
    UCB>CurMax, % we have a new best node
    !,
    get_max_ucb(T,LogNi,UCB,Node,[BestChildSoFar|RestSoFar],BestChild,Rest).

get_max_ucb([Node|T],LogNi,CurMax,BestChildSoFar,RestSoFar,BestChild,Rest) :-
    get_max_ucb(T,LogNi,CurMax,BestChildSoFar,[Node|RestSoFar],BestChild,Rest).

get_mcts_child_for_state(node(State,V,W,Children),State,Res) :- !, % the node itself; we apply MCTS directly for other player
    Res=node(State,V,W,Children).

get_mcts_child_for_state(node(_,_,_,Children),State,Child) :-
    member(Child,Children),
    get_node(Child,State),!.

get_mcts_child_for_state(Tree,State,Child) :-
    print(cannot_get_child_for_state(State,Tree)),nl,
    Child=leaf(State). % create a new root

get_node(node(N,_,_,_),N).

get_node(leaf(N),N).

get_number(int(S),S).

get_number(term(floating(R)),R).

get_number(S,S) :- number(S).

get_visits(node(_,_,V,_),V).

get_visits(leaf(_),0).

get_wins(node(_,W,_,_),W).

get_wins(leaf(_),0).

indent(0).

indent(s(X)) :- print(' + '), indent(X).

invert_win(0,R) :- !, R=1.

invert_win(1,R) :- !, R=0.

invert_win(0.5,R) :- !, R=0.5.

invert_win(R,R1) :- trace, R1 is 1-R.

is_max_player(string(MAX)) :- MAX=max ; MAX='MAX' ; MAX = 'Max'.

is_max_player(max). % XTL

is_true(pred_true).

is_true(true). % XTL

is_true('TRUE').

mcts(node(State,Wins,Visits,Childs),OuterWin,node(State,Wins1,V1,Childs1)) :-
    V1 is Visits+1,
    (Childs=[]
    -> % the node has no children; simulate it, i.e., compute the utility value
    Childs1=[],
    simulate_for_parent(State,_,OuterWin,terminal)
    ; LogNi is log(V1),
    (select_best_ucb_child(Childs,State,LogNi,Child,Childs1,Child1) -> true
    ; print(selection_failed),nl,trace),
    mcts(Child,ChildWin,Child1),
    invert_win(ChildWin,OuterWin)
    ),
    % backpropagate:
    Wins1 is Wins+OuterWin.

mcts(leaf(State),Wins,node(State,Wins,1,Childs)) :-
    simulate_for_parent(State,_Val,Wins,Kind),
    (Kind=terminal
    -> Childs=[] % do not add any children; game is over already
    ; findall(leaf(C),game_move(State,_,_,C),Childs)).

mcts_auto_play(State,Action,TransID,State2) :-
    get_animation_expression_nr(State,'GAME_MCTS_RUNS',1000,SimRuns),
    get_animation_expression_nr(State,'GAME_MCTS_TIMEOUT',5000,Timeout),
    (eval_animation_expression(State,'GAME_MCTS_CACHE_LAST_TREE',Res,not_mandatory), is_true(Res)
    -> Cache=cache ; Cache=no_cache),
    mcts_auto_play(State,Cache,Timeout,SimRuns,Action,TransID,State2).

mcts_auto_play(State,Cache,Timeout,SimRuns,Action,TransID,State2) :-
    (retract(saved_mcts_tree(OldTree)),
    Cache=cache,
    get_mcts_child_for_state(OldTree,State,InitialTree)
    -> true %,print_tree(InitialTree,0,2)
    ; InitialTree = leaf(State)),
    mcts_incr_auto_play(State,Timeout,SimRuns,Action,TransID,State2,InitialTree,FinalTree),
    save_last_mcts_tree(Cache,State2,FinalTree).

mcts_auto_play_available :-
    (b_get_machine_animation_expression('GAME_PLAYER',_) -> true
    ; b_get_machine_animation_expression('GAME_MCTS_RUNS',_) -> true
    ; xtl_mode -> xtl_game_info('GAME_MCTS_RUNS',_,_) -> true).

mcts_incr_auto_play(State,Timeout,SimRuns,Action,TransID,State2,Tree,FinalTree) :-
    statistics(walltime, [Start|_]),
    (mcts_run(Timeout,SimRuns,Tree,FinalTree,Visits,State2)
    -> statistics(walltime, [End|_]),
    Delta is End - Start,
    game_move(State,Action,TransID,State2),
    format('Move found by MCTS in ~w ms (~w runs, ~w visits): ~w (~w --(~w)--> ~w)~n',[Delta,SimRuns,Visits,Action,State,TransID,State2])
).

mcts_loop(EndTime,Nr,Tree,FinalTree) :- Nr>1,!,
    mcts(Tree,_,NewTree),
    N1 is Nr-1,
    (mcts_time_out(EndTime,N1) -> FinalTree=NewTree
    ; mcts_loop(EndTime,N1,NewTree,FinalTree)).

mcts_loop(_,_,Tree,Tree). %format('Final MCTS Tree : ~w~n',[Tree]),

mcts_node(Tree,_,NodeID,none,NodeDesc,Shape,Style,Color) :-
    get_node(Tree,NodeID), %print(gen(NodeID)),nl,
    get_wins(Tree,W), get_visits(Tree,N),
    (visited_expression(NodeID,State),translate_bstate_limited(State,140,TS) -> true ; TS='??'),
    (utility(NodeID,UVal) -> true ; UVal='?'),
    (terminal(NodeID) -> TT='terminal' ; TT=''),
    ajoin(['id:',NodeID,',w=',W,',n=',N,'\\n','utility=',UVal,' ',TT,'\\n',TS],NodeDesc),
    Shape=rectangle, Style=none, Color=black.

mcts_node(Tree,MaxDepth,NodeID,none,NodeDesc,Shape,Style,Color) :-
    MaxDepth>=1, MD is MaxDepth-1,
    get_child(Tree,Child),
    mcts_node(Child,MD,NodeID,none,NodeDesc,Shape,Style,Color).

mcts_run(Target) :-
    start(Init),
    mcts_run(5000,10000,leaf(Init),_,_,Target).

mcts_run(Timeout,Nr,Tree,FinalTree,Visits,Target) :-
    statistics(walltime, [Cur|_]), EndTime is Cur+Timeout,
    %set_prolog_flag(profiling,on),
    mcts_loop(EndTime,Nr,Tree,FinalTree), %set_prolog_flag(profiling,off), print_profile,
    get_best_mcts_move(FinalTree,Visits,Target),
    get_node(FinalTree,From),
    debug_format(19,'Best move from ~w is to ~w (~w visits)~n',[From,Target,Visits]),
    (debug_mode(on) -> print_tree(FinalTree,0,3) ; true).

mcts_time_out(EndTime,Nr) :- 0 is Nr mod 10,
    statistics(walltime, [Cur|_]),
    Cur>EndTime,!,
    format('MCTS TIME-OUT with ~w runs remaining.~n',[Nr]).

mcts_trans(Tree,_,NodeID,Label,SuccID,Color,Style) :- Style=solid, Color=lightgray,
    Label = 'move',
    get_node(Tree,NodeID),
    get_child(Tree,Child),
    get_node(Child,SuccID).

mcts_trans(Tree,MaxDepth,NodeID,Label,SuccID,Color,Style) :-
    MaxDepth>1, MD is MaxDepth-1,
    get_child(Tree,Child),
    mcts_trans(Child,MD,NodeID,Label,SuccID,Color,Style).

my_random_game_move(X,move,Z) :-
    findall(Y,game_move(X,_,_,Y),List),
    random_select(Z,List,_).

other_player(min,max).

other_player(max,min).

player(NodeID,R) :-
    eval_animation_expression(NodeID,'GAME_PLAYER',Res),
    is_max_player(Res),
    !, R=max.

player(_,min).

pretty_print_node(StateID) :- format('State: ~w',[StateID]).

print_tree(leaf(Node),Indent,_) :- indent(Indent), pretty_print_node(Node),nl.

print_tree(node(Node,Wins,Visits,Children),Indent,Max) :- Max>0, M1 is Max-1,
    indent(Indent), pretty_print_node(Node),nl,
    length(Children,Childs),
    indent(Indent), format(' w=~w, n=~w, childs=~w~n',[Wins,Visits,Childs]),
    (member(C,Children), print_tree(C,s(Indent),M1), fail
    ; true).

project(ucb(_,Node),Node).

save_last_mcts_tree(cache,State2,FinalTree) :- !,
    retractall(saved_mcts_tree(_)),
    get_mcts_child_for_state(FinalTree,State2,NewTree), % we assume we will make this move
    %terms:term_size(NewTree,Sz), write(sz(Sz)),nl,
    assert(saved_mcts_tree(NewTree)).

save_last_mcts_tree(_,_,_).

select_best_ucb_child([C],_,_,C,[C1],C1) :- !. % no need to compute when there is a single child

select_best_ucb_child([Child1|Children],_Parent,LogNi,Child,NewChildren,NewChild) :- !,
    ucb(Child1,LogNi,UCB1),
    get_max_ucb(Children,LogNi,UCB1,Child1,[],Child,Rest),
    NewChildren = [NewChild|Rest].

simulate_for_parent(X,Val,Res,NodeKind) :- simulate_random(X,Val,NodeKind),
    (player(X,max), Val<0 -> Res = 1
    ; \+ player(X,max), Val>0 -> Res = 1
    ; Val=0 -> Res = 0.5 % draw
    ; Res = 0). % loss

simulate_random(X,Res,terminal) :-
    terminal(X),
    (utility(X,R) -> true
    ; add_warning(mcts_game_play,'Could not compute utility for terminal node: ',X), trace, utility(X,R),
    R=0),
    !,Res=R.

simulate_random(X,Res,non_terminal) :-
    my_random_game_move(X,_,Z),!, % use random_game_move if not provided by game
    simulate_random(Z,Res,_).

simulate_random(_,Res,terminal) :- Res = 0. % no moves possible, we assume a draw

terminal(NodeID) :-
    eval_animation_expression(NodeID,'GAME_OVER',Res), is_true(Res).

ucb(leaf(_),_,Res) :- Res = 1000000.

ucb(node(_ID,Wins,Visits,C),LogNi,Res) :-
    (Visits=0 -> Res = 10000
    ; C=[], % terminal node
    Wins=Visits % winning node for opponent:
    % we assume player will always detect the winning move (limited mini-max improvement)
    % will make a difference for tic-tac-toe, 40 SimRuns, [- - -, 0 x -, x - -] : with detection x blocked
    -> Res = 10001 %,print(minimax_detection(_ID,Wins,Visits)),nl
    ; Res is (Wins/Visits) + sqrt(2.0 * LogNi / Visits)
).

utility(NodeID,Value) :-
    eval_animation_expression(NodeID,'GAME_VALUE',Res),
    get_number(Res,Value).