<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 -&gt;
      L=L0
    ;
      (hit(T,H) -&gt;
        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>