behavsol.cc

Gambit 是一个游戏库理论软件

//
// $Source: /home/gambit/CVS/gambit/sources/nash/behavsol.cc,v $
// $Date: 2002/09/30 20:00:09 $
// $Revision: 1.5.2.2 $
//
// DESCRIPTION:
// Implementation of behavior strategy solution class
//
// This file is part of Gambit
// Copyright (c) 2002, The Gambit Project
//
// This program is free software; you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation; either version 2 of the License, or
// (at your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with this program; if not, write to the Free Software
// Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
//

#include "math/gmath.h"
#include "behavsol.h"
#include "behavextend.h"
#include "game/lexicon.h"  // needed for ReducedNormalFormRegrets

// we probably want to break this out into another file (rdm)

#include "base/gnullstatus.h"
#include "nash/subsolve.h"

class SubgamePerfectChecker : public SubgameSolver  {
private:
  int subgame_number;
  gNumber eps;
  gTriState isSubgamePerfect;
  gPVector<int> infoset_subgames;
  BehavProfile<gNumber> start;
  gList<Node *> oldroots;
  
  void SolveSubgame(const efgGame &, const EFSupport &,
		    gList<BehavSolution> &, gStatus &);
  
public:
  SubgamePerfectChecker(const efgGame &, const BehavProfile<gNumber> &, const gNumber & epsilon);
  virtual ~SubgamePerfectChecker();
  gTriState IsSubgamePerfect(void) {return isSubgamePerfect;}
};

//----------------------------------------------------
// Constructors, Destructor, Constructive Operators
//----------------------------------------------------

BehavSolution::BehavSolution(const BehavProfile<double> &p_profile,
			     const gText &p_creator)
  : m_profile(new BehavProfile<gNumber>(EFSupport(p_profile.GetGame()))),
    m_precision(precDOUBLE),
    m_support(p_profile.Support()), m_creator(p_creator),
    m_ANFNash(), m_Nash(), m_SubgamePerfect(), m_Sequential(), 
    m_epsilon(0.0), m_qreLambda(-1), m_qreValue(-1),
    m_liapValue(), m_rnfRegret(), 
    m_revision(p_profile.GetGame().RevisionNumber())
{
  gEpsilon(m_epsilon);
  for (int pl = 1; pl <= GetGame().NumPlayers(); pl++) {
    EFPlayer *player = GetGame().Players()[pl];  
    for (int iset = 1; iset <= player->NumInfosets(); iset++) {
      Infoset *infoset = player->Infosets()[iset];
      for (int act = 1; act <= infoset->NumActions(); act++) {
	int index = p_profile.Support().Find(infoset->Actions()[act]);
	if (index > 0)
	  (*m_profile)(pl, iset, act) = p_profile(pl, iset, index);
	else
	  (*m_profile)(pl, iset, act) = gNumber(0.0);
      }
    }
  }
}


BehavSolution::BehavSolution(const BehavProfile<gRational> &p_profile,
			     const gText &p_creator)
  : m_profile(new BehavProfile<gNumber>(EFSupport(p_profile.GetGame()))),
    m_precision(precRATIONAL), 
    m_support(p_profile.Support()), m_creator(p_creator),
    m_ANFNash(), m_Nash(), m_SubgamePerfect(), m_Sequential(), 
    m_qreLambda(-1), m_qreValue(-1), m_liapValue(), m_rnfRegret(), 
    m_revision(p_profile.GetGame().RevisionNumber())
{
  gEpsilon(m_epsilon);
  for (int pl = 1; pl <= GetGame().NumPlayers(); pl++) {
    EFPlayer *player = GetGame().Players()[pl];  
    for (int iset = 1; iset <= player->NumInfosets(); iset++) {
      Infoset *infoset = player->Infosets()[iset];
      for (int act = 1; act <= infoset->NumActions(); act++) {
	int index = p_profile.Support().Find(infoset->Actions()[act]);
	if (index > 0)
	  (*m_profile)(pl, iset, act) = p_profile(pl, iset, index);
	else
	  (*m_profile)(pl, iset, act) = gNumber(0);
      }
    }
  }
}

BehavSolution::BehavSolution(const BehavProfile<gNumber> &p_profile, 
			     const gText &p_creator)
  : m_profile(new BehavProfile<gNumber>(EFSupport(p_profile.GetGame()))),
    m_precision(precRATIONAL),
    m_support(p_profile.Support()), m_creator(p_creator),
    m_ANFNash(), m_Nash(), m_SubgamePerfect(), m_Sequential(), 
    m_qreLambda(-1), m_qreValue(-1), m_liapValue(), m_rnfRegret(), 
    m_revision(p_profile.GetGame().RevisionNumber())
{
  for (int pl = 1; pl <= GetGame().NumPlayers(); pl++) {
    EFPlayer *player = GetGame().Players()[pl];  
    for (int iset = 1; iset <= player->NumInfosets(); iset++) {
      Infoset *infoset = player->Infosets()[iset];
      for (int act = 1; act <= infoset->NumActions(); act++) {
	int index = p_profile.Support().Find(infoset->Actions()[act]);
	if (index > 0)
	  (*m_profile)(pl, iset, act) = p_profile(pl, iset, index);
	else
	  (*m_profile)(pl, iset, act) = gNumber(0);
      }
    }
  }
  LevelPrecision();

  m_epsilon = 0;
  if((*m_profile).Length()>0) 
    if ((*m_profile)[1].Precision() == precDOUBLE)
      m_epsilon = 0.0;

  gEpsilon(m_epsilon);
}

BehavSolution::BehavSolution(const BehavSolution &p_solution)
  : m_profile(new BehavProfile<gNumber>(*p_solution.m_profile)),
    m_precision(p_solution.m_precision), 
    m_support(p_solution.m_support), m_creator(p_solution.m_creator),
    m_ANFNash(p_solution.m_ANFNash),
    m_Nash(p_solution.m_Nash),
    m_SubgamePerfect(p_solution.m_SubgamePerfect),
    m_Sequential(p_solution.m_Sequential),
    m_epsilon(p_solution.m_epsilon),
    m_qreLambda(p_solution.m_qreLambda),
    m_qreValue(p_solution.m_qreValue),
    m_liapValue(p_solution.m_liapValue),
    m_rnfRegret(p_solution.m_rnfRegret), 
    m_name(p_solution.m_name),
    m_revision(p_solution.m_revision)
{ }

BehavSolution::~BehavSolution() 
{ 
  delete m_profile;
}

BehavSolution& BehavSolution::operator=(const BehavSolution &p_solution)
{
  if (this != &p_solution)   {
    delete m_profile;
    m_profile = new BehavProfile<gNumber>(*p_solution.m_profile);
    m_precision = p_solution.m_precision;
    m_support = p_solution.m_support;
    m_creator = p_solution.m_creator;
    m_ANFNash = p_solution.m_ANFNash;
    m_Nash = p_solution.m_Nash;
    m_SubgamePerfect = p_solution.m_SubgamePerfect;
    m_Sequential = p_solution.m_Sequential;
    m_epsilon = p_solution.m_epsilon;
    m_qreLambda = p_solution.m_qreLambda;
    m_qreValue = p_solution.m_qreValue;
    m_liapValue = p_solution.m_liapValue;
    m_rnfRegret = p_solution.m_rnfRegret;
    m_name = p_solution.m_name;
    m_revision = p_solution.m_revision;
  }

  return *this;
}

//-----------------------------
// Private member functions
//-----------------------------

gTriState BehavSolution::GetANFNash(void) const
{
  gNullStatus status;
  algExtendsToAgentNash algorithm;
  gTriState answer = ((algorithm.ExtendsToAgentNash(*this,
						    Support(), Support(),
						    status)) ?
		      triTRUE : triFALSE);
  if (answer == triFALSE) {
    m_Nash.Set(triFALSE);
    m_SubgamePerfect.Set(triFALSE);
    m_Sequential.Set(triFALSE);
  }
  return answer;
  return triUNKNOWN;
}

gTriState BehavSolution::GetNash(void) const
{
  gTriState answer = triUNKNOWN;
  bool decomposes = HasSubgames(GetGame());
  // check subgame perfection if game decomposes (its faster)
  if(decomposes) 
    GetSubgamePerfect();
  // if it was settled in that call, ...
  if (m_Nash.Checked() == true) 
    answer = m_Nash.Answer();
  else {
    // use reduced normal form regrets for complete profiles
    if (IsComplete()) {
      answer = (MaxRNFRegret() <= m_epsilon) ? triTRUE:triFALSE;
    }
    else {
      //  else let Andy figure it out
      // Is perfect recall needed here, Andy?
      if (IsPerfectRecall(m_profile->GetGame())) { 
	// not sure MaxRegret does the right thing here
	gNullStatus status;
	algExtendsToNash algorithm;
	answer = (m_profile->MaxRegret() <= m_epsilon  &&
		  algorithm.ExtendsToNash(*this,Support(),Support(),status)) 
	  ? triTRUE:triFALSE;
      }
      else {
	answer = triUNKNOWN;
      }
    }
  }
  // Done.  Now mark other obvious inferences 
  
  if (answer == triFALSE) {
    m_SubgamePerfect.Set(triFALSE);
    m_Sequential.Set(triFALSE);
  }
  if (answer == triTRUE) {
    m_ANFNash.Set(triTRUE);
    if(!decomposes) 
      m_SubgamePerfect.Set(triTRUE);
  }
  return answer;
}

gTriState BehavSolution::GetSubgamePerfect(void) const
{
  gTriState answer;
  // Note -- HasSubgames should be cached in Efg
  bool decomposes = HasSubgames(GetGame());
  if(!decomposes) GetNash();
  // if it was already resolved ...
  if(m_SubgamePerfect.Checked() == true) 
    answer = m_SubgamePerfect.Answer();
  else {
    // for complete profiles, use subgame perfect checker.  
    if (IsComplete()) {
      BehavProfile<gNumber> p(*m_profile);
      SubgamePerfectChecker checker(p.GetGame(),p, Epsilon());
      gNullStatus status;
      checker.Solve(p.Support(), status);
      answer = checker.IsSubgamePerfect();
    }
    // else, for now, we require complete profiles for subgame perfection.  
    // but we may want to turn over to Andy here. 
    else {
      answer = triUNKNOWN;
    }
  }
  // Done.  Now mark other obvious inferences 
  
  if (answer == triTRUE) {
    m_Nash.Set(triTRUE);
    m_ANFNash.Set(triTRUE);
  }
  else if (answer == triFALSE) {
    m_Sequential.Set(triFALSE);
    if (!decomposes) {
      m_Nash.Set(triFALSE);
    }
  }
  return answer;
}

gTriState BehavSolution::GetSequential(void) const
{
  if(IsSubgamePerfect()==triTRUE) {
    // Liap and QRE should be returning Nash solutions that give positive 
    // probability to all actions, and hence will be approximations to 
    // sequential equilibria.  But we should add code to check up on these 
    // algorithms
    if (Creator() == "Liap[EFG]" || Creator() == "Qre[EFG]")
      return triTRUE;
    else {
      // check if game is perfect info
      // this should be in efg.h
      bool flag = true;
      gPVector<int> v((GetGame()).NumMembers());
      for(int i=v.First();flag == true && i<=v.Last();i++)
	if(v[i]>1) flag = false;
      if(flag==true) return triTRUE;
    }
    return triUNKNOWN;
  }
  else 
    return IsSubgamePerfect();
}

/*
gNumber BehavSolution::GetLiapValue(void)
{ 
  return m_profile->LiapValue();
}
*/

void BehavSolution::LevelPrecision(void)
{
  m_precision = precRATIONAL;
  for (int pl = 1; m_precision == precRATIONAL && pl <= GetGame().NumPlayers();
       pl++) {
    EFPlayer *player = GetGame().Players()[pl];  
    for (int iset = 1; (m_precision == precRATIONAL && 
			iset <= player->NumInfosets()); iset++) {
      Infoset *infoset = player->Infosets()[iset];
      for (int act = 1; (m_precision == precRATIONAL && 
			 act <= infoset->NumActions()); act++) {
	if ((*m_profile)(pl, iset, act).Precision() == precDOUBLE)
	  m_precision = precDOUBLE;
      }
    }
  }

  if (m_precision == precDOUBLE) {
    for (int pl = 1; pl <= GetGame().NumPlayers(); pl++) {
      EFPlayer *player = GetGame().Players()[pl];  
      for (int iset = 1; iset <= player->NumInfosets(); iset++) {
	Infoset *infoset = player->Infosets()[iset];
	for (int act = 1; act <= infoset->NumActions(); act++) {
	  (*m_profile)(pl, iset, act) = (double) (*m_profile)(pl, iset, act);
	}
      }
    }
  }