behavsol.cc

Gambit 是一个游戏库理论软件

}

//------------------------
// Operator overloading
//------------------------

bool BehavSolution::Equals(const BehavProfile<double> &p_profile) const
{  
  gNumber eps(m_epsilon);
  gEpsilon(eps, 4);  // this should be a function of m_epsilon

  int i = p_profile.First();
  while (i <= p_profile.Length()) {
    if (abs((*m_profile)[i] - (gNumber) p_profile[i]) > eps) 
      break;
    i++;
  }
  return (i > p_profile.Length());
}

bool BehavSolution::operator==(const BehavSolution &p_solution) const
{ return (*m_profile == *p_solution.m_profile); }

void BehavSolution::Set(Action *p_action, const gNumber &p_prob)
{
  Invalidate();

  Infoset *infoset = p_action->BelongsTo();
  EFPlayer *player = infoset->GetPlayer();
  (*m_profile)(player->GetNumber(), infoset->GetNumber(),
	       p_action->GetNumber()) = p_prob;
  if (m_precision != p_prob.Precision())
    LevelPrecision();
}

void BehavSolution::Set(int p_player, int p_infoset, int p_action,
			const gNumber &p_prob)
{
  Invalidate();

  (*m_profile)(p_player, p_infoset, p_action) = p_prob;
  if (m_precision != p_prob.Precision())
    LevelPrecision();
}

const gNumber &BehavSolution::operator()(Action *p_action) const
{
  Infoset *infoset = p_action->BelongsTo();
  EFPlayer *player = infoset->GetPlayer();
  return (*m_profile)(player->GetNumber(), infoset->GetNumber(),
		      p_action->GetNumber());
}

gNumber BehavSolution::operator[](Action *p_action) const
{
  return m_profile->GetActionProb(p_action);
}

gNumber &BehavSolution::operator[](Action *p_action)
{
  return (*m_profile)(p_action->BelongsTo()->GetPlayer()->GetNumber(),
		      p_action->BelongsTo()->GetNumber(),
		      p_action->GetNumber());
}

BehavSolution &BehavSolution::operator+=(const BehavSolution &p_solution)
{
  Invalidate(); 
  *m_profile += *p_solution.m_profile;
  if (m_precision == precRATIONAL && p_solution.m_precision == precDOUBLE)
    m_precision = precDOUBLE;
  return *this;
}

BehavSolution &BehavSolution::operator-=(const BehavSolution &p_solution)
{
  Invalidate();
  *m_profile -= *p_solution.m_profile;
  if (m_precision == precRATIONAL && p_solution.m_precision == precDOUBLE)
    m_precision = precDOUBLE;
  return *this;
}

BehavSolution &BehavSolution::operator*=(const gNumber &p_constant)
{ 
  Invalidate();
  *m_profile *= p_constant;
  if (m_precision == precRATIONAL && p_constant.Precision() == precDOUBLE)
    m_precision = precDOUBLE;
  return *this;
}

//-----------------------
// General data access
//-----------------------

bool BehavSolution::IsComplete(void) const
{ 
  gNumber sum;
  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];
      sum = -1;
      for (int act = 1; act <= infoset->NumActions(); act++) 
	sum += (*m_profile)(pl, iset, act);
      if (sum > m_epsilon || sum < -m_epsilon) 
	return false;
    }
  }
  return true;
}

const gTriState &BehavSolution::IsNash(void) const
{
  CheckIsValid();
  if (!m_Nash.Checked()) {
    m_Nash.Set(GetNash());
  }
  return m_Nash.Answer();
}

BehavSolution BehavSolution::PolishEq(void) const
{
#ifdef UNUSED
  bool is_singular = false;
  return PolishEquilibrium(m_support,*this,is_singular);
#endif // UNUSED
  return *this;
}

const gTriState &BehavSolution::IsANFNash(void) const
{
  CheckIsValid();
  if(!m_ANFNash.Checked())
    m_ANFNash.Set(GetANFNash());
  return m_ANFNash.Answer();
}

const gTriState &BehavSolution::IsSubgamePerfect(void) const
{
  CheckIsValid();
  if(!m_SubgamePerfect.Checked())
    m_SubgamePerfect.Set(GetSubgamePerfect());
  return m_SubgamePerfect.Answer();
}

const gTriState &BehavSolution::IsSequential(void) const
{
  CheckIsValid();
  if(!m_Sequential.Checked())
    m_Sequential.Set(GetSequential());
  return m_Sequential.Answer();
}

const gNumber &BehavSolution::LiapValue(void) const
{ 
  CheckIsValid();
  if(!m_liapValue.Checked())
    m_liapValue.Set(m_profile->LiapValue());
  return m_liapValue.Answer();
}

void BehavSolution::Invalidate(void) const
{
  // we depend on GCL or GUI to deallocate if there are structural 
  // changes in m_efg.  This only deals with changes in action probs of 
  // m_profile, and changes to outcome payoffs or chance probs of m_efg
  m_profile->Invalidate();
  m_support = EFSupport(m_profile->GetGame());
  m_creator = "User";
  m_ANFNash.Invalidate();
  m_Nash.Invalidate();
  m_SubgamePerfect.Invalidate();
  m_Sequential.Invalidate();
  m_qreLambda = -1;
  m_qreValue = -1;
  m_liapValue.Invalidate();
  m_rnfRegret.Invalidate();
  m_revision = GetGame().RevisionNumber();
}

//-----------------------------------------
// Computation of interesting quantities
//-----------------------------------------


gPVector<gNumber> BehavSolution::GetRNFRegret(void) const 
{
  const efgGame &E = GetGame(); 
  Lexicon L(E);  // we use the lexicon without allocating normal form.  
  
  for (int i = 1; i <= E.NumPlayers(); i++)
    L.MakeReducedStrats(m_support, E.Players()[i], E.RootNode(), NULL);
  
  gArray<int> dim(E.NumPlayers());
  for (int i = 1; i <= E.NumPlayers(); i++)
    dim[i] = (L.strategies[i].Length()) ? L.strategies[i].Length() : 1;
  
  gPVector<gNumber> regret(dim); 
  
  for (int pl = 1; pl <= E.NumPlayers(); pl++)  {
    gNumber pay = Payoff(pl);
    for (int st = 1; st <= (L.strategies[pl]).Length(); st++) {
      BehavProfile<gNumber> scratch(*m_profile);
      //	gout << "\ninstalled 1:  " << scratch.IsInstalled() << " scratch: " << scratch;
      const gArray<int> *const actions = L.strategies[pl][st];
      for(int j = 1;j<=(*actions).Length();j++) {
	int a = (*actions)[j];
	//	  for (int k = 1;k<=m_support.NumActions(pl,j);k++)
	for (int k = 1;k<=scratch.Support().NumActions(pl,j);k++)
	  scratch(pl,j,k) = (gNumber)0;
	if(a>0)scratch(pl,j,a) = (gNumber)1;
      }
      //	gout << "\ninstalled 2:  " << scratch.IsInstalled() << " scratch: " << scratch;
      gNumber pay2 = scratch.Payoff(pl);
      // use pay - pay instead of zero to get correct precision
      regret(pl,st) = (pay2 < pay) ? pay - pay : pay2 - pay ;
    }
  }
  return regret;
}


const gPVector<gNumber> &BehavSolution::ReducedNormalFormRegret(void) const
{
  CheckIsValid();
  if(!m_rnfRegret.Checked()) 
    m_rnfRegret.Set(GetRNFRegret());
  return m_rnfRegret.Answer();
}

const gNumber BehavSolution::MaxRegret(void) const
{
  return m_profile->MaxRegret();
}

const gNumber BehavSolution::MaxRNFRegret(void) const
{
  gNumber ret = 0;
  const gVector<gNumber> & regret = (gVector<gNumber>)ReducedNormalFormRegret();
  for(int i=regret.First();i<=regret.Last();i++)
    if(regret[i]>=ret)ret = regret[i];

  return ret;
}

//----------
// Output
//----------

void BehavSolution::Dump(gOutput &p_file) const
{
  p_file << *m_profile;
  DumpInfo(p_file);
}

void BehavSolution::DumpInfo(gOutput &p_file) const
{
  p_file << " Creator:" << Creator();
  p_file << " IsNash:" << IsNash();
  p_file << " IsSubgamePerfect:" << IsSubgamePerfect();
  p_file << " IsSequential:" << IsSequential();
  p_file << " LiapValue:" << LiapValue();
  if (Creator() == "Qre[EFG]" || Creator() == "Qre[NFG]") {
    p_file << " QreLambda:" << m_qreLambda;
    p_file << " QreValue:" << m_qreValue;
  }
}

gOutput &operator<<(gOutput &p_file, const BehavSolution &p_solution)
{
  p_solution.Dump(p_file);
  return p_file;
}

SubgamePerfectChecker::SubgamePerfectChecker(const efgGame &E, const BehavProfile<gNumber> &s,
					     const gNumber & epsilon)
  : subgame_number(0), eps(epsilon),  
    isSubgamePerfect(triTRUE), infoset_subgames(E.NumInfosets()), start(s)
{
  MarkedSubgameRoots(E, oldroots);
  gList<Node *> subroots;
  LegalSubgameRoots(E,subroots);
  (start.GetGame()).MarkSubgames(subroots);
  
  for (int pl = 1; pl <= E.NumPlayers(); pl++)   {
    EFPlayer *player = E.Players()[pl];
    for (int iset = 1; iset <= player->NumInfosets(); iset++)  {
      int index;
      
      Infoset *infoset = player->Infosets()[iset];
      Node *member = infoset->Members()[1];
      
      for (index = 1; index <= subroots.Length() &&
	     member->GetSubgameRoot() != subroots[index]; index++);
      
      infoset_subgames(pl, iset) = index;
    }
  }   
}

void SubgamePerfectChecker::SolveSubgame(const efgGame &E,
					 const EFSupport &sup,
					 gList<BehavSolution> &solns,
					 gStatus &p_status)
{
  BehavProfile<gNumber> bp(sup);
  
  subgame_number++;
  
  gArray<int> infosets(infoset_subgames.Lengths());
  
  for (int pl = 1; pl <= E.NumPlayers(); pl++)  {
    int niset = 1;
    for (int iset = 1; iset <= infosets[pl]; iset++)  {
      if (infoset_subgames(pl, iset) == subgame_number)  {
	for (int act = 1; act <= bp.Support().NumActions(pl, niset); act++)
	  bp(pl, niset, act) = start(pl, iset, act);
	niset++;
      }
    }
  }
  //  We need to add function to check if bp is Nash on Subgame.  
  //  gTriState x = IsNashOnSubgame(E,bp,eps);
  // for now, we do the following, which may give wrong answer if player can deviate at
  // multiple isets simultaneously.  :
  gTriState x = triFALSE;
  BehavSolution bs(bp);
  
  if(bs.MaxRNFRegret() <= eps) x = triTRUE;
  
  if(isSubgamePerfect == triTRUE &&  x == triTRUE) 
    isSubgamePerfect = triTRUE;
  else if(isSubgamePerfect == triFALSE ||  x == triFALSE) 
    isSubgamePerfect = triFALSE;
  else 
    isSubgamePerfect = triUNKNOWN;
  
  int index = solns.Append(BehavSolution(bp, "User"));
  solns[index].SetEpsilon(eps);
}

SubgamePerfectChecker::~SubgamePerfectChecker() { 
  (start.GetGame()).UnmarkSubgames((start.GetGame()).RootNode());
  (start.GetGame()).MarkSubgames(oldroots);
}

#include "base/glist.imp"
template class gList<BehavSolution>;