algfunc.cc

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

  else {
    algorithm = GSM_Lcp_Nfg_Rational(AsNumber(param[1]));
  }

  gList<MixedSolution> solutions;

  gsm.StartAlgorithmMonitor("LcpSolve 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 efgNashAlgorithm *GSM_Lcp_Efg_Double(int p_stopAfter)
{
  efgLcp<double> *algorithm = new efgLcp<double>;
  algorithm->SetStopAfter(p_stopAfter);
  return algorithm;
}

static efgNashAlgorithm *GSM_Lcp_Efg_Rational(int p_stopAfter)
{
  efgLcp<gRational> *algorithm = new efgLcp<gRational>;
  algorithm->SetStopAfter(p_stopAfter);
  return algorithm;
}

static Portion *GSM_Lcp_Efg(GSM &gsm, Portion **param)
{
  const EFSupport &support = AsEfgSupport(param[0]);
  const efgGame &efg = support.GetGame();

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

  SubgameSolver algorithm;
  
  if (AsBool(param[1])) {
    if (((PrecisionPortion *) param[3])->Value() == precDOUBLE) {
      algorithm.SetAlgorithm(GSM_Lcp_Nfg_Double(AsNumber(param[2])));
    }
    else {
      algorithm.SetAlgorithm(GSM_Lcp_Nfg_Rational(AsNumber(param[2])));	
    }
  }
  else {
    if (((PrecisionPortion *) param[3])->Value() == precDOUBLE) {
      algorithm.SetAlgorithm(GSM_Lcp_Efg_Double(AsNumber(param[2])));
    }
    else {
      algorithm.SetAlgorithm(GSM_Lcp_Efg_Rational(AsNumber(param[2])));
    }
  }

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

#include "numerical/lemketab.h"

Portion* GSM_Lcp_ListNumber(GSM &, Portion** param)
{
  if (((PrecisionPortion *) param[2])->Value() == precDOUBLE) {
    gMatrix<double> *a = ListToMatrix_Float((ListPortion*) param[0]);
    gVector<double> *b = ListToVector_Float((ListPortion*) param[1]);

    gMatrix<double> aa(1,a->NumRows(),0,a->NumColumns());

    int i,j;
    for (i = 1;i<=a->NumRows();i++) {
      for (j = 1;j<=a->NumColumns();j++)
	aa(i,j) = (*a)(a->MinRow()-1+i,a->MinCol()-1+j);
      aa(i,0) = 1;
    }
    aa(a->NumRows(),0) = 0;

    LTableau<double> *tab = new LTableau<double>(aa, *b);
    tab->LemkePath(0);
    gVector<double> vector(*b);
    tab->BasisVector(vector);
    Portion *result = ArrayToList(vector);
    delete tab;
    delete a;
    delete b;
      
    return result;
  }
  else {  // precision == precRATIONAL
    gMatrix<gRational> *a = ListToMatrix_Rational((ListPortion*) param[0]);
    gVector<gRational> *b = ListToVector_Rational((ListPortion*) param[1]);
      
    LTableau<gRational> *tab = new LTableau<gRational>(*a, *b);
    tab->LemkePath(0);
    gVector<gRational> vector;
    tab->BasisVector(vector);
    Portion *result = ArrayToList(vector);
    delete tab;
    delete a;
    delete b;
      
    return result;
  }
}

//-------------
// LiapSolve
//-------------

#include "nash/eliap.h"

static Portion *GSM_Liap_Behav(GSM &gsm, Portion **param)
{
  const BehavProfile<gNumber> &start = *AsBehav(param[0]).Profile();
  const efgGame &efg = start.GetGame();
  const EFSupport &support = start.Support();
  
  gsm.StartAlgorithmMonitor("LiapSolve Progress");

  SubgameSolver algorithm;

  if (AsBool(param[1])) {
    nfgLiap *nfgAlgorithm = new nfgLiap;
    nfgAlgorithm->SetStopAfter(AsNumber(param[2]));
    nfgAlgorithm->SetNumTries(AsNumber(param[3]));
    algorithm.SetAlgorithm(nfgAlgorithm);
  }
  else {
    efgLiap *efgAlgorithm = new efgLiap;
    efgAlgorithm->SetStopAfter(AsNumber(param[2]));
    efgAlgorithm->SetNumTries(AsNumber(param[3]));
    algorithm.SetAlgorithm(efgAlgorithm);
  }

  gList<BehavSolution> solutions;

  try {
    solutions = algorithm.Solve(support, gsm.GetStatusMonitor());
  }
  catch (gSignalBreak &) { }
  catch (...) {
    gsm.EndAlgorithmMonitor();
    throw;
  }

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

static Portion *GSM_Liap_Mixed(GSM &gsm, Portion **param)
{
  const MixedProfile<gNumber> &start = *AsMixed(param[0]).Profile();
  const Nfg &nfg = start.Game();

  nfgLiap algorithm;
  algorithm.SetStopAfter(AsNumber(param[1]));
  algorithm.SetNumTries(AsNumber(param[2]));

  gList<MixedSolution> solutions;
  gsm.StartAlgorithmMonitor("LiapSolve Progress");
  try {
    solutions = algorithm.Solve(start.Support(), gsm.GetStatusMonitor());
  }
  catch (gSignalBreak &) { }
  catch (...) {
    gsm.EndAlgorithmMonitor();
    throw;
  }

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

//------------
// LpSolve
//------------

static nfgNashAlgorithm *GSM_Lp_Nfg_Double(void)
{
  nfgLcp<double> *algorithm = new nfgLcp<double>;
  algorithm->SetStopAfter(1);
  return algorithm;
}

static nfgNashAlgorithm *GSM_Lp_Nfg_Rational(void)
{
  nfgLcp<gRational> *algorithm = new nfgLcp<gRational>;
  algorithm->SetStopAfter(1);
  return algorithm;
}

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

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

  nfgNashAlgorithm *algorithm =
    (AsBool(param[1])) ? GSM_Lp_Nfg_Double() : GSM_Lp_Nfg_Rational();

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

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


Portion* GSM_Lp_List(GSM &gsm, Portion** param)
{
  if (((PrecisionPortion *) param[4])->Value() == precDOUBLE)  {
    gMatrix<double>* a = ListToMatrix_Float((ListPortion*) param[0]);
    gVector<double>* b = ListToVector_Float((ListPortion*) param[1]);
    gVector<double>* c = ListToVector_Float((ListPortion*) param[2]);

    int nequals = ((NumberPortion*) param[3])->Value();
    bool isFeasible;
    bool isBounded;
    double value;

    LPSolve<double>* s = new LPSolve<double>(*a, *b, *c, nequals,
					     gsm.GetStatusMonitor());
    Portion* result = ArrayToList(s->OptimumVector());
    isFeasible = s->IsFeasible();
    isBounded = s->IsBounded();
    value = s->OptimumCost();
    delete s;
    delete a;
    delete b;
    delete c;
  
    ((BoolPortion*) param[5])->SetValue((isFeasible) ? triTRUE : triFALSE);
    ((BoolPortion*) param[6])->SetValue((isBounded) ? triTRUE : triFALSE);
    ((NumberPortion*) param[7])->SetValue((value));
    return result;
  }
  else  {
    gMatrix<gRational>* a = ListToMatrix_Rational((ListPortion*) param[0]);
    gVector<gRational>* b = ListToVector_Rational((ListPortion*) param[1]);
    gVector<gRational>* c = ListToVector_Rational((ListPortion*) param[2]);

    int nequals = ((NumberPortion*) param[3])->Value();
    bool isFeasible;
    bool isBounded;
    gRational value;
  
    LPSolve<gRational>* s = new LPSolve<gRational>(*a, *b, *c, nequals,
						   gsm.GetStatusMonitor());
    Portion* result = ArrayToList(s->OptimumVector());
    isFeasible = s->IsFeasible();
    isBounded = s->IsBounded();
    value = s->OptimumCost();
    delete s;
    delete a;
    delete b;
    delete c;
  
    ((BoolPortion *) param[5])->SetValue((isFeasible) ? triTRUE : triFALSE);
    ((BoolPortion *) param[6])->SetValue((isBounded) ? triTRUE : triFALSE);
    ((NumberPortion*) param[7])->SetValue((value));
    return result;
  }
}

static efgNashAlgorithm *GSM_Lp_Efg_Double(void)
{
  efgLcp<double> *algorithm = new efgLcp<double>;
  algorithm->SetStopAfter(1);
  return algorithm;
}

static efgNashAlgorithm *GSM_Lp_Efg_Rational(void)
{
  efgLcp<gRational> *algorithm = new efgLcp<gRational>;
  algorithm->SetStopAfter(1);
  return algorithm;
}


static Portion *GSM_Lp_Efg(GSM &gsm, Portion **param)
{
  const EFSupport &support = AsEfgSupport(param[0]);
  const efgGame &efg = support.GetGame();
  
  if (efg.NumPlayers() != 2 || !efg.IsConstSum()) {
    throw gclRuntimeError("Only valid for two-person zero-sum games");
  }

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

  SubgameSolver algorithm;
  
  if (AsBool(param[1])) {
    if (((PrecisionPortion *) param[2])->Value() == precDOUBLE) {
      algorithm.SetAlgorithm(GSM_Lp_Nfg_Double());
    }
    else {
      algorithm.SetAlgorithm(GSM_Lp_Nfg_Rational());
    }
  }
  else {
    if (((PrecisionPortion *) param[2])->Value() == precDOUBLE) {
      algorithm.SetAlgorithm(GSM_Lp_Efg_Double());
    }
    else {
      algorithm.SetAlgorithm(GSM_Lp_Efg_Rational());
    }
  }

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


//------------------
//  PolEnumSolve
//------------------

static Portion *GSM_PolEnumSolve_Nfg(GSM &gsm, Portion **param)
{
  const NFSupport &support = AsNfgSupport(param[0]);
  
  nfgPolEnum algorithm;
  algorithm.SetStopAfter(AsNumber(param[1]));
  gList<MixedSolution> solutions;

  gsm.StartAlgorithmMonitor("PolEnumSolve Progress");
  try {
    solutions = algorithm.Solve(support, gsm.GetStatusMonitor());
  }
  catch (gSignalBreak &) { }
  catch (...) {
    gsm.EndAlgorithmMonitor();
    throw;
  }
  gsm.EndAlgorithmMonitor();
  return new Mixed_ListPortion(solutions);
}

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

  if (!IsPerfectRecall(support.GetGame())) {