// Originally designed & written by: H. Kuijpers © 2001
// Contact me at: hkuijpers@xs4all.nl
// Feel free to redistribute, copy and change this code, but please make
// a reference to this code and the author.
// Please report any bugs, inconsistancies, comments or other helpful tips 
// to the mail address above

// this module contains all functions concerning the artificial intelligence
// of the computer players
// this particular implementation works as follows:
// first all the cards of the players hand are verified with the rules of the
// game wether the selected card can be played or not.
// this will yield a set of cards that can be played 
// for each card that can be played, the max-min method is applied.
// this means that for a playable card, the scores are estimated that
// could be won or lost if the particular card was played.
// an estimate is based on some simple odds-calculations
// multiplied by the score that could be achieved.
// this will yield 3 scores: the estimated score for the this team and
// the estimates score for the other team, and the differences between scores
// this will be calculated for all playable cards.
// also for each card the potential risk is calculated the round is won or lost.
// based on the risk, the ai will play the card that will: 
//  - maximize our score -> maximal exploitation, if round is probably won
//  - minimize effort to win the round, if round is definately won
//  - minimize their score -> minimal damage, if round is lost anyway
// then the ai-player will descide which card to play based on these
// scores. the simples rule is to select the card that will yield the greatest
// difference in scores. 

function Push(elt) {
   this.length = this.length + 1;
   this[this.length-1] = elt;
}

// overload the array push function, since it is not supported for ie5.0
Array.prototype.push = Push;

// returns the index of the card to be played
function SelectPlayCard()
{
	var verify =0; 
	var cards = this.hand.cards;
	var curGame;
	var curRound;
	var curTrump;
	var playable = new Object;
	var first;
	var verify;
	var l;
	curGame = Match.Games[Match.GameIndex];
	curRound = curGame.Rounds[curGame.RoundIndex];	
	curTrump = Match.Trumps.cards[Match.Trumps.index];	
	first = Match.Table.cards[curRound.PlayerStart];
	cards = this.hand.cards;
	playable.indexes = new Array();
	playable.max = new Array();
	playable.min = new Array();
	playable.diff = new Array();
	playable.mean = new Array();
	playable.risk = new Array();
	playable.count = 0;
	
	for (l=0; (l<cards.length); l++) {		
		if (this.hand.pos[l].played == 'false') {
			
			verify = VerifyPlayCard(l, this, Match.Table, curTrump, curRound.PlayerStart);	
			if (verify == 0) {	
			  playable.indexes.push(l); // store the indexes of the playable cards.
			  playable.max.push(0);
			  playable.min.push(0);
			  playable.diff.push(0);
			  playable.mean.push(0);
			  playable.mean.push(0);
			  playable.risk.push(0);
			  playable.count++;
			}			  
		}
	}
	
	// apply best card strategy here
	return SelectBestCard(this, playable, Match.Table, Match.Cards, curTrump);
}

// return true if player dares to play with the trumpcard
// returns the score
function EvaluatePlayColor(Trump) {
  var cards = this.hand.cards;
  //var s = CardsSum(cards, Trump, cards.length);
  //var m = CardsIndexesSum(cards, Trump, cards.length);
  
  s = PlayableCardsSum(cards, Trump, cards.length);

  //s = s * (m / 100);
  DebugPrint( this.name + ' his playable card score = ' + s);
  // this treshold depends on the player type.
  return s; // normalise
}

// returns the index of the color to be selected
// as trump, only used when player must select a trump (after 2 rounds)
function SelectPlayColor() {
  var trump;
  var i;
  var s;
  var m;
  var colors = new Array();
  var cards = this.hand.cards;
  
  for (i=0; i <4; i++) {
    trump = Match.TurnCards[i*5];    
    s = PlayableCardsSum(cards, trump, cards.length); // similar to EvaluatePlayColor, except this is a static function
    colors.push(s);
  }
  
  i = ArrayMaxScore(colors, colors, 4);
  //alert( i + ' - ' + colors[i]);
  return i;
  
}
// returns a value between 0 - 1
// 1 is a high risk, no chance in winning
// 0 is very low ris, will always win.
function GetRisk(perms, first, playcard, Trump, playcount) {

  var higher = 0
  var color = 0
  var highercolor = 0  
  var risk;
  for (l=0;l<perms.length;l++) {          
    if (perms[l].getcardindex(Trump, first) > playcard.getcardindex(Trump, first)) {
      higher++;
      if (perms[l].colorindex == first.colorindex) {
        DebugPrint('higher color = ' + perms[l].name);
        highercolor++;
      }    
    }
    if (perms[l].colorindex == first.colorindex) {
      color++;
    }    
  }

  // in case of troeven, overtroeven is always required, this has impact on
   // the risks, if one can overtroef, then he/she must, therefore the risk is 1
  DebugPrint('higher count = ' + higher  + ' highercolor = ' + highercolor + ' color = ' + color + ' len = ' + perms.length);
  if (first.colorindex == Trump.colorindex && higher > 0) {
    return 1.0;
  } else if (first.colorindex != Trump.colorindex && highercolor > 0) { // must play asked color, will most likely be taken over    
    return 1.0;
  }  
  risk = (higher / perms.length);
  return risk;
}


function GetPlayableCards(perms, cards, Trump, first, player) {
  var l;
	for (l=0; (l<cards.length); l++) {	    	  
	  if (cards[l].played == 'false' && (cards[l].colorindex == first.colorindex || cards[l].colorindex == Trump.colorindex) && !(HasCard(player.hand.cards, cards[l].value, cards[l].colorindex))) {	    
      perms.push(cards[l]); 
    }
  }
  for (l=0; (l<cards.length && perms.length < 4); l++) {
    if (cards[l].played == 'false' && (cards[l].colorindex != first.colorindex && cards[l].colorindex != Trump.colorindex) && !(HasCard(player.hand.cards, cards[l].value, cards[l].colorindex))) {	    
      perms.push(cards[l]); ;  // add dummy cards, otherwise algorithms will get messed up.
    }
  }

}

// implementation of the max-min algorithm
// this function contains most of the AI rules
// and calculates all possible options
// only one level deep
// also it uses some heuristics (rules), they are commented
function SelectBestCard(player, playable, table, cards, Trump) {
  var best;   
  var highestcard;   
  var perms;
  var p1, p2, p3, p4;
  var pl, pr, pt, pm;
  var i, j;
  var l;
  var score;
  var playcard;
	var curGame = Match.Games[Match.GameIndex];
	var curRound = curGame.Rounds[curGame.RoundIndex];	
  var first = Match.Table.cards[curRound.PlayerStart];
  var risks;
  
  //DebugClear();
    // estimate scores
	for (l=0; (l<playable.count); l++) {		
    playable.diff[l] = 0;
 	}

  //DebugPrint('Playcount = ' + Match.PlayCount);
  
  if (Match.PlayCount == 0) DebugClear();
  //if (Match.PlayCount == 3) alert();
  for (i=0; i<playable.count; i++) {  //start main evaluation loop
    risks = 0;
    score = 0;
    playcard = player.hand.cards[playable.indexes[i]]
    if (Match.PlayCount == 0) {
      //situation 1 of ai scenario (see rules.txt)
      // select cards that are still in the game and not mine and not on table and are of the playable color
      perms = new Array();      
      GetPlayableCards(perms, cards, Trump, playcard, player);
      //for (l=0; (l<perms.length); l++) {		
     	//  DebugPrint(l + ' ' + perms[l].name + ' - ' + perms[l].played);
      //}
      
      p1 = new Array();      
      p1.push(playcard);
      p2 = perms;
      p3 = perms;
      p4 = perms;      
      score = CalculateCombinations(p1, p2, p3, p4, playable, i, Match.PlayCount, Trump);
      playable.risk[i] = GetRisk(perms, playcard, playcard, Trump, Match.PlayCount)  * 2 / 3; // partner may have higher card
      var playing = (Match.ColorPlayerIndex) % 4;	// player that selected the playcolor

      var pt = 0;
      var pm = 0;
      if (playcard.colorindex == Trump.colorindex) { // i'm playing         
        // check perms if there are no more trumps out there
        for (j =0; j < perms.length; j++) {
          if (perms[j].colorindex == Trump.colorindex) 
            pt++;
        }
        // check trumps in hand
        for (j =0; j < player.hand.cards.length; j++) {
          if (player.hand.cards[j].colorindex == Trump.colorindex) 
            pm++;
        }       
      }
      // only play trumps if opponent still has some left and i'm playing
      pr = Match.Players[(player.index + 1) % 2] // player to the right
      pp = Match.Players[(player.index + 2) % 2] // partner player
      pl = Match.Players[(player.index + 3) % 2] // player to the left
      
      if (playing == player.index) {
        
        if (playcard.colorindex == Trump.colorindex) { // i'm playing         
          // check on trump!! review this!!
          if ((!pr.hand.colors[playcard.colorindex] && !pl.hand.colors[playcard.colorindex]) || pt == 0) {
            playable.risk[i] = 1.1;  // set to absolute maximum risk that trumps will be retrieved from partner or played without necessaty
            //alert('max risk!');
          } else if (pt > 1) {  // should try retrieve trumps
	    // try throw lowest trump here, since you'll probably lose it.
	    if (playable.risk[i] > 0.1) 
	    {
       	        playable.risk[i] = 0.3; // retrieving trumps will decrease score of opponent on long run, hardcode losses
        	score = 20 - playcard.getvalue(Trump); // hardcode reverse score, so lowest trump is thrown.
            	DebugPrint('reset playcard ' + playcard.name + ' value to ' + score);
	    }
            //alert('try retrieve trump even if losing');
          }
        }
      } else {
        // will reduce risk for trumps, if partner is playing.. this will make partner play a trump sooner
        if (playing % 2 == player.index % 2 && playcard.colorindex == Trump.colorindex)      
        {
          if ((!pr.hand.colors[playcard.colorindex] && !pl.hand.colors[playcard.colorindex]) || pt == 0) {
            playable.risk[i] == 1.1; // set to absolute maximum risk that trumps will be retrieved from partner or played without necessaty
          } else {
            playable.risk[i] /= 3; // reduce risk by third
          }
          //alert('reduce risk');
          DebugPrint('partner is playing -> ' + playcard.name + ' risk = ' + playable.risk[i]);
        } else if (playing % 2 != player.index % 2 && playcard.colorindex == Trump.colorindex) {
          if (pm <= 1) {            
            if (playable.risk[i] != 0) {
              playable.risk[i] = 1.1; // absolute maximum risk, must not retrieve trumps
            } else {
              playable.risk[i] = .3; // evaluate if it is feasable to play the card (ie. for bonus points).
            }
          }          
        }
      }

    } else if (Match.PlayCount == 1) {
      //situation 2 of ai scenario (see rulex.txt)
      // select cards that are still in the game and not mine and not on table and are of the playable color
      perms = new Array();
      GetPlayableCards(perms, cards, Trump, first, player);

      p1 = new Array();      
      p1.push(first);
      p2 = new Array();      
      p2.push(playcard);
      p3 = perms;
      p4 = perms;      
      score = CalculateCombinations(p1, p2, p3, p4, playable, i, 1, Trump);
      highestcard = playcard;
      if (p1[0].getcardindex(Trump, first) > playcard.getcardindex(Trump, first)) {
        playable.risk[i] = 1
      } else {      
        playable.risk[i] = GetRisk(perms, first, highestcard, Trump, Match.PlayCount) / 2;
      }
      
    } else if (Match.PlayCount == 2) {
      //situation 3 of ai scenario (see rulex.txt)
      // select cards that are still in the game and not mine and not on table and are of the playable color
      perms = new Array();
      GetPlayableCards(perms, cards, Trump, first, player);      

      p1 = new Array();      
      p1.push(first);
      p2 = new Array();      
      p2.push(Match.Table.cards[(curRound.PlayerStart + 1) % 4]);
      p3 = new Array();      
      p3.push(playcard);
      p4 = perms;      
      score = CalculateCombinations(p1, p2, p3, p4, playable, i, 0, Trump);

      highestcard = playcard;      
      if (p1[0].getcardindex(Trump, first) > highestcard.getcardindex(Trump, first)) {        
        highestcard = p1[0];
        if (p2[0].getcardindex(Trump, first) > highestcard.getcardindex(Trump, first)) {        
          highestcard = p2[0];
          playable.risk[i] = 1;
        } else {
          playable.risk[i] = GetRisk(perms, first, highestcard, Trump, Match.PlayCount);
        }
      } else {
        if (p2[0].getcardindex(Trump, first) > highestcard.getcardindex(Trump, first)) {        
          playable.risk[i] = 1;
        } else {
          playable.risk[i] = GetRisk(perms, first, highestcard, Trump, Match.PlayCount);
        }
      }
      
      if (p2[0].getcardindex(Trump, first) > p1[0].getcardindex(Trump, first) && p2[0].getcardindex(Trump, first) > playcard.getcardindex(Trump, first)) {
        playable.risk[i] = 1;
      }      
    } else {
      //situation 4 of ai scenario (see rulex.txt)
      // select cards that are still in the game and not mine and not on table and are of the playable color
      perms = new Array();
      GetPlayableCards(perms, cards, Trump, first, player);
      
      p1 = new Array();      
      p1.push(first);
      p2 = new Array();      
      p2.push(Match.Table.cards[(curRound.PlayerStart + 1) % 4]);
      p3 = new Array();      
      p3.push(Match.Table.cards[(curRound.PlayerStart + 2) % 4]);
      p4 = new Array();      
      p4.push(playcard);
      score = CalculateCombinations(p1, p2, p3, p4, playable, i, 0, Trump);
      playable.risk[i] = GetRisk(perms, first, playcard, Trump, Match.PlayCount);

      highestcard = playcard;      
      
      if ((p1[0].getcardindex(Trump, first) > playcard.getcardindex(Trump, first)) && (p1[0].getcardindex(Trump, first) > p2[0].getcardindex(Trump, first)) ) {        
          playable.risk[i] = 1; // the round is theirs
      } else if ((p3[0].getcardindex(Trump, first) > playcard.getcardindex(Trump, first)) && (p3[0].getcardindex(Trump, first) > p2[0].getcardindex(Trump, first)) ) {        
            playable.risk[i] = 1; // the round is theirs
      } else if ((p2[0].getcardindex(Trump, first) > p1[0].getcardindex(Trump, first)) && (p2[0].getcardindex(Trump, first) > p3[0].getcardindex(Trump, first)) ) {         
        // --> select signal or bonus card, alter the risk to         
        // make the algorithm select a more suitable card; this rule can be improved a lot
        // a simple heuristic is now used        
        playable.risk[i] = (playcard.getcardindex(Trump, first) / 50) * ((50 - playcard.getcardindex(Trump, first)) / 50)
        DebugPrint('signal card = ' + playcard.name + ' risk = ' + playable.risk[i]);
      } else {
        playable.risk[i] = 0; // the round is for me
      }      
    }  
    playable.max[i] = score * (1-playable.risk[i]);
    playable.min[i] = -score * playable.risk[i];
    playable.diff[i] = playable.max[i] - playable.min[i];
    playable.mean[i] = (playable.max[i] + playable.min[i]) / 2;
    DebugPrint('check = ' + player.hand.cards[playable.indexes[i]].name + ' : ' + playable.max[i] + ' - ' + playable.min[i] + ' diff = ' + playable.diff[i] + ' mean = ' + playable.mean[i]  + ' risk = ' + playable.risk[i]);   
    DebugPrint('');    
  } // next i


  var minRisk = ArrayMinRisk(playable.risk, playable.max, playable.count); 
  // set risk treshold here, could be characteristic of the player
  if (3 * playable.risk[minRisk] < 1.0) {   // if risk < 1/3 then maximise own score
    if (playable.risk[minRisk] == 0) { // if risk = 0, then minimise the effort to win this round (e.g. lowest troef)
	    best = ArrayMinEffort(playable.risk, playable.max, playable.count); ; 
	    DebugPrint('min effort = ' + playable.risk[best] + ' best = ' + best);
    } else { // select card with minimal risk of losing: 0 < risk < 1/3
	    best = minRisk; 
	    DebugPrint('min risk = ' + playable.risk[best] + ' best = ' + best);
	  }
	} else { // if risk > 1/3 then minimise their score
	  best = ArrayMaxScore(playable.min, playable.risk, playable.count); 
	  DebugPrint('min damage = ' + playable.min[best] + ' best = ' + best);
	}
  
  DebugPrint('');
	//alert(playable.indexes[best]);
  return playable.indexes[best];
}

function CalculateCombinations(p1, p2, p3, p4, playable, index, playerindex, Trump) 
{
  var i1, i2, i3, i4;
  var l;
  var counter = 0;
  var score = 0;
  var cards = new Array(4);

  str = p1.length + ' - ' + p2.length + ' - ' + p3.length + ' - ' + p4.length;
  DebugPrint(str); 
  for (i1=0;i1<p1.length;i1++) {
    for (i2=i1;i2<p2.length;i2++) {
      for (i3=i2;i3<p3.length;i3++) {
        for (i4=i3;i4<p4.length;i4++) {          
          cards[0] = p1[i1];
          cards[1] = p2[i2];
          cards[2] = p3[i3];
          cards[3] = p4[i4];
          if (cards[1].index != cards[2].index && cards[1].index != cards[3].index && cards[2].index != cards[3].index) {
            score += CardsValue(cards, Trump) + CardsBonus(cards, Trump);      
            //str = cards[0].name + ' - ' + cards[1].name + ' - ' + cards[2].name + ' - ' + cards[3].name + ' score = ' + score + ' them = ' + them;
            //DebugPrint(str); 
            counter++         
          }
        }
      }
    }
  }
  
  DebugPrint('score = ' + score + ' counter = ' + counter); 
  return score / counter;
 
}

// returns the index of the max value in the array
// if the index is equal, the values of the second array are compared
function ArrayMaxScore(arr, arr2, count) {
  var l;
  var i;
  i = 0
	for (l=1; (l<count); l++) {		
	  if (arr[i] == arr[l]) {
  	  if (arr2[i] < arr2[l]) {
  	    i = l;
  	  }	    
	  }
	  if (arr[i] < arr[l]) {
	    i = l;
	  }
	}
  return i;
}

// returns the index of the min value in the array
// if the index is equal or the arr2 value is higher than a treshold,
// then the expectation value is used as a criterium 
// typically used in cases of roem
function ArrayMinEffort(arr, arr2, count) {
  var l;
  var i;
  i = 0
	for (l=1; (l<count); l++) {		
	  if (arr[i] == arr[l] || arr[i] >= 20) {
  	  if ((1-arr[i]) * arr2[i] > (1- arr[l]) * arr2[l]) {
  	    i = l;
  	  }	    
	  }
	  if (arr[i] > arr[l]) {
	    i = l;
	  }
	}
  return i;
}

// returns the index of the min value in the array
// if the index is equal, the values of the second array are compared, will return the highest
function ArrayMinRisk(arr, arr2, count) {
  var l;
  var i;
  i = 0
	for (l=1; (l<count); l++) {		
	  if (arr[i] == arr[l]) {
  	  if (arr2[i] < arr2[l]) {
  	    i = l;
  	  }	    
	  }
	  if (arr[i] > arr[l]) {
	    i = l;
	  }
	}
  return i;
}


// calculates the sum of points of the cards for a certain trump value
function CardsSum(cards, trump, count) {
  var l;
  var s;
  var m;
  //var first = new Object();
  //first.color = 'none';
  s = 0
  m = 0;
	for (l=1; (l<count); l++) {		
	  s += cards[l].getvalue(trump);
	  m += cards[l].getcardindex(trump, cards[l]);
	}
  return s;
}

// calculates the sum of points of the cards for a certain trump value
function PlayableCardsSum(cards, trump, count) {
  var l;
  var s;
  var m;
  var colorcount;
  var card;
  var trumpcount = SameCardCount(cards, trump, count);
  
  m = 0; // initialize

  if (trumpcount > 3)
	 m += 10; // big +
  if (trumpcount < 1)
	 m += -10; // big -
    
  for (l=0; (l<count); l++) {		
	  colorcount = SameCardCount(cards, cards[l], count);
	  if (colorcount < 1) colorcount = 1; // just to be sure
  	  if (colorcount > 3) colorcount = 3;
	  
	  if (cards[l].colorindex == trump.colorindex) // trump card!
	  {
		m += playtrumpmatrix[colorcount][cards[l].value-7];
	  }
	  else // not trump card
	  {
		m += playcolormatrix[colorcount][cards[l].value-7];
	  }
  }
  return m;
}

function SameCardCount(cards, card, count)
{
	var m = 0;
	for (l=0; (l<count); l++) {			
	  if (cards[l].colorindex == card.colorindex)
		m ++;
	}	
	return m;
}


// calculates the sum of points of the cards for a certain trump value
function CardsIndexesSum(cards, trump, count) {
  var l;
  var s;
  var m;
  //var first = new Object();
  //first.color = 'none';
  m = 0;
	for (l=1; (l<count); l++) {		
	  m += cards[l].getcardindex(trump, cards[l]);
	}
  return m;
}

// calculates the sum of 1 to n (1+2+3..+n)
function sum(n) {
	var i;
	var r = n;
	if (n<1)
		return 0;
	for (i=1; i<n; i++) {
		r = r + i;
	}
	return r;
}

// calculates the faculty of n = n!
function fac(n) {
	var i;
	var r = n;
	if (n<=1)
		return 1;
	for (i=2; i<n; i++) {
		r = r * i;
	}
	return r;
}

// culculates number of permutations
function perm(n, k) {
	return fac(n) / fac(n-k);
}

// calculates n above k (number of combinations)
function above(n, k) {
	return fac(n) / (fac(n-k) * fac(k));
}