algfunc.cc

来自「Gambit 是一个游戏库理论软件」· CC 代码 · 共 1,541 行 · 第 1/4 页

//
// $Source: /home/gambit/CVS/gambit/sources/gcl/algfunc.cc,v $
// $Date: 2002/09/10 14:27:35 $
// $Revision: 1.11.2.1 $
//
// DESCRIPTION:
// Functions for computing Nash equilibria
//
// 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 "gsm.h"
#include "portion.h"
#include "gsmfunc.h"

#include "math/rational.h"

#include "game/nfg.h"
#include "game/nfplayer.h"
#include "game/efg.h"

#include "nash/subsolve.h"
#include "nash/nfgpure.h"
#include "nash/efgpure.h"
#include "nash/enum.h"
#include "nash/lemke.h"
#include "nash/seqform.h"
#include "nash/nliap.h"
#include "nash/eliap.h"
#include "nash/nfgcsum.h"
#include "nash/efgcsum.h"
#include "nash/nfgalleq.h"
#include "nash/efgalleq.h"
#include "nash/nfgqregrid.h"
#include "nash/nfgqre.h"
#include "nash/efgqre.h"
#include "nash/simpdiv.h"

#include "numerical/vertenum.h"
#include "numerical/lpsolve.h"


template <class T> Portion *ArrayToList(const gArray<T> &);
extern gVector<double>* ListToVector_Float(ListPortion* list);
extern gVector<gRational>* ListToVector_Rational(ListPortion* list);
extern gMatrix<double>* ListToMatrix_Float(ListPortion* list);
extern gMatrix<gRational>* ListToMatrix_Rational(ListPortion* list);


//
// Useful utilities for creation of lists of profiles
//
class Mixed_ListPortion : public ListPortion   {
  public:
    Mixed_ListPortion(const gList<MixedSolution> &);
    virtual ~Mixed_ListPortion()   { }
};

Mixed_ListPortion::Mixed_ListPortion(const gList<MixedSolution> &list)
{
  rep->_DataType = porMIXED;
  for (int i = 1; i <= list.Length(); i++)
    Append(new MixedPortion(new MixedSolution(list[i])));
}

class Behav_ListPortion : public ListPortion   {
  public:
    Behav_ListPortion(const gList<BehavSolution> &);
    virtual ~Behav_ListPortion()   { }
};

Behav_ListPortion::Behav_ListPortion(const gList<BehavSolution> &list)
{
  rep->_DataType = porBEHAV;
  for (int i = 1; i <= list.Length(); i++)
    Append(new BehavPortion(new BehavSolution(list[i])));
}

class NfSupport_ListPortion : public ListPortion   {
  public:
    NfSupport_ListPortion(const gList<const NFSupport> &);
    NfSupport_ListPortion();
    virtual ~NfSupport_ListPortion()   { }

  void SetValue(const gList<const NFSupport> &);
};

NfSupport_ListPortion::NfSupport_ListPortion(const gList<const 
					                 NFSupport> &list)
{
  rep->_DataType = porNFSUPPORT;
  for (int i = 1; i <= list.Length(); i++)
    Append(new NfSupportPortion(new NFSupport(list[i])));
}

NfSupport_ListPortion::NfSupport_ListPortion()
{
  rep->_DataType = porNFSUPPORT;
}

void NfSupport_ListPortion::SetValue(const gList<const NFSupport> &list)
{
  for (int i = 1; i <= list.Length(); i++)
    Append(new NfSupportPortion(new NFSupport(list[i])));
}


class EfSupport_ListPortion : public ListPortion   {
  public:
    EfSupport_ListPortion(const gList<const EFSupport> &);
    EfSupport_ListPortion();
    virtual ~EfSupport_ListPortion()   { }

  void SetValue(const gList<const EFSupport> &);
};

EfSupport_ListPortion::EfSupport_ListPortion(const gList<const 
					                 EFSupport> &list)
{
  rep->_DataType = porEFSUPPORT;
  for (int i = 1; i <= list.Length(); i++)
    Append(new EfSupportPortion(new EFSupport(list[i])));
}

EfSupport_ListPortion::EfSupport_ListPortion()
{
  rep->_DataType = porEFSUPPORT;
}

void EfSupport_ListPortion::SetValue(const gList<const EFSupport> &list)
{
  for (int i = 1; i <= list.Length(); i++)
    Append(new EfSupportPortion(new EFSupport(list[i])));
}



//-------------
// AgentForm
//-------------

static Portion *GSM_AgentForm(GSM &, Portion **param)
{
  efgGame &E = *((EfgPortion*) param[0])->Value();
  gWatch watch;

  Nfg *N = MakeAfg(E);
  
  ((NumberPortion *) param[1])->SetValue(watch.Elapsed());

  if (N)
    return new NfgPortion(N);
  else
    throw gclRuntimeError("Conversion to agent form failed");
}

//------------
// Behav
//------------

static Portion *GSM_Behav(GSM &, Portion **param)
{
  MixedSolution &mp = *((MixedPortion*) param[0])->Value();
  BehavProfile<gNumber> *bp = new BehavProfile<gNumber>(MixedProfile<gNumber>(*mp.Profile()));
  BehavSolution *bs = new BehavSolution(*bp);
  bs->SetCreator(mp.Creator());
  bs->SetEpsilon(mp.Epsilon());
    
  return new BehavPortion(bs);
}


//------------------
// EnumMixedSolve
//------------------

static nfgNashAlgorithm *GSM_EnumMixed_Nfg_Double(int p_stopAfter,
						  bool p_cliques)
{
  nfgEnumMixed<double> *algorithm = new nfgEnumMixed<double>;
  algorithm->SetStopAfter(p_stopAfter);
  algorithm->SetCliques(p_cliques);
  return algorithm;
}

static nfgNashAlgorithm *GSM_EnumMixed_Nfg_Rational(int p_stopAfter,
						    bool p_cliques)
{
  nfgEnumMixed<gRational> *algorithm = new nfgEnumMixed<gRational>;
  algorithm->SetStopAfter(p_stopAfter);
  algorithm->SetCliques(p_cliques);
  return algorithm;
}

static Portion *GSM_EnumMixed_Nfg(GSM &gsm, Portion **param)
{
  const NFSupport &support = AsNfgSupport(param[0]);
  nfgNashAlgorithm *algorithm = 0;

  if (((PrecisionPortion *) param[2])->Value() == precDOUBLE) {
    algorithm = GSM_EnumMixed_Nfg_Double(AsNumber(param[1]), AsBool(param[7]));
  }
  else {
    algorithm = GSM_EnumMixed_Nfg_Rational(AsNumber(param[1]),
					   AsBool(param[7]));
  }

  gList<MixedSolution> solutions;

  gsm.StartAlgorithmMonitor("EnumMixedSolve Progress");
  try {
    solutions = algorithm->Solve(support, gsm.GetStatusMonitor());
  }
  catch (gSignalBreak &) { }
  catch (...) {
    gsm.EndAlgorithmMonitor();
    delete algorithm;
    throw;
  }

  delete algorithm;
  gsm.EndAlgorithmMonitor();
  return new Mixed_ListPortion(solutions);
}

static Portion *GSM_EnumMixed_Efg(GSM &gsm, Portion **param)
{
  const EFSupport &support = AsEfgSupport(param[0]);

  if (!AsBool(param[1])) {
    throw gclRuntimeError("algorithm not implemented for extensive forms");
  }

  nfgNashAlgorithm *nfgAlgorithm = 0;

  if (((PrecisionPortion *) param[3])->Value() == precDOUBLE) {
    nfgAlgorithm = GSM_EnumMixed_Nfg_Double(AsNumber(param[2]),
					    AsBool(param[8]));
  }
  else {
    nfgAlgorithm = GSM_EnumMixed_Nfg_Rational(AsNumber(param[2]),
					      AsBool(param[8]));
  }

  if (!IsPerfectRecall(support.GetGame())) {
    gsm.OutputStream() << "WARNING: Solving game of imperfect recall with EnumMixed; results not guaranteed\n";
  }

  SubgameSolver *algorithm = new SubgameSolver;
  algorithm->SetAlgorithm(nfgAlgorithm);

  gsm.StartAlgorithmMonitor("EnumMixedSolve Progress");
  gList<BehavSolution> solutions;
  try {
    solutions = algorithm->Solve(support, gsm.GetStatusMonitor());
  }
  catch (gSignalBreak &) { }
  catch (...) {
    gsm.EndAlgorithmMonitor();
    delete algorithm;
    throw;
  }
  delete algorithm;
  gsm.EndAlgorithmMonitor();
  return new Behav_ListPortion(solutions);
}


//-----------------
// EnumPureSolve
//-----------------

static Portion *GSM_EnumPure_Nfg(GSM &gsm, Portion **param)
{
  NFSupport *support = ((NfSupportPortion*) param[0])->Value();

  gWatch watch;
  gList<MixedSolution> solutions;

  gsm.StartAlgorithmMonitor("EnumPureSolve Progress");
  try {
    nfgEnumPure solver;
    solver.SetStopAfter(((NumberPortion *) param[1])->Value());
    solutions = solver.Solve(*support, gsm.GetStatusMonitor());
    ((NumberPortion *) param[3])->SetValue(watch.Elapsed());
  }
  catch (gSignalBreak &) { }
  catch (...) {
    gsm.EndAlgorithmMonitor();
    throw;
  }

  gsm.EndAlgorithmMonitor();
  return new Mixed_ListPortion(solutions);
}

static Portion *GSM_EnumPure_Efg(GSM &gsm, Portion **param)
{
  const EFSupport &support = AsEfgSupport(param[0]);

  if (!IsPerfectRecall(support.GetGame())) {
    gsm.OutputStream() << "WARNING: Solving game of imperfect recall with EnumPure; results not guaranteed\n";
  }

  gsm.StartAlgorithmMonitor("EnumPureSolve Progress");

  gList<BehavSolution> solutions;
  if (AsBool(param[1])) {
    try {
      nfgEnumPure *nfgAlgorithm = new nfgEnumPure;
      nfgAlgorithm->SetStopAfter(AsNumber(param[2]));
      SubgameSolver algorithm;
      algorithm.SetAlgorithm(nfgAlgorithm);
      solutions = algorithm.Solve(support, gsm.GetStatusMonitor());
    }
    catch (gSignalBreak &) { }
    catch (...) {
      gsm.EndAlgorithmMonitor();
      throw;
    }
  }
  else  {
    try {
      efgEnumPure algorithm;
      algorithm.SetStopAfter(AsNumber(param[2]));
      solutions = algorithm.Solve(support, gsm.GetStatusMonitor());
    }
    catch (gSignalBreak &) { }
    catch (...) {
      gsm.EndAlgorithmMonitor();
      throw;
    }
  }
  gsm.EndAlgorithmMonitor();
  return new Behav_ListPortion(solutions);
}

//------------
// LcpSolve
//------------

static nfgNashAlgorithm *GSM_Lcp_Nfg_Double(int p_stopAfter)
{
  nfgLcp<double> *algorithm = new nfgLcp<double>;
  algorithm->SetStopAfter(p_stopAfter);
  return algorithm;
}

static nfgNashAlgorithm *GSM_Lcp_Nfg_Rational(int p_stopAfter)
{
  nfgLcp<gRational> *algorithm = new nfgLcp<gRational>;
  algorithm->SetStopAfter(p_stopAfter);
  return algorithm;
}

static Portion *GSM_Lcp_Nfg(GSM &gsm, Portion **param)
{
  const NFSupport &support = AsNfgSupport(param[0]);
  const Nfg &nfg = support.Game();

  if (nfg.NumPlayers() != 2) {
    throw gclRuntimeError("Only valid for two-person games");
  }

  nfgNashAlgorithm *algorithm = 0;

  if (AsPrecision(param[2]) == precDOUBLE) {
    algorithm = GSM_Lcp_Nfg_Double(AsNumber(param[1]));
  }