I have been working on a very simple artificial intelligence algorithm based upon my limited knowledge of game theory. The purpose of the algorithm is to keep track of other actors' karma so that we know how to treat them. The algorithm is a modified tit-for-tat (as demonstrated in Thinking Strategically).

Assume that we are creating a virtual world which contains a main character who interacts with other actors. The main character would instantiate a karma object (var actor_karma = new karma();) for each of the other actors he encounters. For each interaction with the other actors the main character records whether that actor's actions were good (actor_karma.addDeed(true);) or bad (actor_karma.addDeed(false);). Based upon this information the main character would know whether he should treat the actor favorably (true is returned) or not (false is returned).

Below is the JavaScript code (continued after the jump).

/**
 * Karma (Game Theory) class/object
 *
 * @constructor
 * @this {karma}
 */
function karma(){
 this._timeShort = 3;   // number of deeds in short-term
 this._timeMedium = 20;   // number of deeds in medium-term
 this._timeLong = 100;   // number of deeds in long-term
 this._timeProbation = 20// number of deeds in probation
 this._timeNormalization = 50; // number of deeds til normalization
 this._minGoodShort = .35// minimum % of short-term good deeds
 this._minGoodMedium = .85// minimum % of medium-term good deeds
 this._minGoodLong = .96// minimum % of long-term good deeds

 this._isEvil = false;   // the object is considered wicked
 this._isMaybeEvil = false// the object may be considered wicked

 this._deeds = new Array();  // array of this objects deeds
 this._timeSinceLastBad = -1; // time since this object's last bad deed

 this.giveGoodwill = true// should this object receive goodwill
}

 /**
  * Calculate goodwill based upon tit-for-tat
  *
  * @private
  * @this {karma}
  * @param {boolean} pDeedIsGood Is the new deed good
  * @returns {boolean} Wheather to return goodwill
  */
 karma.prototype._titForTat = function(pDeedIsGood){  
  if(pDeedIsGood){
   this.giveGoodwill = true;
  }else{
   this.giveGoodwill = false;
  }
  return this.giveGoodwill;
 }


 /**
  * Calculate karma for a given timeframe
  *
  * @private
  * @this {karma}
  * @param {numeric} pTimeFrame Time frame to calculate for
  * @param {numeric} pMinGood Minimum allowed good percentage
  * @returns {boolean} Wheather to return goodwill
  */
 karma.prototype._calcTermKarma = function(pTimeFrame, pMinGood){
  var goodDeedCount = 0,
   goodDeedPercent = 1;
   
  // evaluate the timeframe if we can
  if(this._deeds.length >= pTimeFrame){
   for(i=0; i
    if(this._deeds[this._deeds.length-i-1]){
     goodDeedCount++;
    }
   }
   
   // short-term good deed percentage
   goodDeedPercent = goodDeedCount / pTimeFrame;
   
   // DEBUG
   //console.log('goodDeedPercent: '+goodDeedPercent*100+'% ('+goodDeedCount+'/'+pTimeFrame+') ');
   
   // is the good deed percentage below required
   if(goodDeedPercent < pMinGood){
    // then this object may be evil
    this._isMaybeEvil = true;
    this._timeSinceLastBad = 0;
   }
  }
 }

 /**
  * Add a deed to this objects karma (private)
  *
  * @private
  * @this {karma}
  * @param {boolean} pDeedIsGood Is the new deed good
  * @returns {boolean} Wheather to return goodwill
  */
 karma.prototype._addDeed = function(pDeedIsGood){
  this._deeds.push(pDeedIsGood);
  
  if(this._deeds.length > this._timeLong){
   this._deeds = this._deeds.splice(1, this._timeLong);
  }
  
  // calculate short-term karma
  this._calcTermKarma(this._timeShort, this._minGoodShort);
  
  // calculate medium-term karma
  this._calcTermKarma(this._timeMedium, this._minGoodMedium);
  
  // calculate long-term karma
  this._calcTermKarma(this._timeLong, this._minGoodLong);
  
  // this object is suspect
  if(this._isMaybeEvil){
   this._timeSinceLastBad++;
   
   // DEBUG
   //console.log('this._timeSinceLastBad: '+this._timeSinceLastBad+' ');
   
   // this object should no longer be suspect
   if(this._timeSinceLastBad >= this._timeNormalization){
    // take the object off of probation
    this._isMaybeEvil = false;
    this._timeSinceLastBad = -1;
    this.giveGoodwill = true;
    return this.giveGoodwill;
   
   // this object stays suspect
   }else{
    // this object is not under the probation period
    if(this._timeSinceLastBad >= this._timeProbation){
     this.giveGoodwill = true;
     return this.giveGoodwill;
    
    // this object is under the probation period
    }else{
     return this._titForTat(pDeedIsGood);
    }
   }
  
  // this object is not suspect
  }else{
   this.giveGoodwill = true;
   return this.giveGoodwill;
  }
 }

 /**
  * Add a deed to this objects karma
  *
  * @this {karma}
  * @param {boolean} pDeedIsGood Is the new deed good
  * @returns {boolean} Wheather to return goodwill
  */
 karma.prototype.addDeed = function(pDeedIsGood){  
  // this object is not wicked
  if(!this._isEvil){
   // this object has past deeds
   if(this._deeds.length > 0){
    // this object is not suspect
    if(!this._isMaybeEvil){
     return this._addDeed(pDeedIsGood);
    
    // this object is already suspect
    }else{
     // this object is making good
     if(pDeedIsGood){
      return this._addDeed(pDeedIsGood);
     
     // this object has broken probation
     }else{
      this._isEvil = true;
      return this._titForTat(pDeedIsGood);
     }
    }
   
   // this object has no past deeds
   }else{
    // the first impresion is good
    if(pDeedIsGood){
     return this._addDeed(pDeedIsGood);
     
    // the first impresion is bad
    }else{
     this._isEvil = true;
     return this._titForTat(pDeedIsGood);
    }
   }
   
  // this object is wicked
  }else{
   return this._titForTat(pDeedIsGood);
  }
 }

Tags: Blogger JavaScript Game Theory Code Algorithms

Published: 2011-05-15