<div class="notebook"> <div class="nb-cell html"> <h2> Truel, or duel among three opponents. </h2> <p>There are three truelists, <code>a</code>, <code>b</code> and <code>c</code>, that take turns in shooting with a gun. The firing order is <code>a</code>, <code>b</code> and <code>c</code>. Each truelist can shoot at another truelist or at the sky (deliberate miss). The truelist have these probabilities of hitting the target (if they are not aiming at the sky): <code>a</code> 1/3, <code>b</code> 2/3 and <code>c</code> 1. The aim for each truelist is kill all the other truelists. </p> <p> The question is: what should <code>a</code> do to maximize his probability of living? Aim at <code>b</code>, <code>c</code> or the sky? </p> Note that the best strategy for the other truelists and situations is easy to find intuitively and corresponds to aim at the best shooter. <p></p> <p>See </p><ul> <li> <a href="https://en.wikipedia.org/wiki/Truel">https://en.wikipedia.org/wiki/Truel</a> </li> <li> Martin Shubik, Game Theory and Related Approaches to Social Behavior, 1964, page 43 </li> </ul> <p></p> <div><iframe src="https://www.youtube.com/embed/VQT29lq3UGQ?ecver=2" width="640" height="360" frameborder="0" allowfullscreen=""></iframe> </div> </div> <div class="nb-cell html"> <p>What is the best action for <code>a</code>?</p> </div> <div class="nb-cell query"> best_strategy(a,[a,b,c],S). </div> <div class="nb-cell html"> <p>What is the probability that <code>a</code> survives if it aims at <code>b</code>?</p> </div> <div class="nb-cell query"> mc_sample(survives_action(a,[a,b,c],0,b),100,P). </div> <div class="nb-cell html"> <p>What is the probability that <code>a</code> survives if it aims at <code>c</code>?</p> </div> <div class="nb-cell query"> mc_sample(survives_action(a,[a,b,c],0,c),100,P). </div> <div class="nb-cell html"> <p>What is the probability that <code>a</code> survives if it aims at the sky?</p> </div> <div class="nb-cell query"> mc_sample(survives_action(a,[a,b,c],0,sky),100,P). </div> <div class="nb-cell html"> <p>What is the probability that <code>a</code> survives against <code>c</code>?</p> </div> <div class="nb-cell query"> mc_sample(survives([a,c],a,0),100,P). </div> <div class="nb-cell html"> <p>What is the probability that <code>a</code> survives against <code>b</code>?</p> </div> <div class="nb-cell query"> mc_sample(survives([a,b],a,0),100,P). </div> <div class="nb-cell html"> <p>What is the probability that <code>a</code> survives against <code>b</code> when it's <code>b</code>'s turn?</p> </div> <div class="nb-cell query"> mc_sample(survives_round([b],[a,b],a,0),100,P). </div> <div class="nb-cell html"> <h3>Code</h3> </div> <div class="nb-cell program" data-background="true"> :- use_module(library(mcintyre)). :- if(current_predicate(use_rendering/1)). :- use_rendering(c3). :- use_rendering(graphviz). :- endif. :- dynamic kr/1,num/1. :- mc. :- begin_lpad. /** * best_strategy(+A:atom,+L:list,-S:atom). * * The best strategy for truelist A with * L still alive is to aim at S (with sky for the sky). * */ best_strategy(A,L,S):- delete(L,A,L1), append(L1,[sky],L2), maplist(ev_action(A,L,0),L2,LP), sort(LP,LP1), reverse(LP1,[_P-S|_]). /** * ev_action(+A:atom,+L:list,+T:term,+S:atom,-C:couple). * * Tuelist A with L still alive performing action S in turn T survives * with probability P in C=P-S. * */ ev_action(A,L,T,S,P-S):- mc_sample(survives_action(A,L,T,S),100,P). /** * survives_action(+A:atom,+L0:list,+T:term,+S:atom) * * A survives truel performing action S with L0 still alive in turn T * */ survives_action(A,L0,T,S):- shoot(A,S,L0,T,L1), remaining(L1,A,Rest), survives_round(Rest,L1,A,T). /** * shoot(+H:atom,+S:atom,+L0:list,+T:term,-L:list). * * When H shoots at S in round T and L0 still alive, * the truelist still alive become L */ shoot(H,S,L0,T,L):- (S=sky -> L=L0 ; (hit(T,H) -> delete(L0,S,L) ; L=L0 ) ). hit(_,a):1/3. hit(_,b):2/3. hit(_,c):1. /** * survives(+List:list,+Individual:atom,Round:term). * * Individual survives the truel with List at Round * */ survives([A],A,_):-!. survives(L,A,T):- survives_round(L,L,A,T). /** * survives_round(+Rest:list,+List:list,+Individual:atom,+Round:term) * * Individual survives the truel at Round with Rest still to shoot and * List truelist still alive */ survives_round([],L,A,T):- survives(L,A,s(T)). survives_round([H|_Rest],L0,A,T):- base_best_strategy(H,L0,S), shoot(H,S,L0,T,L1), remaining(L1,H,Rest1), member(A,L1), survives_round(Rest1,L1,A,T). /** * base_best_strategy(+A:atom,+T:list,-S:atom). * * the best action for A when * T is the list of surviving truelist, is S * * These are the strategies that are easy to find (most intuitive) * */ base_best_strategy(b,[b,c],c). base_best_strategy(c,[b,c],b). base_best_strategy(a,[a,c],c). base_best_strategy(c,[a,c],a). base_best_strategy(a,[a,b],b). base_best_strategy(b,[a,b],a). base_best_strategy(b,[a,b,c],c). base_best_strategy(c,[a,b,c],b). remaining([A|Rest],A,Rest):-!. remaining([_|Rest0],A,Rest):- remaining(Rest0,A,Rest). :- end_lpad. </div> </div>