Simple Game Theory Algorithm 1 in JavaScript
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){
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);
}
}
