/* 

  Chess tournament in Picat.

  https://brainstellar.com/puzzles/probability/117
  """
  A chess tournament has  K levels and N=2^K players with skills 
  P1 > P2 > ... > Pn. At each level, random pairs are formed and one person 
  from each pair proceeds to the next level. When two opponents play, the 
  one with the better skills always wins. What is the probability that players 
  P1 and P2 will meet in the final level?

  Answer:  n / (2* (n-1))
  """

  Cf my Gamble model gamble_chess_tournament.rkt

  This program was created by Hakan Kjellerstrand, hakank@gmail.com
  See also my Picat page: http://www.hakank.org/picat/

*/

import ppl_distributions, ppl_utils.
import util.

main => go.

/*
  For K = 2..7  (probability that 1 and 2 is meeting in the final)

  [k = 2,n = 4,theoretical = 0.666667]
  var : final pair
  Probabilities:
  [1,2]: 0.6645000000000000
  [1,3]: 0.3355000000000000
  mean = [[1,2] = 0.6645,[1,3] = 0.3355]

  var : p
  Probabilities:
  true: 0.6645000000000000
  false: 0.3355000000000000
  mean = [true = 0.6645,false = 0.3355]


  [k = 3,n = 8,theoretical = 0.571429]
  var : final pair
  Probabilities:
  [1,2]: 0.5748000000000000
  [1,3]: 0.2810000000000000
  [1,4]: 0.1139000000000000
  [1,5]: 0.0303000000000000
  mean = [[1,2] = 0.5748,[1,3] = 0.281,[1,4] = 0.1139,[1,5] = 0.0303]

  var : p
  Probabilities:
  true: 0.5748000000000000
  false: 0.4252000000000000
  mean = [true = 0.5748,false = 0.4252]


  [k = 4,n = 16,theoretical = 0.533333]
  var : final pair
  Probabilities:
  [1,2]: 0.5343000000000000
  [1,3]: 0.2652000000000000
  [1,4]: 0.1201000000000000
  [1,5]: 0.0536000000000000
  [1,6]: 0.0199000000000000
  [1,7]: 0.0053000000000000
  [1,8]: 0.0015000000000000
  [1,9]: 0.0001000000000000
  mean = [[1,2] = 0.5343,[1,3] = 0.2652,[1,4] = 0.1201,[1,5] = 0.0536,[1,6] = 0.0199,[1,7] = 0.0053,[1,8] = 0.0015,[1,9] = 0.0001]

  var : p
  Probabilities:
  true: 0.5343000000000000
  false: 0.4657000000000000
  mean = [true = 0.5343,false = 0.4657]


  [k = 5,n = 32,theoretical = 0.516129]
  var : final pair
  Probabilities:
  [1,2]: 0.5189000000000000
  [1,3]: 0.2557000000000000
  [1,4]: 0.1234000000000000
  [1,5]: 0.0581000000000000
  [1,6]: 0.0263000000000000
  [1,7]: 0.0099000000000000
  [1,8]: 0.0047000000000000
  [1,9]: 0.0017000000000000
  [1,10]: 0.0010000000000000
  [1,11]: 0.0003000000000000
  mean = [[1,2] = 0.5189,[1,3] = 0.2557,[1,4] = 0.1234,[1,5] = 0.0581,[1,6] = 0.0263,[1,7] = 0.0099,[1,8] = 0.0047,[1,9] = 0.0017,[1,10] = 0.001,[1,11] = 0.0003]

  var : p
  Probabilities:
  true: 0.5189000000000000
  false: 0.4811000000000000
  mean = [true = 0.5189,false = 0.4811]


  [k = 6,n = 64,theoretical = 0.507937]
  var : final pair
  Probabilities (truncated):
  [1,2]: 0.5099000000000000
  [1,3]: 0.2528000000000000
  [1,4]: 0.1244000000000000
  [1,5]: 0.0596000000000000
  .........
  [1,11]: 0.0005000000000000
  [1,12]: 0.0003000000000000
  [1,14]: 0.0001000000000000
  [1,13]: 0.0001000000000000
  mean = [[1,2] = 0.5099,[1,3] = 0.2528,[1,4] = 0.1244,[1,5] = 0.0596,[1,6] = 0.0277,[1,7] = 0.0147,[1,8] = 0.006,[1,9] = 0.0024,[1,10] = 0.0015,[1,11] = 0.0005,[1,12] = 0.0003,[1,14] = 0.0001,[1,13] = 0.0001]

  var : p
  Probabilities:
  true: 0.5099000000000000
  false: 0.4901000000000000
  mean = [true = 0.5099,false = 0.4901]


  [k = 7,n = 128,theoretical = 0.503937]
  var : final pair
  Probabilities (truncated):
  [1,2]: 0.5050000000000000
  [1,3]: 0.2530000000000000
  [1,4]: 0.1258000000000000
  [1,5]: 0.0627000000000000
  .........
  [1,10]: 0.0016000000000000
  [1,11]: 0.0006000000000000
  [1,13]: 0.0005000000000000
  [1,12]: 0.0004000000000000
  mean = [[1,2] = 0.505,[1,3] = 0.253,[1,4] = 0.1258,[1,5] = 0.0627,[1,6] = 0.0279,[1,7] = 0.0134,[1,8] = 0.0061,[1,9] = 0.003,[1,10] = 0.0016,[1,11] = 0.0006,[1,13] = 0.0005,[1,12] = 0.0004]

  var : p
  Probabilities:
  true: 0.5050000000000000
  false: 0.4950000000000000
  mean = [true = 0.505,false = 0.495]


*/
go ?=>
  member(K,2..7),
  N = 2**K,
  println([k=K,n=N,theoretical=((N / (2 * (N-1))))]),
  reset_store,
  run_model(10_000,$model(K),[show_probs_trunc,mean]),
  nl,
  % show_store_lengths,nl,
  fail,
  nl.
go => true.
  
% (a b c d e f) -> (a b) (c d) (e f)
make_random_pairs(People) = draw_without_replacement(People.len,People).chunks_of(2).

fight(A,B,Skills) = cond(Skills[A] > Skills[B], A, B).

tournament(Left,Skills) = Res =>
  if Left.len == 2 then
    Res = Left
  else
    Pairs = make_random_pairs(Left),
    Winners = [ fight(Pair[1],Pair[2],Skills)   : Pair in Pairs],
    Res = tournament(Winners,Skills)
  end.


model(K) =>
  N = 2**K,  % K levels

  Skills = draw_without_replacement(N, 1..2*N).sort_down,
  % println(skills=Skills),

  FinalPair = tournament(1..N,Skills).sort,
  % println(finalPair=FinalPair),

  P = check(FinalPair == [1,2]),
  
  add("final pair",FinalPair),
  add("p",P).