source: liacs/pm/qt-nim/nimSpel.cc@ 2

/*programeeropdracht 4 The Nim Game
 *Pascal de Vos  (ID = 0446916)
 *Rick van der Zwet (ID = 0433373)
 *file: nimSpel.cc
 *de is het rekengedeelte van mainForm.cc, hierin kan makkelijk en snel
 *gegevens worden verwerkt en oplossingen worden doorgerekend
 */
#include "nimSpel.h"
#include "const.h"
#include <cstdlib>

using namespace std;
NimSpel::NimSpel( ){ //constructor
  laatsteZet_pt = NULL;
  aantalZetten = 0;
} //end NimSpel::NimSpel



//aantal beurten terug geven
int NimSpel::aantalBeurten( ){
  return( aantalZetten/2 );
} //end NimSpel::aantalBeurten



//aantal op stapel teruggeven
int NimSpel::aantalOpStapel( const int nummer ){
  return( stapels[nummer] );
} //end NimSpel::aantalOpStapel



//aantal actieve stapels teruggeven
int NimSpel::actieveStapels( ){
  return( aantalStapels );
} //end NimSpel::actieveStapels

bool NimSpel::afgelopen( ){ //kijken of spel afgelopen is
  for( int i = 0; i < MAX_STAPELS; i++ ) {
    if( stapels[i] > 0 ) { //als er nog ergens waardes aanwezig zijn
      return( false );
    }//end if
  }//end if
  return( true );
}//end NimSpel::afgelopen



//zet de beginwaarden van de stapel
void NimSpel::beginWaarden( const int stapelAantal, const int aantal) {
  zetTerug(aantalZetten/2); //terugzetten om oude pointer naar NULL te
                            //helpen en alles netjes de destructen
  for( int i = 0; i < stapelAantal; i++ ) {
    stapels[i] = aantal;
    aantalStapels = stapelAantal;
  } //end for
} //end NimSpel::beginWaarden



//creer een nieuwe zet voor de computer
void NimSpel::computerZet( const bool niveauComputer, int & stapelNummer,
                           int & aantal) {
  int tmpStapelNummer = -1;
  int tmpAantal = -1;
  
  if( niveauComputer ) { //winnend spelen als dat verwacht wordt
    winnend( tmpStapelNummer, tmpAantal );
  } //end if
  
  if( tmpAantal == -1 ) {
    //hij zal in deze if komen als er geen winnnende keuzes zijn 
    randomZet( tmpStapelNummer, tmpAantal );
  } //end if
  
  stapelNummer = tmpStapelNummer;
  aantal = tmpAantal;
} //end NimSpel::computerZet



//doe een random zet, die wel in de range van een stapel aantal ligt
void NimSpel::randomZet( int & stapelNummer, int & aantal ) {
  do {
    stapelNummer = int( double(aantalStapels) * rand()/(RAND_MAX+1.0) );
    aantal = 1 + int( double(2) * rand()/(RAND_MAX+1.0) );
  } //end do
  while( stapels[stapelNummer] - aantal < 0 );
}//end NimSpel::randomZet



//verwerk een zet
void NimSpel::pakWeg( const int stapelNummer, const int aantal ){
  NimStapel * temp_pt;                        //
  temp_pt = new NimStapel;                    //
  temp_pt->vorigeZet_pt = laatsteZet_pt;      //Zetten onthouden
  laatsteZet_pt = temp_pt;                    //
  laatsteZet_pt->stapelNummer = stapelNummer; //
  laatsteZet_pt->aantalEraf = aantal;         //
  aantalZetten++;                             //Max Zetten bijhouden
  stapels[stapelNummer] = stapels[stapelNummer] - aantal; 
} //end NimSpel::pakweg



//zoek recursief het aantal winnende sporen en het aantal
//verliezende sporter
void NimSpel::recur( const int aantal, const bool aanBeurt,
            int & aantalWinst, int & aantalVerlies ) {
  if( aantal < 3 ) { //aantal lager dan 3
    if( aanBeurt ) { //als je aan beurt bent dan een winstpunt
      aantalWinst++;
    }
    else {           //en anders een verliespunt
      aantalVerlies++;
    }
  }
  else {             //3 en hoger zorgt ervoor dat we de functie weer
                     //aan moeten roepen en wel met 1 en 2 minder
    recur( aantal-1, !(aanBeurt), aantalWinst, aantalVerlies);
    recur( aantal-2, !(aanBeurt), aantalWinst, aantalVerlies);
  }
} //end NimSpel::recur;



//zoek de keuze op met de meeste winkans
//als er niet gewonnen kan worden return voor keuze '-1'
void NimSpel::recurKeuze( const int aantal, int & keuze, double & winstKans ) {
  int min1Winst = 0;      //winst paden voor aantal-1
  int min1Verlies = 0;    //verlies paden voor aantal-1
  int min2Winst = 0;      //winst paden voor aantal-2
  int min2Verlies = 0;    //verlies paden voor aantal-2
  double win1Kans = 0;    //kans op winst met 1
  double win2Kans = 0;    //kans op winst met 2
    
    if( aantal < 1 ) {      //aantal is 0 of minder, kans op -2 zetten,
    keuze = aantal;         //want hij is afgelopen
    winstKans = -2;
    }
    else if( aantal < 3 ) { //als er minder als 3 worden opgegeven hebben
    keuze = aantal;         //we altijd een winst situatie en gaan we niet 
    winstKans = 10;
    }
    else {                  //recursief rekenen
    recur( aantal-1, false, min1Winst, min1Verlies ); //reken 
    recur( aantal-2, false, min2Winst, min2Verlies ); //kansen uit
    
    //aangezien door 0 delen niet mag, zullen we de verliesKans met 1 
    //ophogen om zo toch eerlijkt te kunnen rekenen
    min1Verlies++;
    min2Verlies++;
    win1Kans = double(min1Winst)/double(min1Verlies);
    win2Kans = double(min2Winst)/double(min2Verlies);
    
    //Als beiden kanten (-1 en -2) geen winst ergens oplevert is het
    //hopenloos verloren en zullen we dit ook aangeven
    //anders de kans met de meeste winst teruggeven
    if( (min1Winst == 0) and (min2Winst == 0) ) {
      keuze = -1;
      winstKans = -1;
    }
    else if( win1Kans > win2Kans ) {
      keuze = 1;
      winstKans = win1Kans;
    }
    else {
      keuze = 2;
      winstKans = win2Kans;
    }//end if

  } //end if
  
} //end NimSpel::recurKeuze



//zoek de winnende zet uit (met hulp van een recursieve formule)
void NimSpel::winnend( int & stapelNummer, int & aantal ) {
  int tmpStapelNummer = -1; //-1 om ervoor te zorgen dat de winnende zet -1
  int tmpAantal = -1;       //wordt als er geen winnende zetten zijn
  int tmpKeuze = 0;         //(uit recurKeuze functie)
  double tmpKans = 0;       //tijdelijke Kans en Keuze
  double kansMax = 0;       //tijdelijk Variable voor geldende maximale kans

  for( int i = 0; i <( aantalStapels - 1); i++ ) {
  //ga alle stapels af en van de stapel met de meeste kans pak je de
  //winnnende stokjes vanaf
    recurKeuze( stapels[i], tmpKeuze, tmpKans ); //bereken waardes

    if( tmpKans > kansMax ) {
      tmpStapelNummer = i;
      tmpAantal = tmpKeuze;
      kansMax = tmpKans;
    } //end if

  }//end for
  stapelNummer = tmpStapelNummer;
  aantal = tmpAantal;
}// end NimSpel::winnnend


//zet beurten terug
void NimSpel::zetTerug( const int aantalBeurten ) {
  int aantalStappen = aantalBeurten * 2;
  NimStapel * temp_pt;
  for( int i = 0; i < aantalStappen; i++ ) {
    temp_pt = laatsteZet_pt;
    stapels[temp_pt->stapelNummer] =
    ( stapels[temp_pt->stapelNummer] + temp_pt->aantalEraf );
    aantalZetten--;
    laatsteZet_pt = temp_pt->vorigeZet_pt;
    delete temp_pt;
  } //end for
} //end NimSpel::ZetTerug



//kijk of je niet meer stokjes van een stapel afpakt als dat er liggen
bool NimSpel::zetMogelijk( const int stapelNummer,
                           const int aantalPakken ) {
  if( (stapels[stapelNummer] - aantalPakken) < 0 ) {
    return false;
  }
  else {
    return true;
  } //end if
} //end NimSpel::zetMogelijk