efgcsum.imp

Gambit 是一个游戏库理论软件

//
// $Source: /home/gambit/CVS/gambit/sources/nash/efgcsum.imp,v $
// $Date: 2002/09/10 14:27:39 $
// $Revision: 1.5.2.1 $
//
// DESCRIPTION:
// Implementation of algorithm to solve efgs via linear programming
//
// 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 "efgcsum.h"

//-------------------------------------------------------------------------
//                      efgLp<T>: Member functions
//-------------------------------------------------------------------------

template <class T>
efgLp<T>::efgLp(void)
{ }

template <class T> 
gList<BehavSolution> efgLp<T>::Solve(const EFSupport &p_support,
				     gStatus &p_status)
{
  BFS<T> cbfs((T) 0);
  
  ns1 = p_support.NumSequences(1);
  ns2 = p_support.NumSequences(2);
  ni1 = p_support.GetGame().Players()[1]->NumInfosets()+1;  
  ni2 = p_support.GetGame().Players()[2]->NumInfosets()+1; 
  isets1 = p_support.ReachableInfosets(p_support.GetGame().Players()[1]);
  isets2 = p_support.ReachableInfosets(p_support.GetGame().Players()[2]); 

  if (p_support.GetGame().NumPlayers() != 2 ||
      !p_support.GetGame().IsConstSum() ||
      !IsPerfectRecall(p_support.GetGame())) {
    return gList<BehavSolution>();
  }
  
  List.Flush();
  
  gMatrix<T> A(1,ns1+ni2,1,ns2+ni1);
  gVector<T> b(1,ns1+ni2);
  gVector<T> c(1,ns2+ni1);

  maxpay = p_support.GetGame().MaxPayoff() + gNumber(1);
  minpay = p_support.GetGame().MinPayoff() - gNumber(1);

  A = (T)0;
  T prob = (T)1;
  FillTableau(p_support, A, p_support.GetGame().RootNode(),prob,1,1,0,0);
  A(1,ns2+1) = -(T)1;
  A(ns1+1,1) = (T)1;

  b = (T)0;
  b[ns1+1] = (T)1;

  c = (T)0;
  c[ns2+1] = -(T)1;

  LPSolve<T> LP(A,b,c,ni2,p_status);
  if (!LP.IsAborted()) {
    Add_BFS(LP); 
  }

  gList<BehavSolution> solutions;
  GetSolutions(p_support, solutions);
  return solutions;
}


template <class T> int efgLp<T>::Add_BFS(/*const*/ LPSolve<T> &lp)
{
  BFS<T> cbfs((T) 0);

  // LPSolve<T>::GetAll() does not currently work correctly; for now,
  // LpSolve is restricted to returning only one equilibrium 
  lp.OptBFS(cbfs);
  if (List.Contains(cbfs))  return 0;
  List.Append(cbfs);
  return 1;
}



template <class T> void efgLp<T>::GetProfile(const EFSupport &p_support,
					     gDPVector<T> &v,
					     const BFS<T> &sol,
					     const Node *n,
					     int s1,int s2) const
{
  
  int i,pl,inf,snew;
  T eps = (T)0;
//  eps = tab->Epsilon();
  if(n->GetInfoset()) {
    if(n->GetPlayer()->IsChance()) {
      for(i=1;i<=n->Game()->NumChildren(n);i++)
	GetProfile(p_support,v,sol,n->GetChild(i),s1,s2);
    }
    pl = n->GetPlayer()->GetNumber();
    if(pl==2) {
    inf= isets2.Find(n->GetInfoset());
      snew=1;
      for(i=1;i<inf;i++)
	snew+=p_support.NumActions(isets2[i]); 
      for(i=1;i<=p_support.NumActions(n->GetInfoset());i++) {
	v(pl,inf,i) = (T)0;
	if(sol.IsDefined(s1)) {
	  if(sol(s1)>eps) {
	    if(sol.IsDefined(snew+i)) {
	      if(sol(snew+i)>eps)
		v(pl,inf,i) = sol(snew+i)/sol(s1);
	    }
	  } 
	} 
	GetProfile(p_support,v,sol,n->GetChild(p_support.Actions(n->GetInfoset())[i]->GetNumber()),snew+i,s2);
      }
    }
    if(pl==1) {
    inf= isets1.Find(n->GetInfoset());
      snew=1;
      for(i=1;i<inf;i++)
	snew+=p_support.NumActions(isets1[i]); 
      for(i=1;i<=p_support.NumActions(n->GetInfoset());i++) {
	v(pl,inf,i) = (T)0;
	if(sol.IsDefined(-s2)) {
	  if(sol(-s2)>eps) {
	    if(sol.IsDefined(-(snew+i))) {
	      if(sol(-(snew+i))>eps)
		v(pl,inf,i) = sol(-(snew+i))/sol(-s2);
	    }
	  } 
	} 
	GetProfile(p_support,v,sol,n->GetChild(p_support.Actions(n->GetInfoset())[i]->GetNumber()),s1,snew+i);
      }
    }
  }
}


template <class T>
void efgLp<T>::FillTableau(const EFSupport &p_support,
			   gMatrix<T> &A, const Node *n, T prob,
			   int s1, int s2, int i1, int i2)
{
  int i,snew;
  if (n->Game()->GetOutcome(n)) {
    A(s1,s2) = gNumber(A(s1,s2)) +
      gNumber(prob) * n->Game()->Payoff(n, n->Game()->Players()[1]) - gNumber(minpay);
  }
  if(n->GetInfoset()) {
    if(n->GetPlayer()->IsChance()) {
      for(i=1;i<=n->Game()->NumChildren(n);i++)
	FillTableau(p_support, A, n->GetChild(i),
		    gNumber(prob) * n->Game()->GetChanceProb(n->GetInfoset(), i),
		    s1,s2,i1,i2);
    }
    int pl = n->GetPlayer()->GetNumber();
    if(pl==1) {
      i1=isets1.Find(n->GetInfoset());
      snew=1;
      for(i=1;i<i1;i++)
	snew+=p_support.NumActions(isets1[i]);
      A(s1,ns2+i1+1) = (T) +1;
      for(i=1;i<=p_support.NumActions(n->GetInfoset());i++) {
	A(snew+i,ns2+i1+1) = (T) -1;
	FillTableau(p_support, A, n->GetChild(p_support.Actions(n->GetInfoset())[i]->GetNumber()),prob,snew+i,s2,i1,i2);
      }
    }
    if(pl==2) {
      i2=isets2.Find(n->GetInfoset());
      snew=1;
      for(i=1;i<i2;i++)
	snew+=p_support.NumActions(isets2[i]);
      A(ns1+i2+1,s2) = (T) -1;
      for(i=1;i<=p_support.NumActions(n->GetInfoset());i++) {
	A(ns1+i2+1,snew+i) = (T) +1;
	FillTableau(p_support, A, n->GetChild(p_support.Actions(n->GetInfoset())[i]->GetNumber()),prob,s1,snew+i,i1,i2);
      }
    }
  }
}

template <class T>
void efgLp<T>::GetSolutions(const EFSupport &p_support,
			    gList<BehavSolution> &solutions) const
{
  for (int i = 1; i <= List.Length(); i++)    {
    BehavProfile<T> profile(p_support);
    GetProfile(p_support, profile.GetDPVector(),List[i],p_support.GetGame().RootNode(),1,1);
    solutions.Append(BehavSolution(profile, "Lp[EFG]"));
  }

}