efstrat.cc

Gambit 是一个游戏库理论软件

    const gArray<Action *> &actions = Actions(n->GetInfoset());
    for (int i = 1; i <= actions.Length(); i++) {
      Node *nn = n->GetChild(actions[i]);
      if (nn->IsNonterminal()) {
	answer += nn;
	answer += ReachableNonterminalNodes(nn);
      }
    }
  }
  return answer;
}

gList<Node *> EFSupport::ReachableNonterminalNodes(const Node *n,
						   const Action *a) const
{
  gList<Node *> answer;
  Node *nn = n->GetChild(a);
  if (nn->IsNonterminal()) {
    answer += nn;
    answer += ReachableNonterminalNodes(nn);
  }
  return answer;
}

gList<Infoset *> EFSupport::ReachableInfosets(const EFPlayer *p) const
{ 
  gArray<Infoset *> isets = p->Infosets();
  gList<Infoset *> answer;

  for (int i = isets.First(); i <= isets.Last(); i++)
    if (MayReach(isets[i]))
      answer += isets[i];
  return answer;
}

gList<Infoset *> EFSupport::ReachableInfosets(const Node *n) const
{
  gList<Infoset *> answer;
  gList<Node *> nodelist = ReachableNonterminalNodes(n);
  for (int i = 1; i <= nodelist.Length(); i++)
    answer += nodelist[i]->GetInfoset();
  answer.RemoveRedundancies();
  return answer;
}

gList<Infoset *> EFSupport::ReachableInfosets(const Node *n, 
					      const Action *a) const
{
  gList<Infoset *> answer;
  gList<Node *> nodelist = ReachableNonterminalNodes(n,a);
  for (int i = 1; i <= nodelist.Length(); i++)
    answer += nodelist[i]->GetInfoset();
  answer.RemoveRedundancies();
  return answer;
}

bool EFSupport::AlwaysReaches(const Infoset *i) const
{
  return AlwaysReachesFrom(i, m_efg->RootNode());
}

bool EFSupport::AlwaysReachesFrom(const Infoset *i, const Node *n) const
{
  if (n->IsTerminal()) return false;
  else
    if (n->GetInfoset() == i) return true;
    else {
      gArray<Action *> actions = Actions(n->GetInfoset());
      for (int j = 1; j <= actions.Length(); j++)
	if (!AlwaysReachesFrom(i,n->GetChild(actions[j]))) 
	  return false;
    }
  return true;
}

bool EFSupport::MayReach(const Infoset *i) const
{
  gArray<Node *> members = i->Members();
  for (int j = 1; j <= members.Length(); j++)
    if (MayReach(members[j]))
      return true;
  return false;
}

bool EFSupport::MayReach(const Node *n) const
{
  if (n == m_efg->RootNode())
    return true;
  else {
    if (!ActionIsActive((Action*)n->GetAction()))
      return false;
    else 
      return MayReach(n->GetParent());
  }
}


void EFSupport::Dump(gOutput &p_output) const
{
  p_output << '"' << m_name << "\" { ";
  for (int pl = 1; pl <= m_efg->NumPlayers(); pl++)  {
    EFPlayer &player = m_players[pl]->GetPlayer();
    p_output << '"' << player.GetName() << "\" { ";
    for (int iset = 1; iset <= player.NumInfosets(); iset++)  {
      Infoset *infoset = player.Infosets()[iset];
      p_output << '"' << infoset->GetName() << "\" { ";
      for (int act = 1; act <= NumActions(pl, iset); act++)  {
	const Action *action = m_players[pl]->ActionList(iset)[act];
	p_output << action << ' ';
      }
      p_output << "} ";
    }
    p_output << "} ";
  }
  p_output << "} ";
}

gOutput& operator<<(gOutput&s, const EFSupport& e)
{
  e.Dump(s);
  return s;
}


//----------------------------------------------------
//                EFSupportWithActiveInfo
// ---------------------------------------------------

// Utilities 
bool EFSupportWithActiveInfo::infoset_has_active_nodes(const int pl,
						       const int iset) const
{
  //DEBUG
  /*
  gout << "Got in with pl = " << pl << " and iset = " << iset << ".\n";
  if (InfosetIsActive(pl,iset))
    gout << "Apparently the infoset is active??\n";
  else
    gout << "Somehow it got deactivated.\n";
  */

  for (int i = 1; i <= is_nonterminal_node_active[pl][iset].Length(); i++)
    { //DEBUG
      /*
      gout << "With pl = " << pl << ", iset = " << iset
	   << ", and i = " << i << " the node is supposedly ";
      if (NodeIsActive(pl,iset,i))
	gout << "active.\n";
      else
	gout << "inactive.\n";
      */

    if (is_nonterminal_node_active[pl][iset][i])
      return true;
    }
  return false;
}

bool EFSupportWithActiveInfo::infoset_has_active_nodes(const Infoset *i) const
{
  return infoset_has_active_nodes(i->GetPlayer()->GetNumber(), i->GetNumber());
}

void EFSupportWithActiveInfo::activate(const Node *n)
{
  is_nonterminal_node_active[n->GetPlayer()->GetNumber()]
                            [n->GetInfoset()->GetNumber()]
                            [n->NumberInInfoset()] = true;
}

void EFSupportWithActiveInfo::deactivate(const Node *n)
{
  is_nonterminal_node_active[n->GetPlayer()->GetNumber()]
                            [n->GetInfoset()->GetNumber()]
                            [n->NumberInInfoset()] = false;
}

void EFSupportWithActiveInfo::activate(const Infoset * i)
{
  is_infoset_active[i->GetPlayer()->GetNumber()][i->GetNumber()] = true;
}

void EFSupportWithActiveInfo::deactivate(const Infoset * i)
{
  is_infoset_active[i->GetPlayer()->GetNumber()][i->GetNumber()] = false;
}

void EFSupportWithActiveInfo::activate_this_and_lower_nodes(const Node *n)
{
  if (n->IsNonterminal()) {
    activate(n); 
    activate(n->GetInfoset());
    gArray<Action *> actions(Actions(n->GetInfoset()));
    for (int i = 1; i <= actions.Length(); i++) 
      activate_this_and_lower_nodes(n->GetChild(actions[i]));    
  }
}

void EFSupportWithActiveInfo::deactivate_this_and_lower_nodes(const Node *n)
{
  if (n->IsNonterminal()) {  // THIS ALL LOOKS FISHY
    deactivate(n); 
    if ( !infoset_has_active_nodes(n->GetInfoset()) )
      deactivate(n->GetInfoset());
    gArray<Action *> actions(Actions(n->GetInfoset()));
      for (int i = 1; i <= actions.Length(); i++) 
	deactivate_this_and_lower_nodes(n->GetChild(actions[i]));    
  }
}

void EFSupportWithActiveInfo::
deactivate_this_and_lower_nodes_returning_deactivated_infosets(const Node *n, 
                                                gList<Infoset *> *list)
{
  if (n->IsNonterminal()) {
    deactivate(n); 
    if ( !infoset_has_active_nodes(n->GetInfoset()) ) {

      //DEBUG
      /*
      gout << "We are deactivating infoset " << n->GetInfoset()->GetNumber()
	   << " with support \n" << *this << "\n";
      */

      (*list) += n->GetInfoset(); 
      deactivate(n->GetInfoset());
    }
    gArray<Action *> actions(Actions(n->GetInfoset()));
      for (int i = 1; i <= actions.Length(); i++) 
	deactivate_this_and_lower_nodes_returning_deactivated_infosets(
			     n->GetChild(actions[i]),list);    
  }
}

void EFSupportWithActiveInfo::InitializeActiveListsToAllActive()
{
  for (int pl = 0; pl <= GetGame().NumPlayers(); pl++) {
    EFPlayer *player = (pl == 0) ? GetGame().GetChance() : GetGame().Players()[pl]; 
    gList<bool>         is_players_infoset_active;
    gList<gList<bool> > is_players_node_active;
    for (int iset = 1; iset <= player->NumInfosets(); iset++) {
      is_players_infoset_active += true;

      gList<bool> is_infosets_node_active;
      for (int n = 1; n <= player->Infosets()[iset]->NumMembers(); n++)
	is_infosets_node_active += true;
      is_players_node_active += is_infosets_node_active;
    }
    is_infoset_active[pl] = is_players_infoset_active;
    is_nonterminal_node_active[pl] = is_players_node_active;
  }
}

void EFSupportWithActiveInfo::InitializeActiveListsToAllInactive()
{
  for (int pl = 0; pl <= GetGame().NumPlayers(); pl++) {
    EFPlayer *player = (pl == 0) ? GetGame().GetChance() : GetGame().Players()[pl];
    gList<bool>         is_players_infoset_active;
    gList<gList<bool> > is_players_node_active;

    for (int iset = 1; iset <= player->NumInfosets(); iset++) {
      is_players_infoset_active += false;

      gList<bool> is_infosets_node_active;
      for (int n = 1; n <= player->Infosets()[iset]->NumMembers()
; n++)
	is_infosets_node_active += false;
      is_players_node_active += is_infosets_node_active;
    }
    is_infoset_active[pl] = is_players_infoset_active;
    is_nonterminal_node_active[pl] = is_players_node_active;
  }
}

void EFSupportWithActiveInfo::InitializeActiveLists()
{
  InitializeActiveListsToAllInactive();

  activate_this_and_lower_nodes(GetGame().RootNode());
}

// Constructors and Destructor
EFSupportWithActiveInfo::EFSupportWithActiveInfo(const efgGame &E) 
  : EFSupport(E), 
    is_infoset_active(0,E.NumPlayers()), 
    is_nonterminal_node_active(0,E.NumPlayers())
{
  InitializeActiveLists();
}

EFSupportWithActiveInfo::EFSupportWithActiveInfo(const EFSupport& given)
  : EFSupport(given), 
    is_infoset_active(0,given.GetGame().NumPlayers()), 
    is_nonterminal_node_active(0,given.GetGame().NumPlayers())
{
  InitializeActiveLists();
}

EFSupportWithActiveInfo::EFSupportWithActiveInfo(
				  const EFSupportWithActiveInfo& given)
  : EFSupport(given.UnderlyingSupport()), 
    //is_infoset_active(0,given.GetGame().NumPlayers()), 
        is_infoset_active(is_infoset_active), 
    is_nonterminal_node_active(given.is_nonterminal_node_active)
{
  //  InitializeActiveLists();
}

EFSupportWithActiveInfo::~EFSupportWithActiveInfo()
{}

// Operators
EFSupportWithActiveInfo &
EFSupportWithActiveInfo::operator=(const EFSupportWithActiveInfo &s)
{
  if (this != &s) {
    ((EFSupport&) *this) = s;
    is_infoset_active = s.is_infoset_active;
    is_nonterminal_node_active = s.is_nonterminal_node_active;
  }
  return *this;
}

bool 
EFSupportWithActiveInfo::operator==(const EFSupportWithActiveInfo &s) const
{
  if ((EFSupport&) *this != (EFSupport&) s) {
    //  gout << "Underlying supports differ.\n"; 
    return false; 
  }
  
  if (is_infoset_active != s.is_infoset_active) {
    //    gout<< "Active infosets differ:\n"; 
   
    //  for(int i = 0; i < is_infoset_active.Length(); i++)
    //  gout << "is_infoset_active[" << i << "] = " << is_infoset_active[i];

    //for(int i = 0; i < s.is_infoset_active.Length(); i++)
    //  gout << "s.is_infoset_active[" << i << "] = " << s.is_infoset_active[i];

    return false;
  }
  if (is_nonterminal_node_active != s.is_nonterminal_node_active) {
    // gout << "Active nodes differ.\n";
    return false;
  }
  return true;
}

bool 
EFSupportWithActiveInfo::operator!=(const EFSupportWithActiveInfo &s) const
{
  return !(*this == s);
}

// Member Function
const gList<const Node *> 
EFSupportWithActiveInfo::ReachableNodesInInfoset(const Infoset * i) const
{
  gList<const Node *> answer;
  int pl = i->GetPlayer()->GetNumber();
  int iset = i->GetNumber();
  for (int j = 1; j <= i->NumMembers(); j++)
    if (is_nonterminal_node_active[pl][iset][j])
      answer += i->GetMember(j);
  return answer;
}

const gList<const Node *>
EFSupportWithActiveInfo::ReachableNonterminalNodes() const
{
  gList<const Node *> answer;
  for (int pl = 1; pl <= GetGame().NumPlayers(); pl++) {
    const EFPlayer *p = GetGame().Players()[pl];
    for (int iset = 1; iset <= p->NumInfosets(); iset++)
      answer += ReachableNodesInInfoset(p->GetInfoset(iset));
  }
  return answer;
}

// Editing functions
void EFSupportWithActiveInfo::AddAction(const Action *s)
{
  EFSupport::AddAction(s);

  gList<const Node *> startlist(ReachableNodesInInfoset(s->BelongsTo()));
  for (int i = 1; i <= startlist.Length(); i++)
    activate_this_and_lower_nodes(startlist[i]);
}

bool EFSupportWithActiveInfo::RemoveAction(const Action *s)
{

  gList<const Node *> startlist(ReachableNodesInInfoset(s->BelongsTo()));
  for (int i = 1; i <= startlist.Length(); i++)
    deactivate_this_and_lower_nodes(startlist[i]->GetChild(s));

  // the following returns false if s was not active
  return EFSupport::RemoveAction(s);
}

bool 
EFSupportWithActiveInfo::RemoveActionReturningDeletedInfosets(const Action *s,
					   gList<Infoset *> *list)
{

  gList<const Node *> startlist(ReachableNodesInInfoset(s->BelongsTo()));
  for (int i = 1; i <= startlist.Length(); i++)
    deactivate_this_and_lower_nodes_returning_deactivated_infosets(
                           startlist[i]->GetChild(s),list);

  // the following returns false if s was not active
  return EFSupport::RemoveAction(s);
}

int EFSupportWithActiveInfo::NumActiveNodes(const int pl,
					     const int iset) const
{
  int answer = 0;
  for (int i = 1; i <= is_nonterminal_node_active[pl][iset].Length(); i++)
    if (is_nonterminal_node_active[pl][iset][i])
      answer++;
  return answer;
}

int EFSupportWithActiveInfo::NumActiveNodes(const Infoset *i) const
{
  return NumActiveNodes(i->GetPlayer()->GetNumber(),i->GetNumber());
}

bool EFSupportWithActiveInfo::InfosetIsActive(const int pl,
					      const int iset) const
{
  return is_infoset_active[pl][iset];
}

bool EFSupportWithActiveInfo::InfosetIsActive(const Infoset *i) const
{
  return InfosetIsActive(i->GetPlayer()->GetNumber(),i->GetNumber());
}

bool EFSupportWithActiveInfo::NodeIsActive(const int pl,
					   const int iset,
					   const int node) const
{
  return is_nonterminal_node_active[pl][iset][node];
}

bool EFSupportWithActiveInfo::NodeIsActive(const Node *n) const
{
  return NodeIsActive(n->GetInfoset()->GetPlayer()->GetNumber(),
		      n->GetInfoset()->GetNumber(),
		      n->NumberInInfoset());
}

bool EFSupportWithActiveInfo::HasActiveActionsAtActiveInfosets()
{
  for (int pl = 1; pl <= GetGame().NumPlayers(); pl++)
    for (int iset = 1; iset <= GetGame().Players()[pl]->NumInfosets(); iset++) 
      if (InfosetIsActive(pl,iset))
        if ( NumActions(GetGame().Players()[pl]->Infosets()[iset]) == 0 )
          return false;
  return true;
}

bool EFSupportWithActiveInfo::HasActiveActionsAtActiveInfosetsAndNoOthers()
{
  for (int pl = 1; pl <= GetGame().NumPlayers(); pl++)
    for (int iset = 1; iset <= GetGame().Players()[pl]->NumInfosets(); iset++) {
      if (InfosetIsActive(pl,iset))
        if ( NumActions(GetGame().Players()[pl]->Infosets()[iset]) == 0 )
          return false;
      if (!InfosetIsActive(pl,iset))
        if ( NumActions(GetGame().Players()[pl]->Infosets()[iset]) > 0 )
          return false;
      }
  return true;
}


void EFSupportWithActiveInfo::Dump(gOutput& s) const
{
  EFSupport::Dump(s);

  /*
  s << "\n";

  for (int pl = 0; pl <= GetGame().NumPlayers(); pl++) {
  
    if (pl == 0)
      s << " Chance:  ";
    else 
      s << "Player " << pl << ":";
    //    s << "(" << GetGame().Players()[pl]->NumInfosets() << ")";
    //    s << "\n";

    for (int iset = 1; iset <= GetGame().Players()[pl]->NumInfosets(); iset++) { 

      s << "  Infoset " << iset << " is ";
      if (InfosetIsActive(pl,iset))
	s << "Active  : ";
      else
	s << "inactive: ";
      
      s << "{";
      for (int n = 1; n <= GetGame().NumNodesInInfoset(pl,iset); n++) {
	if (NodeIsActive(pl,iset,n))
	  s << "+";
	else
	  s << "0";
	if (n < GetGame().NumNodesInInfoset(pl,iset))
	  s << ",";
      }
      s << "}";

      //      s << "\n";
    }
    s << "\n ";
  }
  //    s << "\n\n";
  */
}

gOutput& operator<<(gOutput&s, const EFSupportWithActiveInfo& e)
{
  e.Dump(s);
  return s;
}


// Instantiations
template class gList<EFSupport>;
template class gList<const EFSupport>;
template class gList<const EFSupportWithActiveInfo>;