seqform.imp

Gambit 是一个游戏库理论软件

//
// $Source: /home/gambit/CVS/gambit/sources/nash/seqform.imp,v $
// $Date: 2002/09/10 14:27:44 $
// $Revision: 1.5.2.1 $
//
// DESCRIPTION:
// Implementation of algorithm to solve extensive forms using linear
// complementarity program from sequence form
//
// 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 "base/base.h"
#include "seqform.h"
#include "lhtab.h"

//---------------------------------------------------------------------------
//                        efgLcp: member functions
//---------------------------------------------------------------------------

template <class T>
efgLcp<T>::efgLcp(void)
  : m_stopAfter(1), m_maxDepth(0)
{ } 

template <class T> efgLcp<T>::~efgLcp()
{ }

//
// Lemke implements the Lemke's algorithm (as refined by Eaves 
// for degenerate problems) for  Linear Complementarity
// problems, starting from the primary ray.  
//

template <class T> 
gList<BehavSolution> efgLcp<T>::Solve(const EFSupport &p_support,
				      gStatus &p_status)
{
  BFS<T> cbfs((T) 0);
  int i, j;
  
  if (p_support.GetGame().NumPlayers() != 2) {
    return gList<BehavSolution>();
  }
  
  isets1 = p_support.ReachableInfosets(p_support.GetGame().Players()[1]);
  isets2 = p_support.ReachableInfosets(p_support.GetGame().Players()[2]); 

  List.Flush();

  int ntot;
  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;

  ntot = ns1+ns2+ni1+ni2;

  gMatrix<T> A(1,ntot,0,ntot);
  gVector<T> b(1,ntot);

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

  T prob = (T)1;
  for (i = A.MinRow(); i <= A.MaxRow(); i++) {
    b[i] = (T) 0;
    for (j = A.MinCol(); j <= A.MaxCol(); j++) {
      A(i,j) = (T) 0; 
    }
  }

  FillTableau(p_support, A, p_support.GetGame().RootNode(), prob, 1, 1, 0, 0);
  for (i = A.MinRow(); i <= A.MaxRow(); i++) { 
    A(i,0) = -(T) 1;
  }
  A(1,ns1+ns2+1) = (T)1;
  A(ns1+ns2+1,1) = -(T)1;
  A(ns1+1,ns1+ns2+ni1+1) = (T)1;
  A(ns1+ns2+ni1+1,ns1+1) = -(T)1;
  b[ns1+ns2+1] = -(T)1;
  b[ns1+ns2+ni1+1] = -(T)1;

  LTableau<T> tab(A,b);
  eps = tab.Epsilon();
  
  BehavProfile<T> profile(p_support);
  gVector<T> sol(tab.MinRow(),tab.MaxRow());
    
  gList<BehavSolution> solutions;

  if (m_stopAfter != 1) {
    All_Lemke(p_support, ns1+ns2+1, tab, 0, A, solutions, p_status);
  }
  else {
    tab.Pivot(ns1+ns2+1,0);
    tab.SF_LCPPath(ns1+ns2+1, p_status);

    Add_BFS(tab);
    tab.BasisVector(sol);
    GetProfile(p_support, tab, profile.GetDPVector(),sol,p_support.GetGame().RootNode(),1,1);
    solutions.Append(BehavSolution(profile, "Lcp[EFG]"));
  }

  return solutions;
}

template <class T> int efgLcp<T>::Add_BFS(const LTableau<T> &tableau)
{
  BFS<T> cbfs((T) 0);
  gVector<T> v(tableau.MinRow(), tableau.MaxRow());
  tableau.BasisVector(v);

  for (int i = tableau.MinCol(); i <= tableau.MaxCol(); i++)
    if (tableau.Member(i)) {
      cbfs.Define(i, v[tableau.Find(i)]);
    }

  if (List.Contains(cbfs))  return 0;
  List.Append(cbfs);
  return 1;
}

//
// All_Lemke finds all accessible Nash equilibria by recursively 
// calling itself.  List maintains the list of basic variables 
// for the equilibria that have already been found.  
// From each new accessible equilibrium, it follows
// all possible paths, adding any new equilibria to the List.  
//
template <class T> int 
efgLcp<T>::All_Lemke(const EFSupport &p_support,
		     int j, LTableau<T> &B, int depth,
		     gMatrix<T> &A, gList<BehavSolution> &p_solutions,
		     gStatus &p_status)
{
  if (m_maxDepth != 0 && depth > m_maxDepth) {
    return 1;
  }

  int i,len,newsol,missing;
  T p1,p2,aa;
  T small_num = (T)1/(T)1000;

  gVector<T> sol(B.MinRow(),B.MaxRow());
  BehavProfile<T> profile(p_support);

  newsol =0;
  for (i = B.MinRow(); 
       i <= B.MaxRow()  && newsol == 0 &&
       (m_stopAfter == 0 || p_solutions.Length() < m_stopAfter);
       i++) {
    p_status.Get();
    
    if (i != j)  {
      len=List.Length();  
      p1=(double)len/(double)(len+1);
      p2=(double)(len+1)/(double)(len+2);
      int num_strats = B.MaxCol()-B.MinCol()-1;
      aa=(double)(i)/(double)num_strats;
      p_status.SetProgress(p1+aa*(p2-p1));
      
      LTableau<T> BCopy(B);
      A(i,0)=-small_num;
      BCopy.Refactor();

      if(depth==0) {
	BCopy.Pivot(j,0);
	missing = -j;
      }
      else
	missing = BCopy.SF_PivotIn(0);

      assert(missing);
      newsol=0;

      if(BCopy.SF_LCPPath(-missing,p_status)==1) {
	newsol = Add_BFS(BCopy);
	BCopy.BasisVector(sol);
	GetProfile(p_support, BCopy, profile.GetDPVector(),sol,p_support.GetGame().RootNode(),1,1);
	if(newsol) {
	  p_solutions.Append(BehavSolution(profile, "Lcp[EFG]")); 
	}
      }
      else {
	// gout << ": Dead End";
      }
      
      A(i,0)=-(T)1;
      if(newsol) {
	BCopy.Refactor();
	All_Lemke(p_support,i,BCopy,depth+1, A, p_solutions, p_status);
      }
    }
  }
  
  return 1;
}

template <class T>
void efgLcp<T>::FillTableau(const EFSupport &p_support, gMatrix<T> &A,
				   const Node *n, T prob,
				   int s1, int s2, int i1, int i2)
{
  int snew;
  if (p_support.GetGame().GetOutcome(n)) {
    A(s1,ns1+s2) = gNumber(A(s1,ns1+s2)) +
      gNumber(prob) * (p_support.GetGame().Payoff(n, p_support.GetGame().Players()[1]) - gNumber(maxpay));
    A(ns1+s2,s1) = gNumber(A(ns1+s2,s1)) +
      gNumber(prob) * (p_support.GetGame().Payoff(n, p_support.GetGame().Players()[2]) - gNumber(maxpay));
  }
  if (n->GetInfoset()) {
    if (n->GetPlayer()->IsChance()) {
      for (int i = 1; i <= p_support.GetGame().NumChildren(n); i++) {
	FillTableau(p_support, A, n->GetChild(i),
		    gNumber(prob) * p_support.GetGame().GetChanceProb(n->GetInfoset(), i),
		    s1,s2,i1,i2);
      }
    }
    int pl = n->GetPlayer()->GetNumber();
    if (pl==1) {
      i1=isets1.Find(n->GetInfoset());
      snew=1;
      for (int i = 1; i < i1; i++) {
	snew+=p_support.NumActions(isets1[i]);
      }
      A(s1,ns1+ns2+i1+1) = -(T)1;
      A(ns1+ns2+i1+1,s1) = (T)1;
      for (int i = 1; i <= p_support.NumActions(n->GetInfoset()); i++) {
	A(snew+i,ns1+ns2+i1+1) = (T)1;
	A(ns1+ns2+i1+1,snew+i) = -(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 (int i = 1; i < i2; i++) {
	snew+=p_support.NumActions(isets2[i]);
      }
      A(ns1+s2,ns1+ns2+ni1+i2+1) = -(T)1;
      A(ns1+ns2+ni1+i2+1,ns1+s2) = (T)1;
      for (int i = 1; i <= p_support.NumActions(n->GetInfoset()); i++) {
	A(ns1+snew+i,ns1+ns2+ni1+i2+1) = (T)1;
	A(ns1+ns2+ni1+i2+1,ns1+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 efgLcp<T>::GetProfile(const EFSupport &p_support,
				  const LTableau<T> &tab, 
				  gDPVector<T> &v, const gVector<T> &sol,
				  const Node *n, int s1,int s2)
{
  int i,pl,inf,snew,ind,ind2;
  if(n->GetInfoset()) {
    if(n->GetPlayer()->IsChance()) {
      for (i = 1; i <= p_support.GetGame().NumChildren(n);i++)
	GetProfile(p_support, tab, v,sol,n->GetChild(i),s1,s2);
    }
    pl = n->GetPlayer()->GetNumber();
    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(tab.Member(s1)) {
	  ind = tab.Find(s1);
	  if(sol[ind]>eps) {
	    if(tab.Member(snew+i)) {
	      ind2 = tab.Find(snew+i);
	      if(sol[ind2]>eps)
		v(pl,inf,i) = sol[ind2]/sol[ind];
	    }
	  } 
	} 
	GetProfile(p_support, tab, v,sol,n->GetChild(p_support.Actions(n->GetInfoset())[i]->GetNumber()),snew+i,s2);
      }
    }
    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(tab.Member(ns1+s2)) {
	  ind = tab.Find(ns1+s2);
	  if(sol[ind]>eps) {
	    if(tab.Member(ns1+snew+i)) {
	      ind2 = tab.Find(ns1+snew+i);
	      if(sol[ind2]>eps)
		v(pl,inf,i) = sol[ind2]/sol[ind];
	    }
	  } 
	} 
	GetProfile(p_support, tab, v,sol,n->GetChild(p_support.Actions(n->GetInfoset())[i]->GetNumber()),s1,snew+i);
      }
    }
  }
}