efg.cc

Gambit 是一个游戏库理论软件

    p_file << "EFG 2 R";
    p_file << " \"" << EscapeQuotes(title) << "\" { ";
    for (int i = 1; i <= players.Length(); i++)
      p_file << '"' << EscapeQuotes(players[i]->name) << "\" ";
    p_file << "}\n";
    p_file << "\"" << EscapeQuotes(comment) << "\"\n\n";

    WriteEfgFile(p_file, root);
    p_file.SetPrec(oldPrecision);
    m_revision++;
    m_dirty = false;
  }
  catch (...) {
    p_file.SetPrec(oldPrecision);
    throw;
  }
}


//------------------------------------------------------------------------
//                    Efg: General data access
//------------------------------------------------------------------------

int efgGame::NumPlayers(void) const
{ return players.Length(); }

EFPlayer *efgGame::NewPlayer(void)
{
  m_revision++;
  m_dirty = true;

  EFPlayer *ret = new EFPlayer(this, players.Length() + 1);
  players.Append(ret);

  for (int outc = 1; outc <= outcomes.Last();
       outcomes[outc++]->m_payoffs.Append(0));
  for (int outc = 1; outc <= outcomes.Last();
       outcomes[outc++]->m_doublePayoffs.Append(0));
  DeleteLexicon();
  return ret;
}

gBlock<Infoset *> efgGame::Infosets() const
{
  gBlock<Infoset *> answer;

  gArray<EFPlayer *> p = Players();
  int i;
  for (i = 1; i <= p.Length(); i++) {
    gArray<Infoset *> infosets_for_player = p[i]->Infosets();
    int j;
    for (j = 1; j <= infosets_for_player.Length(); j++)
      answer += infosets_for_player[j];
  }

  return answer;
}

int efgGame::NumOutcomes(void) const
{ return outcomes.Last(); }

efgOutcome *efgGame::NewOutcome(void)
{
  m_revision++;
  m_dirty = true;
  return NewOutcome(outcomes.Last() + 1);
}

void efgGame::DeleteOutcome(efgOutcome *p_outcome)
{
  m_revision++;
  m_dirty = true;

  root->DeleteOutcome(p_outcome);
  delete outcomes.Remove(outcomes.Find(p_outcome));
  DeleteLexicon();
}

efgOutcome *efgGame::GetOutcome(int p_index) const
{
  return outcomes[p_index];
}

void efgGame::SetOutcomeName(efgOutcome *p_outcome, const gText &p_name)
{
  p_outcome->m_name = p_name;
}

const gText &efgGame::GetOutcomeName(efgOutcome *p_outcome) const
{
  return p_outcome->m_name;
}

efgOutcome *efgGame::GetOutcome(const Node *p_node) const
{
  return p_node->outcome;
}

void efgGame::SetOutcome(Node *p_node, efgOutcome *p_outcome)
{
  p_node->outcome = p_outcome;
}

void efgGame::SetPayoff(efgOutcome *p_outcome, int pl, 
			const gNumber &value)
{
  if (!p_outcome) {
    return;
  }

  m_revision++;
  m_dirty = true;
  p_outcome->m_payoffs[pl] = value;
  p_outcome->m_doublePayoffs[pl] = (double) value;
}

gNumber efgGame::Payoff(efgOutcome *p_outcome,
			const EFPlayer *p_player) const
{
  if (!p_outcome) {
    return gNumber(0);
  }

  return p_outcome->m_payoffs[p_player->number];
}

gNumber efgGame::Payoff(const Node *p_node, const EFPlayer *p_player) const
{
  return (p_node->outcome) ? p_node->outcome->m_payoffs[p_player->number] : gNumber(0);
}

gArray<gNumber> efgGame::Payoff(efgOutcome *p_outcome) const
{
  if (!p_outcome) {
    gArray<gNumber> ret(players.Length());
    for (int i = 1; i <= ret.Length(); ret[i++] = 0);
    return ret;
  }
  else {
    return p_outcome->m_payoffs;
  }
}

bool efgGame::IsConstSum(void) const
{
  int pl, index;
  gNumber cvalue = (gNumber) 0;

  if (outcomes.Last() == 0)  return true;

  for (pl = 1; pl <= players.Length(); pl++)
    cvalue += outcomes[1]->m_payoffs[pl];

  for (index = 2; index <= outcomes.Last(); index++)  {
    gNumber thisvalue(0);

    for (pl = 1; pl <= players.Length(); pl++)
      thisvalue += outcomes[index]->m_payoffs[pl];

    if (thisvalue > cvalue || thisvalue < cvalue)
      return false;
  }

  return true;
}

gNumber efgGame::MinPayoff(int pl) const
{
  int index, p, p1, p2;
  gNumber minpay;

  if (NumOutcomes() == 0)  return 0;

  if(pl) { p1=p2=pl;}
  else {p1=1;p2=players.Length();}

  minpay = outcomes[1]->m_payoffs[p1];

  for (index = 1; index <= outcomes.Last(); index++)  {
    for (p = p1; p <= p2; p++)
      if (outcomes[index]->m_payoffs[p] < minpay)
	minpay = outcomes[index]->m_payoffs[p];
  }
  return minpay;
}

gNumber efgGame::MaxPayoff(int pl) const
{
  int index, p, p1, p2;
  gNumber maxpay;

  if (NumOutcomes() == 0)  return 0;

  if(pl) { p1=p2=pl;}
  else {p1=1;p2=players.Length();}

  maxpay = outcomes[1]->m_payoffs[p1];

  for (index = 1; index <= outcomes.Last(); index++)  {
    for (p = p1; p <= p2; p++)
      if (outcomes[index]->m_payoffs[p] > maxpay)
	maxpay = outcomes[index]->m_payoffs[p];
  }
  return maxpay;
}

Node *efgGame::RootNode(void) const
{ return root; }

bool efgGame::IsSuccessor(const Node *n, const Node *from) const
{ return IsPredecessor(from, n); }

bool efgGame::IsPredecessor(const Node *n, const Node *of) const
{
  while (of && n != of)    of = of->parent;

  return (n == of);
}

gArray<int> efgGame::PathToNode(const Node *p_node) const
{
  gBlock<int> ret;
  const Node *n = p_node;
  while (n->GetParent()) {
    ret.Insert(p_node->GetAction()->GetNumber(), 1);
    n = n->GetParent();
  }
  return ret;
}

void efgGame::DescendantNodes(const Node* n, 
			      const EFSupport& supp,
			      gList<Node *> &current) const
{
  current += const_cast<Node *>(n);
  if (n->IsNonterminal()) {
    const gArray<Action *> actions = supp.Actions(n->GetInfoset());
    for (int i = 1; i <= actions.Length(); i++) {
      const Node* newn = n->GetChild(actions[i]);
      DescendantNodes(newn,supp,current);
    }
  }
}

void efgGame::NonterminalDescendants(const Node* n, 
					  const EFSupport& supp,
					  gList<const Node*>& current) const
{
  if (n->IsNonterminal()) {
    current += n;
    const gArray<Action *> actions = supp.Actions(n->GetInfoset());
    for (int i = 1; i <= actions.Length(); i++) {
      const Node* newn = n->GetChild(actions[i]);
      NonterminalDescendants(newn,supp,current);
    }
  }
}

void efgGame::TerminalDescendants(const Node* n, 
				  const EFSupport& supp,
				  gList<Node *> &current) const
{
  if (n->IsTerminal()) { 
    // casting away const to silence compiler warning
    current += (Node *) n;
  }
  else {
    const gArray<Action *> actions = supp.Actions(n->GetInfoset());
    for (int i = 1; i <= actions.Length(); i++) {
      const Node* newn = n->GetChild(actions[i]);
      TerminalDescendants(newn,supp,current);
    }
  }
}

gList<Node *>
efgGame::DescendantNodes(const Node &p_node, const EFSupport &p_support) const
{
  gList<Node *> answer;
  DescendantNodes(&p_node, p_support, answer);
  return answer;
}

gList<const Node*> 
efgGame::NonterminalDescendants(const Node& n, const EFSupport& supp) const
{
  gList<const Node*> answer;
  NonterminalDescendants(&n,supp,answer);
  return answer;
}

gList<Node *> 
efgGame::TerminalDescendants(const Node& n, const EFSupport& supp) const
{
  gList<Node *> answer;
  TerminalDescendants(&n,supp,answer);
  return answer;
}

gList<Node *> efgGame::TerminalNodes() const
{
  return TerminalDescendants(*(RootNode()),EFSupport(*this));
}

gList<Infoset*> efgGame::DescendantInfosets(const Node& n, 
					const EFSupport& supp) const
{
  gList<Infoset*> answer;
  gList<const Node*> nodelist = NonterminalDescendants(n,supp);
  int i;
  for (i = 1; i <= nodelist.Length(); i++) {
      Infoset* iset = nodelist[i]->GetInfoset();
      if (!answer.Contains(iset))
	answer += iset;
  }
  return answer;
}

const gArray<Node *> &efgGame::Children(const Node *n) const
{ return n->children; }

int efgGame::NumChildren(const Node *n) const
{ return n->children.Length(); }

efgOutcome *efgGame::NewOutcome(int index)
{
  m_revision++;
  m_dirty = true;
  outcomes.Append(new efgOutcome(this, index));
  return outcomes[outcomes.Last()];
} 

//------------------------------------------------------------------------
//                     Efg: Operations on players
//------------------------------------------------------------------------

EFPlayer *efgGame::GetChance(void) const
{
  return chance;
}

Infoset *efgGame::AppendNode(Node *n, EFPlayer *p, int count)
{
  if (!n || !p || count == 0)
    throw Exception();

  m_revision++;
  m_dirty = true;

  if (n->children.Length() == 0)   {
    n->infoset = CreateInfoset(p->infosets.Length() + 1, p, count);
    n->infoset->members.Append(n);
    while (count--)
      n->children.Append(new Node(this, n));
  }

  DeleteLexicon();
  SortInfosets();
  return n->infoset;
}  

Infoset *efgGame::AppendNode(Node *n, Infoset *s)
{
  if (!n || !s)   throw Exception();
  
  // Can't bridge subgames...
  if (s->members.Length() > 0 && n->gameroot != s->members[1]->gameroot)
    return 0;

  if (n->children.Length() == 0)   {
    m_revision++;
    m_dirty = true;
    n->infoset = s;
    s->members.Append(n);
    for (int i = 1; i <= s->actions.Length(); i++)
      n->children.Append(new Node(this, n));
  }

  DeleteLexicon();
  SortInfosets();
  return s;
}
  
Node *efgGame::DeleteNode(Node *n, Node *keep)
{
  if (!n || !keep)   throw Exception();

  if (keep->parent != n)   return n;

  if (n->gameroot == n)
    MarkSubgame(keep, keep);

  m_revision++;
  m_dirty = true;
  // turn infoset sorting off during tree deletion -- problems will occur
  sortisets = false;

  n->children.Remove(n->children.Find(keep));
  DeleteTree(n);
  keep->parent = n->parent;
  if (n->parent)
    n->parent->children[n->parent->children.Find(n)] = keep;
  else
    root = keep;

  delete n;
  DeleteLexicon();

  sortisets = true;

  SortInfosets();
  return keep;
}

Infoset *efgGame::InsertNode(Node *n, EFPlayer *p, int count)
{
  if (!n || !p || count <= 0)  throw Exception();

  m_revision++;
  m_dirty = true;

  Node *m = new Node(this, n->parent);
  m->infoset = CreateInfoset(p->infosets.Length() + 1, p, count);
  m->infoset->members.Append(m);
  if (n->parent)
    n->parent->children[n->parent->children.Find(n)] = m;
  else
    root = m;
  m->children.Append(n);
  n->parent = m;
  while (--count)
    m->children.Append(new Node(this, m));

  DeleteLexicon();
  SortInfosets();
  return m->infoset;
}

Infoset *efgGame::InsertNode(Node *n, Infoset *s)
{
  if (!n || !s)  throw Exception();

  // can't bridge subgames
  if (s->members.Length() > 0 && n->gameroot != s->members[1]->gameroot)
    return 0;
  
  m_revision++;
  m_dirty = true;

  Node *m = new Node(this, n->parent);
  m->infoset = s;
  s->members.Append(m);
  if (n->parent)
    n->parent->children[n->parent->children.Find(n)] = m;
  else
    root = m;
  m->children.Append(n);
  n->parent = m;
  int count = s->actions.Length();
  while (--count)
    m->children.Append(new Node(this, m));

  DeleteLexicon();
  SortInfosets();
  return m->infoset;
}

Infoset *efgGame::CreateInfoset(EFPlayer *p, int br)
{
  if (!p || p->Game() != this)  throw Exception();
  m_revision++;
  m_dirty = true;
  return CreateInfoset(p->infosets.Length() + 1, p, br);
}

Infoset *efgGame::JoinInfoset(Infoset *s, Node *n)
{
  if (!n || !s)  throw Exception();

  // can't bridge subgames
  if (s->members.Length() > 0 && n->gameroot != s->members[1]->gameroot)
    return 0;
  
  if (!n->infoset)   return 0; 
  if (n->infoset == s)   return s;
  if (s->actions.Length() != n->children.Length())  return n->infoset;

  m_revision++;
  m_dirty = true;

  Infoset *t = n->infoset;

  t->members.Remove(t->members.Find(n));
  s->members.Append(n);

  n->infoset = s;

  DeleteLexicon();
  SortInfosets();
  return s;
}

Infoset *efgGame::LeaveInfoset(Node *n)
{
  if (!n)  throw Exception();

  if (!n->infoset)   return 0;

  Infoset *s = n->infoset;
  if (s->members.Length() == 1)   return s;

  m_revision++;
  m_dirty = true;

  EFPlayer *p = s->player;
  s->members.Remove(s->members.Find(n));
  n->infoset = CreateInfoset(p->infosets.Length() + 1, p,
			     n->children.Length());
  n->infoset->name = s->name;
  n->infoset->members.Append(n);
  for (int i = 1; i <= s->actions.Length(); i++)
    n->infoset->actions[i]->name = s->actions[i]->name;

  DeleteLexicon();
  SortInfosets();
  return n->infoset;
}

Infoset *efgGame::SplitInfoset(Node *n)
{
  if (!n)  throw Exception();

  if (!n->infoset)   return 0;

  Infoset *s = n->infoset;
  if (s->members.Length() == 1)   return s;

  m_revision++;
  m_dirty = true;

  EFPlayer *p = s->player;
  Infoset *ns = CreateInfoset(p->infosets.Length() + 1, p,
			      n->children.Length());
  ns->name = s->name;
  int i;
  for (i = s->members.Length(); i > s->members.Find(n); i--)   {
    Node *nn = s->members.Remove(i);
    ns->members.Append(nn);
    nn->infoset = ns;
  }
  for (i = 1; i <= s->actions.Length(); i++) {
    ns->actions[i]->name = s->actions[i]->name;
    if (p == chance) {
      SetChanceProb(ns, i, GetChanceProb(s, i));
    }
  }
  DeleteLexicon();
  SortInfosets();
  return n->infoset;
}

Infoset *efgGame::MergeInfoset(Infoset *to, Infoset *from)
{
  if (!to || !from)  throw Exception();

  if (to == from ||
      to->actions.Length() != from->actions.Length())   return from;

  if (to->members[1]->gameroot != from->members[1]->gameroot) 
    return from;

  m_revision++;
  m_dirty = true;

  to->members += from->members;
  for (int i = 1; i <= from->members.Length(); i++)
    from->members[i]->infoset = to;

  from->members.Flush();

  DeleteLexicon();
  SortInfosets();
  return to;
}