// (C) Jörg Bewersdorff 07-2003

// ====== QuaakAnalyse =====================================================

// Eine Instanz des Objekts QuaakAnalyse managt die rekursive Minimax-
// Analyse aller Positionen des Zwei-Personen-Bluff-Spiels QUUAK! von
// Dirk Hanneforth

// Es werden zwei Varianten der Spielregel analysiert:
// 0: Man gewinnt nur dann, wenn man dreimal öfter eine Runde gewinnt
//    als der Gegner (es kommt daher zu häufigen Unentschieden)
// 1: Man gewinnt auch dann, wenn man nach dem Aufbrauchen aller Chips
//    mehr Runden gewonnen hat als der Gegner


// QA = new QuaakAnalyse(SpielregelVariante);
// QA.MinimaxAnalyse(ChipAnzMax);

// Output:
// QA.Minimax(ChipsL,ChipsR,Saldo)  Minimax-Wert zur
//                                  Position (ChipsL,ChipsR,Saldo)

// Der mathemtische Hintergrund wird u.a erläutert in
// Jörg Bewersdorff, "Glück, Logik und Bluff: Mathematik im Spiel -
// Methoden, Ergebnisse und Grenzen", Kapitel 3.12


function QuaakAnalyse(SpielregelVariante)
{
  // Eigenschaften:
  this.SpielregelVariante=SpielregelVariante; 
  this.MinimaxWerte=new Abbildung();            // Position -> Minimax-Wert

  // Methoden:
  this.MinimaxAnalyse=QuaakAnalyseMinimaxAnalyse;
  this.Minimax=QuaakAnalyseMinimax;
  this.StrategieMix=QuaakAnalyseStrategieMix;
}

// =========================================================================


function QuaakAnalyseMinimaxAnalyse(ChipsL,ChipsR,Saldo)
// Es findet eine rekursive Analyse statt, wobei die Position
// (ChipsL,ChipsR,Saldo) und deren Nachfolgepositionen untersucht werden:
{
  var i;
  // zur Verhinderung eines Stapelüberlaufs aufgrund einer zu hohen Rekursionstiefe 
  // werden zunächst spätere Positionen (in einer ungefähr chronologischen Reihenfolge)
  // untersucht:
  for (i=Math.min(ChipsL,ChipsR)-1;i>=0;i--)
    this.Minimax(ChipsL-i,ChipsR-i,Saldo);
}


function QuaakAnalyseMinimax(ChipsL,ChipsR,Saldo)
// Ermittelt den MinimaxWert zur Position (ChipsL,ChipsR,Saldo):
{
  // prüfe zunächst, ob das Spiel bereits zu Ende ist:
  if (Saldo>=3)
    return  1;

  if (Saldo<=-3)
    return -1;

  if ((ChipsL+ChipsR)==0)
  {
    if (this.SpielregelVariante==0)
      return  0;
    else if (Saldo>0)
      return  1;
    else if (Saldo<0)
      return -1;
    else
      return  0;
  }

  if (this.SpielregelVariante==0 && ((ChipsL==0) || (ChipsR==0)) )
  {
    if ((ChipsL==0) && (Saldo-ChipsR<=-3))
      return -1;
    if ((ChipsR==0) && (Saldo+ChipsL>= 3))
      return  1;
    return  0;
  }

  if (ChipsL>ChipsR)
    // verwende Symmetrie:  
    return -this.Minimax(ChipsR,ChipsL,-Saldo);

  var Key, ret;
  Key=ChipsL+","+ChipsR+","+Saldo;
  ret=this.MinimaxWerte.Bild(Key);                                 // ggf. bereits abgespeicherter Wert
  if (ret !=null)
    return ret;

  // Der gewünschte Minimax-Wert muss rekursiv berechnet werden:  
  var A, ChL, ChR, SaldoNeu, IterEnd, a00;
  IterEnd=false;
  a00=0;                                                           // Iterations-Startwert für a00 in Matrix
  while (!IterEnd)
  {
    A = new MatrixSpiel();
    for (ChL=0;ChL<=Math.min(3,ChipsL);ChL++)
      for (ChR=0;ChR<=Math.min(3,ChipsR);ChR++)
      {
        if (ChL>ChR)
          SaldoNeu=Saldo+1;
        else if (ChL<ChR)
          SaldoNeu=Saldo-1;
        else
          SaldoNeu=Saldo;
        if (ChL+ChR>0) 
          A.Set_a("x"+ChL,"y"+ChR, this.Minimax(ChipsL-ChL,ChipsR-ChR,SaldoNeu));
      }
    A.Set_a("x0","y0",a00);        
    ret=A.Minimax();
    IterEnd=(Math.abs(a00-ret)<0.000001);

    a00=ret;
 }

 this.MinimaxWerte.DefBild(Key,ret);                                 // speichere Wert ab
 return ret;
}


function QuaakAnalyseStrategieMix(ChipsL,ChipsR,Saldo,Spieler)
// bestimmt zu einer Position für Spieler=1,2 das optimale
// Strategie-Mix:
{
  var A, ChL, ChR, SaldoNeu, ret;
  ret=new Array(0,0,0,0);

  A = new MatrixSpiel();
  for (ChL=0;ChL<=Math.min(3,ChipsL);ChL++)
    for (ChR=0;ChR<=Math.min(3,ChipsR);ChR++)
    {
      if (ChL>ChR)
        SaldoNeu=Saldo+1;
      else if (ChL<ChR)
        SaldoNeu=Saldo-1;
      else
        SaldoNeu=Saldo;
      A.Set_a("x"+ChL,"y"+ChR, this.Minimax(ChipsL-ChL,ChipsR-ChR,SaldoNeu));
    }
  A.Minimax();
 
  if (Spieler==1)
    for (ChL=0;ChL<=Math.min(3,ChipsL);ChL++)
      ret[ChL]=A.Wert("x"+ChL);

  if (Spieler==2)
    for (ChR=0;ChR<=Math.min(3,ChipsR);ChR++)
      ret[ChR]=A.Wert("y"+ChR);

  return ret;

}