function [ s, turn_average ] = truel_simulation ( p, strategy, truel_num )

%*****************************************************************************80
%
%% truel_simulation() simulates a truel (a 3-way duel).
%
%  Discussion:
%
%    Three players fight a three-sided duel, or "truel".
%
%    Player 1 chooses a target (player 2, player 3, or nobody), and fires.
%    If aimed at a player, he hits with a probability of P(1).
%
%    Then it is Player 2's turn, and Player 3's turn.
%
%    Play continues to alternate until there is only one survivor.
%
%    Strategy 1:
%
%      Each player uses their turn to fire at the opponent with the
%      highest accuracy.
%
%    Strategy 2:
%      Each player fires at the "next" player.  1->2, 2->3, 3->1
%      until there are only two players.
%
%    Strategy 3:
%      Each player chooses their target at random.
%
%    Strategy 4:
%
%    * The player with the highest accuracy will always aim at the player
%      with the next highest accuracy.
%    * The player with the medium accuracy will always aim at the player
%      with the highest accuracy; if that player is dead, then the player
%      will aim at the player with lowest accuracy.
%    * The player with lowest accuracy will aim at NO ONE, as long as
%      the other two players are both alive.  Once there is only one
%      opponent, he will aim at that opponent.  
%
%    Although the program was written to simulate a 3-way duel, it can
%    handle duels with an arbitrary number of players.  It determines the number 
%    of players from the length of the P array.  Therefore, to play a duel with 
%    4 players, simply supply 4 numbers in P.
%
%  Licensing:
%
%    This code is distributed under the MIT license.
%
%  Modified:
%
%    14 November 2009
%
%  Author:
%
%    John Burkardt
%
%  Reference:
%
%    Martin Gardner,
%    "The Triangular Duel",
%    The Second Scientific American Book of Mathematical
%    Puzzles and Diversions,
%    Simon and Schuster, 1961.
%
%    Marc Kilgour, Steven Brams,
%    The Truel,
%    Mathematics Magazine,
%    Volume 70, Number 5, December 1997, pages 315-326.
%
%    Paul Nahin,
%    Duelling Idiots and Other Probability Puzzlers,
%    Princeton University Press, 2000,
%    ISBN13: 978-0691009797,
%    LC: QA273.N29.
%
%    Martin Shubik,
%    "Does the Fittest Necessarily Survive?",
%    in Readings in Game Theory and Political Behavior,
%    edited by Martin Shubik,
%    Doubleday, 1954,
%    LC: H61.S53.
%
%  Input:
%
%    real P(*), the probabilities that player I will hit an opponent
%    in a single shot.  Each P(I) should be between 0 and 1.
%
%    integer STRATEGY, the index of the strategy.
%    1: each player fires at best opponent.
%    4: player 1 at 2, player 2 at 1, player 3 withholds.
%
%    integer TRUEL_NUM, the number of truels to run.
%
%  Output:
%
%    real S(*), the estimated probablity that player I will survive.
%
%    real TURN_AVERAGE, the average number of turns required to
%    complete the truel.
%
  fprintf ( 1, '\n' );
  fprintf ( 1, 'truel_simulation():\n' );
  fprintf ( 1, '  MATLAB/Octave version %s\n', version ( ) );

  if ( nargin < 2 )
    truel_num = input ( 'Enter the number of truels to run: ' );
  end

  if ( nargin < 1 )
    p = input ( 'Enter player accuracies between 0 and 1, in a vector [*,*,*]: ' );
  end
 
  player_num = length ( p );

  s = zeros(player_num,1);
  turn_average = 0;

  for duel = 1 : truel_num

    if ( strategy == 1 )
      [ survivor, turn_num ] = truel_strategy1 ( p );
    elseif ( strategy == 2 )
      [ survivor, turn_num ] = truel_strategy2 ( p );
    elseif ( strategy == 3 )
      [ survivor, turn_num ] = truel_strategy3 ( p );
    elseif ( strategy == 4 )
      [ survivor, turn_num ] = truel_strategy4 ( p );
    end

    s(survivor) = s(survivor) + 1;
    turn_average = turn_average + turn_num;

  end

  s = s / truel_num;
  turn_average = turn_average / truel_num;

  return
end
function [ survivor, turn_num ] = truel_strategy1 ( p )

%*****************************************************************************80
%
%% truel_strategy1() returns the outcome of a truel with strategy 1.
%
%  Discussion;
%
%    Strategy 1:
%
%    * Each player chooses the opponent with highest accuracy as target.
%
%  Licensing:
%
%    This code is distributed under the MIT license.
%
%  Modified:
%
%    26 August 2017
%
%  Author:
%
%    John Burkardt
%
%  Reference:
%
%    Martin Shubik,
%    "Does the Fittest Necessarily Survive?",
%    in Readings in Game Theory and Political Behavior,
%    edited by Martin Shubik,
%    Doubleday, 1954,
%    LC: H61.S53.
%
%  Input:
%
%    real P(*), the probabilities that player I will hit an opponent
%    in a single shot.  Each P(I) should be between 0 and 1.
%
%  Output:
%
%    integer SURVIVOR, the survivor.
%
  player_num = length ( p );
  alive_num = player_num;
  q = p;

  turn_num = 0;
 
  while ( true )

    for i = 1 : player_num
%
%  Use the Q vector to keep track of who's alive, and who's worth
%  shooting at.  To avoid shooting yourself, temporarily zero your
%  own Q value.
%
      if ( 0.0 < q(i) )

        turn_num = turn_num + 1;

        q_save = q(i);
        q(i) = 0.0;

        [ q_max, target ] = max ( q );

        r = rand ( );
        if ( r <= q_save )
          q(target) = 0.0;
          alive_num = alive_num - 1;
          if ( alive_num == 1 )
            survivor = i;
            return
          end
        end

        q(i) = q_save;

      end

    end

  end

  return
end
function [ survivor, turn_num ] = truel_strategy2 ( p )

%*****************************************************************************80
%
%% truel_strategy2() returns the outcome of a truel with strategy 2.
%
%  Discussion;
%
%    Strategy 2:
%
%    * Each player chooses the opponent whose index is next.
%
%  Licensing:
%
%    This code is distributed under the MIT license.
%
%  Modified:
%
%    07 July 2022
%
%  Author:
%
%    John Burkardt
%
%  Reference:
%
%    Martin Shubik,
%    "Does the Fittest Necessarily Survive?",
%    in Readings in Game Theory and Political Behavior,
%    edited by Martin Shubik,
%    Doubleday, 1954,
%    LC: H61.S53.
%
%  Input:
%
%    real P(*), the probabilities that player I will hit an opponent
%    in a single shot.  Each P(I) should be between 0 and 1.
%
%  Output:
%
%    integer SURVIVOR, the survivor.
%
  player_num = length ( p );
  alive_num = player_num;
  q = p;

  turn_num = 0;
 
  while ( true )

    for i = 1 : player_num
%
%  Use the Q vector to keep track of who's alive.
%
      if ( 0.0 < q(i) )

        turn_num = turn_num + 1;
%
%  Choose target.
%
        ip1 = mod ( i, 3 ) + 1;
        ip2 = mod ( i + 1, 3 ) + 1;
        if ( 0 < q(ip1) )
          target = ip1;
        else
          target = ip2;
        end
%
%  Fire at target.
%
        r = rand ( );
        if ( r <= q(i) )
          q(target) = 0.0;
          alive_num = alive_num - 1;
          if ( alive_num == 1 )
            survivor = i;
            return
          end
        end

      end

    end

  end

  return
end
function [ survivor, turn_num ] = truel_strategy3 ( p )

%*****************************************************************************80
%
%% truel_strategy3() returns the outcome of a truel with strategy 3.
%
%  Discussion;
%
%    Strategy 3:
%
%    * Each player chooses an opponent randomly.
%
%  Licensing:
%
%    This code is distributed under the MIT license.
%
%  Modified:
%
%    07 July 2022
%
%  Author:
%
%    John Burkardt
%
%  Reference:
%
%    Martin Shubik,
%    "Does the Fittest Necessarily Survive?",
%    in Readings in Game Theory and Political Behavior,
%    edited by Martin Shubik,
%    Doubleday, 1954,
%    LC: H61.S53.
%
%  Input:
%
%    real P(*), the probabilities that player I will hit an opponent
%    in a single shot.  Each P(I) should be between 0 and 1.
%
%  Output:
%
%    integer SURVIVOR, the survivor.
%
  player_num = length ( p );
  alive_num = player_num;
  q = p;

  turn_num = 0;
 
  while ( true )

    for i = 1 : player_num
%
%  Use the Q vector to keep track of who's alive.
%
      if ( 0.0 < q(i) )

        turn_num = turn_num + 1;
%
%  Choose target.
%
        ip1 = mod ( i, 3 ) + 1;
        ip2 = mod ( i + 1, 3 ) + 1;
        if ( 0 == q(ip1) )
          target = ip2;
        elseif ( 0 == q(ip2) )
          target = ip1;
        else
          r = rand ( );
          if ( r <= 0.5 )
            target = ip1;
          else
            target = ip2;
          end
        end
%
%  Fire at target.
%
        r = rand ( );
        if ( r <= q(i) )
          q(target) = 0.0;
          alive_num = alive_num - 1;
          if ( alive_num == 1 )
            survivor = i;
            return
          end
        end

      end

    end

  end

  return
end
function [ survivor, turn_num ] = truel_strategy4 ( p )

%*****************************************************************************80
%
%% truel_strategy4() returns the outcome of a truel with strategy 4.
%
%  Discussion;
%
%    Strategy 4:
%
%    * The player with the highest accuracy will always aim at the player
%      with the next highest accuracy.
%    * The player with the medium accuracy will always aim at the player
%      with the highest accuracy; if that player is dead, then the player
%      will aim at the player with lowest accuracy.
%    * The player with lowest accuracy will aim at NO ONE, as long as
%      the other two players are both alive.  Once there is only one
%      opponent, he will aim at that opponent.  
%
%    With the probabilities ( 2/6, 4/6, 5/6), the weakest player has about 
%    a 70% chance of surviving, using this strategy.
%
%    With the probabilities ( 5/6, 4/6, 2/6), the weakest player has about
%    a 40% chance of surviving.
%
%  Licensing:
%
%    This code is distributed under the MIT license.
%
%  Modified:
%
%    14 November 2009
%
%  Author:
%
%    John Burkardt
%
%  Reference:
%
%    Martin Shubik,
%    "Does the Fittest Necessarily Survive?",
%    in Readings in Game Theory and Political Behavior,
%    edited by Martin Shubik,
%    Doubleday, 1954,
%    LC: H61.S53.
%
%  Input:
%
%    real P(*), the probabilities that player I will hit an opponent
%    in a single shot.  Each P(I) should be between 0 and 1.
%
%  Output:
%
%    integer SURVIVOR, the survivor.
%
  player_num = length ( p );
  alive_num = player_num;
  p_min = min ( p );
  p_max = max ( p );
%
%  Make a copy of P that we can manipulate.
%
  q = p;

  turn_num = 0;
 
  while ( true )

    for i = 1 : player_num
%
%  Use the Q vector to keep track of who's alive, and who's worth
%  shooting at.  To avoid shooting yourself, temporarily zero your
%  own P value.
%
      if ( 0.0 < q(i) )

        turn_num = turn_num + 1;
%
%  If there's more than one other player,
%  and you're the worst player,
%  and you're strictly a worst player,
%  then don't do anything.
%
        if ( 2 < alive_num & q(i) == p_min & p_min < p_max )
%
%  Otherwise, aim at the target (highest opponent) and
%  hit them with your accuracy.
%
        else
          q_save = q(i);
          q(i) = 0.0;
          [ q_target, target ] = max ( q );
          r = rand ( );

          if ( r <= q_save )
            q(target) = 0.0;
            alive_num = alive_num - 1;
            if ( alive_num == 1 )
              survivor = i;
              return
            end
          end

          q(i) = q_save;

        end

      end

    end

  end

  return
end
 
