efgensup.cc

Gambit 是一个游戏库理论软件

      if ( sact->ActionIsActive((Action *)c_copy.GetAction()) ) {
	gList<Infoset *> deactivated_infosets;
	sact->RemoveActionReturningDeletedInfosets(c_copy.GetAction(),
						   &deactivated_infosets); 
	if (!c_copy.DeletionsViolateActiveCommitments(sact,
						      &deactivated_infosets))
	  PossibleNashSubsupportsRECURSIVE(s,sact,&c_copy,list,status);

	sact->AddAction(c_copy.GetAction());
      }
    } while (c_copy.GoToNext()) ;
  }
}

gList<const EFSupport> SortSupportsBySize(gList<const EFSupport> &list) 
{
  gArray<int> sizes(list.Length());
  for (int i = 1; i <= list.Length(); i++)
    sizes[i] = list[i].NumDegreesOfFreedom();

  gArray<int> listproxy(list.Length());
  for (int i = 1; i <= list.Length(); i++)
    listproxy[i] = i;

  int maxsize(0);
  for (int i = 1; i <= list.Length(); i++)
    if (sizes[i] > maxsize)
      maxsize = sizes[i];

  int cursor(1);

  for (int j = 0; j < maxsize; j++) {
    int scanner(list.Length());
    while (cursor < scanner)
      if (sizes[scanner] != j)
	scanner--;
      else {
	while (sizes[cursor] == j)
	  cursor++;
	if (cursor < scanner) {
	  int tempindex = listproxy[cursor];
	  listproxy[cursor] = listproxy[scanner];
	  listproxy[scanner] = tempindex;
	  int tempsize = sizes[cursor];
	  sizes[cursor] = sizes[scanner];
	  sizes[scanner] = tempsize;
	  cursor++;
	}
      }
  }

  gList<const EFSupport> answer;
  for (int i = 1; i <= list.Length(); i++)
    answer += list[listproxy[i]];

  return answer;
}
  
gList<const EFSupport> PossibleNashSubsupports(const EFSupport &S,
					       gStatus &status)
{
  gList<const EFSupport> answer;
  EFSupportWithActiveInfo sact(S);
  ActionCursorForSupport cursor(S);

  status.SetProgress(0);
  PossibleNashSubsupportsRECURSIVE(&S,&sact,&cursor,&answer,status);
  status.SetProgress(.5);

  // At this point answer has all consistent subsupports without
  // any strong dominations.  We now edit the list, removing all
  // subsupports that exhibit weak dominations, and we also eliminate
  // subsupports exhibiting domination by currently inactive actions.

  for (int i = answer.Length(); i >= 1; i--) {
    status.SetProgress((2.0-((double)i/(double)answer.Length()))/2.0);
    status.Get();
    EFSupportWithActiveInfo current(answer[i]);
    ActionCursorForSupport crsr(S);
    bool remove = false;
    do {
      const Action *act = crsr.GetAction();
      if (current.ActionIsActive((Action *)act)) 
	for (int j = 1; j <= act->BelongsTo()->NumActions(); j++) {
	  Action *other_act = act->BelongsTo()->GetAction(j);
	  if (other_act != act)
	    if (current.ActionIsActive(other_act)) {
	      if (current.Dominates(other_act,act,false,true) ||
		  current.Dominates(other_act,act,false,false)) 
		remove = true;
	    }
	    else { 
	      current.AddAction(other_act);
	      if (current.HasActiveActionsAtActiveInfosetsAndNoOthers())
		if (current.Dominates(other_act,act,false,true) ||
		    current.Dominates(other_act,act,false,false)) {
		  remove = true;
		}
	      current.RemoveAction(other_act);
	    }
      }
    } while (crsr.GoToNext() && !remove);
    if (remove)
      answer.Remove(i);
  }

  return SortSupportsBySize(answer);
}

//----------------------------------------------------
//                ActionCursorForSupport
// ---------------------------------------------------

ActionCursorForSupport::ActionCursorForSupport(const EFSupport &S)
  : support(&S), pl(1), iset(1), act(1)
{}

ActionCursorForSupport::ActionCursorForSupport(
                  const ActionCursorForSupport &ac)
  : support(ac.support), pl(ac.pl), iset(ac.iset), act(ac.act)
{}

ActionCursorForSupport::~ActionCursorForSupport()
{}

ActionCursorForSupport& 
ActionCursorForSupport::operator=(const ActionCursorForSupport &rhs)
{
  if (this != &rhs) {
    support = rhs.support;
    pl = rhs.pl;
    iset = rhs.iset;
    act = rhs.act;
  }
  return *this;
}

bool 
ActionCursorForSupport::operator==(const ActionCursorForSupport &rhs) const
{
  if (support != rhs.support ||
      pl      != rhs.pl      ||
      iset    != rhs.iset    ||
      act != rhs.act)
    return false;
  return true;
}

bool 
ActionCursorForSupport::operator!=(const ActionCursorForSupport &rhs) const
{
 return (!(*this==rhs));
}

bool
ActionCursorForSupport::GoToNext()
{
  if (act != support->NumActions(pl,iset))
    { act++; return true; }
  
  int temppl(pl);
  int tempiset(iset);
  tempiset ++; 

  while (temppl <= support->GetGame().NumPlayers()) {
    while (tempiset <= support->GetGame().Players()[temppl]->NumInfosets()) {
      if (support->NumActions(temppl,tempiset) > 0) {
	pl = temppl;
	iset = tempiset;
	act = 1;
	return true;
      }
      else
	tempiset++;
    }
    tempiset = 1;
    temppl++;
  }
  return false;
}

const Action *ActionCursorForSupport::GetAction() const
{
  return support->Actions(pl,iset)[act];
}

int ActionCursorForSupport::ActionIndex() const
{
  return act;
}


const Infoset *ActionCursorForSupport::GetInfoset() const
{
  return support->GetGame().Players()[pl]->Infosets()[iset];
}

int ActionCursorForSupport::InfosetIndex() const
{
  return iset;
}

const EFPlayer *ActionCursorForSupport::GetPlayer() const
{
  return support->GetGame().Players()[pl];
}

int ActionCursorForSupport::PlayerIndex() const
{
  return pl;
}

bool 
ActionCursorForSupport::IsLast() const
{
  if (pl == support->GetGame().NumPlayers())
    if (iset == support->GetGame().Players()[pl]->NumInfosets())
      if (act == support->NumActions(pl,iset))
	return true;
  return false;
}

bool 
ActionCursorForSupport::IsSubsequentTo(const Action *a) const
{
  if (pl > a->BelongsTo()->GetPlayer()->GetNumber())
    return true; 
  else if (pl < a->BelongsTo()->GetPlayer()->GetNumber())
    return false;
  else
    if (iset > a->BelongsTo()->GetNumber())
      return true; 
    else if (iset < a->BelongsTo()->GetNumber())
      return false;
    else 
      if (act > a->GetNumber())
	return true;
      else
	return false;
}


bool ActionCursorForSupport::
DeletionsViolateActiveCommitments(const EFSupportWithActiveInfo *S,
				   const gList<Infoset *> *infosetlist)
{
  for (int i = 1; i <= infosetlist->Length(); i++) {
    const Infoset *infoset = (*infosetlist)[i];
    if (infoset->GetPlayer()->GetNumber() < PlayerIndex() ||
	( infoset->GetPlayer()->GetNumber() == PlayerIndex() &&
	  infoset->GetNumber() < InfosetIndex()) )
      if (S->NumActions(infoset) > 0)
	return true;
    if (infoset->GetPlayer()->GetNumber() == PlayerIndex() &&
	infoset->GetNumber() == InfosetIndex() )
      for (int act = 1; act < ActionIndex(); act++)
	if ( S->ActionIsActive(infoset->GetPlayer()->GetNumber(),
			       infoset->GetNumber(),
			       act) )
	  return true;
  }
  return false;
}


bool ActionCursorForSupport::
InfosetGuaranteedActiveByPriorCommitments(const EFSupportWithActiveInfo *S,
					  const Infoset *infoset)
{
  gList<const Node *> members = infoset->ListOfMembers();
  for (int i = 1; i <= members.Length(); i++) {
    const Node* current = members[i];
    if ( current == S->GetGame().RootNode() )
      return true;
    else
      while ( S->ActionIsActive((Action *)current->GetAction()) &&
	      IsSubsequentTo(current->GetAction()) ) {
	current = current->GetParent();
	if ( current == S->GetGame().RootNode() )
	  return true;
      }
  }
  return false;
}