dlefgnash.cc

Gambit 是一个游戏库理论软件

//
// $Source: /home/gambit/CVS/gambit/sources/gui/dlefgnash.cc,v $
// $Date: 2002/09/14 23:24:38 $
// $Revision: 1.10.2.4 $
//
// DESCRIPTION:
// Dialog for selecting algorithms to compute 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 "wx/wxprec.h"
#ifndef WX_PRECOMP
#include "wx/wx.h"
#endif  // WX_PRECOMP
#include "wx/spinctrl.h"
#include "dlefgnash.h"

#include "base/gnullstatus.h"

#include "nash/subsolve.h"

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

const int idCHECKBOX_FINDALL = 2000;
const int idSPINCTRL_STOPAFTER = 2001;

class panelEfgNashAlgorithm : public wxPanel {
public:
  panelEfgNashAlgorithm(wxWindow *p_parent) : wxPanel(p_parent, -1) { }

  virtual efgNashAlgorithm *GetAlgorithm(void) const = 0;
};

//========================================================================
//                         class efgOneNash
//========================================================================

class efgOneNash : public efgNashAlgorithm {
public:
  gText GetAlgorithm(void) const { return "OneNash"; }
  gList<BehavSolution> Solve(const EFSupport &, gStatus &);
};

gList<BehavSolution> efgOneNash::Solve(const EFSupport &p_support,
				       gStatus &p_status)
{
  gArray<int> players(p_support.GetGame().NumPlayers());
  for (int pl = 1; pl <= players.Length(); pl++) {
    players[pl] = pl;
  }

  try {
    gNullStatus status;
    gNullOutput gnull;
    /* one round of elimination of weakly dominated strategies */
    EFSupport support = p_support.Undominated(false, true,
					      players, gnull, status);
    
    SubgameSolver algorithm;
    p_support.GetGame().MarkSubgames();

    if (p_support.GetGame().NumPlayers() == 2) {
      if (p_support.GetGame().IsConstSum()) {
	algorithm.SetAlgorithm(new efgLp<double>);
      }
      else {
	efgLcp<double> *subAlgorithm = new efgLcp<double>;
	subAlgorithm->SetStopAfter(1);
	algorithm.SetAlgorithm(subAlgorithm);
      }
    }
    else {
      algorithm.SetAlgorithm(new nfgSimpdiv<double>);
    }

    return algorithm.Solve(p_support, p_status);
  }
  catch (...) {
    return gList<BehavSolution>();
  }
}

//========================================================================
//                       class panelEfgOneNash
//========================================================================

class panelEfgOneNash : public panelEfgNashAlgorithm {
public:
  panelEfgOneNash(wxWindow *);

  efgNashAlgorithm *GetAlgorithm(void) const;
};

panelEfgOneNash::panelEfgOneNash(wxWindow *p_parent)
  : panelEfgNashAlgorithm(p_parent)
{
  SetAutoLayout(true);

  wxBoxSizer *topSizer = new wxBoxSizer(wxHORIZONTAL);
  
  wxStaticBox *centerBox = new wxStaticBox(this, wxID_STATIC, "OneNashSolve");
  wxStaticBoxSizer *centerSizer = new wxStaticBoxSizer(centerBox, wxVERTICAL);
  centerSizer->Add(new wxStaticText(this, wxID_STATIC,
				    "Find one Nash equilibrium"),
		   0, wxALL | wxCENTER, 5);

  centerSizer->Add(new wxStaticText(this, wxID_STATIC,
				    "This algorithm requires no parameters"),
		   0, wxALL | wxCENTER, 5);
  topSizer->Add(centerSizer, 1, wxALL | wxCENTER, 5);

  SetSizer(topSizer);
  topSizer->Fit(this);
  topSizer->SetSizeHints(this);
  Layout();

  Show(false);
}

efgNashAlgorithm *panelEfgOneNash::GetAlgorithm(void) const
{
  return new efgOneNash;
}

//========================================================================
//                         class efgTwoNash
//========================================================================

class efgTwoNash : public efgNashAlgorithm {
public:
  gText GetAlgorithm(void) const { return "TwoNash"; }
  gList<BehavSolution> Solve(const EFSupport &, gStatus &);
};

gList<BehavSolution> efgTwoNash::Solve(const EFSupport &p_support,
				       gStatus &p_status)
{
  gArray<int> players(p_support.GetGame().NumPlayers());
  for (int pl = 1; pl <= players.Length(); pl++) {
    players[pl] = pl;
  }

  try {
    EFSupport support(p_support);

    while (true) {
      gNullStatus status;
      gNullOutput gnull;
      EFSupport newSupport = support.Undominated(true, true, players,
						 gnull, status);
      
      if (newSupport == support) {
	break;
      }
      else {
	support = newSupport;
      }
    }

    SubgameSolver algorithm;
    p_support.GetGame().UnmarkSubgames(p_support.GetGame().RootNode());

    if (p_support.GetGame().NumPlayers() == 2) {
      nfgEnumMixed<double> *subAlgorithm = new nfgEnumMixed<double>;
      subAlgorithm->SetStopAfter(2);
      algorithm.SetAlgorithm(subAlgorithm);
    }
    else {
      efgPolEnum *subAlgorithm = new efgPolEnum;
      subAlgorithm->SetStopAfter(2);
      algorithm.SetAlgorithm(subAlgorithm);
    }

    return algorithm.Solve(p_support, p_status);
  }
  catch (...) {
    return gList<BehavSolution>();
  }
}

//========================================================================
//                       class panelEfgTwoNash
//========================================================================

class panelEfgTwoNash : public panelEfgNashAlgorithm {
public:
  panelEfgTwoNash(wxWindow *);

  efgNashAlgorithm *GetAlgorithm(void) const;
};

panelEfgTwoNash::panelEfgTwoNash(wxWindow *p_parent)
  : panelEfgNashAlgorithm(p_parent)
{
  SetAutoLayout(true);

  wxBoxSizer *topSizer = new wxBoxSizer(wxHORIZONTAL);
  
  wxStaticBox *centerBox = new wxStaticBox(this, wxID_STATIC, "TwoNashSolve");
  wxStaticBoxSizer *centerSizer = new wxStaticBoxSizer(centerBox, wxVERTICAL);
  centerSizer->Add(new wxStaticText(this, wxID_STATIC,
				    "Find two Nash equilibria"),
		   0, wxALL | wxCENTER, 5);

  centerSizer->Add(new wxStaticText(this, wxID_STATIC,
				    "This algorithm requires no parameters"),
		   0, wxALL | wxCENTER, 5);
  topSizer->Add(centerSizer, 1, wxALL | wxCENTER, 5);

  SetSizer(topSizer);
  topSizer->Fit(this);
  topSizer->SetSizeHints(this);
  Layout();

  Show(false);
}

efgNashAlgorithm *panelEfgTwoNash::GetAlgorithm(void) const
{
  return new efgTwoNash;
}

//========================================================================
//                         class efgAllNash
//========================================================================

class efgAllNash : public efgNashAlgorithm {
public:
  gText GetAlgorithm(void) const { return "AllNash"; }
  gList<BehavSolution> Solve(const EFSupport &, gStatus &);
};

gList<BehavSolution> efgAllNash::Solve(const EFSupport &p_support,
				       gStatus &p_status)
{
  gArray<int> players(p_support.GetGame().NumPlayers());
  for (int pl = 1; pl <= players.Length(); pl++) {
    players[pl] = pl;
  }

  try {
    EFSupport support(p_support);

    while (true) {
      gNullStatus status;
      gNullOutput gnull;
      EFSupport newSupport = support.Undominated(true, true, players,
						 gnull, status);
      
      if (newSupport == support) {
	break;
      }
      else {
	support = newSupport;
      }
    }

    SubgameSolver algorithm;
    p_support.GetGame().UnmarkSubgames(p_support.GetGame().RootNode());

    if (p_support.GetGame().NumPlayers() == 2) {
      nfgEnumMixed<double> *subAlgorithm = new nfgEnumMixed<double>;
      subAlgorithm->SetStopAfter(0);
      algorithm.SetAlgorithm(subAlgorithm);
    }
    else {
      efgPolEnum *subAlgorithm = new efgPolEnum;
      subAlgorithm->SetStopAfter(0);
      algorithm.SetAlgorithm(subAlgorithm);
    }

    return algorithm.Solve(p_support, p_status);
  }
  catch (...) {
    return gList<BehavSolution>();
  }
}

//========================================================================
//                       class panelEfgAllNash
//========================================================================

class panelEfgAllNash : public panelEfgNashAlgorithm {
public:
  panelEfgAllNash(wxWindow *);

  efgNashAlgorithm *GetAlgorithm(void) const;
};

panelEfgAllNash::panelEfgAllNash(wxWindow *p_parent)
  : panelEfgNashAlgorithm(p_parent)
{
  SetAutoLayout(true);

  wxBoxSizer *topSizer = new wxBoxSizer(wxVERTICAL);

  wxStaticBox *centerBox = new wxStaticBox(this, wxID_STATIC, "AllNashSolve");
  wxStaticBoxSizer *centerSizer = new wxStaticBoxSizer(centerBox, wxVERTICAL);
  centerSizer->Add(new wxStaticText(this, wxID_STATIC,
				    "Find all Nash equilibria"),
		   0, wxALL | wxCENTER, 5);
  centerSizer->Add(new wxStaticText(this, wxID_STATIC,
				    "This algorithm requires no parameters"),
		   0, wxALL | wxCENTER, 5);
  topSizer->Add(centerSizer, 1, wxALL | wxCENTER, 5);

  SetSizer(topSizer);
  topSizer->Fit(this);
  topSizer->SetSizeHints(this);
  Layout();

  Show(false);
}

efgNashAlgorithm *panelEfgAllNash::GetAlgorithm(void) const
{
  return new efgAllNash;
}

//========================================================================
//                         class efgOnePerfect
//========================================================================

class efgOnePerfect : public efgNashAlgorithm {
public:
  gText GetAlgorithm(void) const { return "OnePerfect"; }
  gList<BehavSolution> Solve(const EFSupport &, gStatus &);
};

gList<BehavSolution> efgOnePerfect::Solve(const EFSupport &p_support,
					  gStatus &p_status)
{
  gArray<int> players(p_support.GetGame().NumPlayers());
  for (int pl = 1; pl <= players.Length(); pl++) {
    players[pl] = pl;
  }

  try {
    gNullStatus status;
    gNullOutput gnull;
    /* one round of elimination of weakly dominated strategies */
    EFSupport support = p_support.Undominated(false, true,
					      players, gnull, status);
    
    SubgameSolver algorithm;
    p_support.GetGame().MarkSubgames();

    if (p_support.GetGame().NumPlayers() == 2) {
      if (p_support.GetGame().IsConstSum()) {
	algorithm.SetAlgorithm(new efgLp<double>);
      }
      else {
	efgLcp<double> *subAlgorithm = new efgLcp<double>;
	subAlgorithm->SetStopAfter(1);
	algorithm.SetAlgorithm(subAlgorithm);
      }
    }
    else {
      algorithm.SetAlgorithm(new nfgSimpdiv<double>);
    }

    return algorithm.Solve(p_support, p_status);
  }
  catch (...) {
    return gList<BehavSolution>();
  }
}

//========================================================================
//                       class panelEfgOnePerfect
//========================================================================

class panelEfgOnePerfect : public panelEfgNashAlgorithm {
public:
  panelEfgOnePerfect(wxWindow *);

  efgNashAlgorithm *GetAlgorithm(void) const;
};

panelEfgOnePerfect::panelEfgOnePerfect(wxWindow *p_parent)
  : panelEfgNashAlgorithm(p_parent)
{
  SetAutoLayout(true);

  wxBoxSizer *topSizer = new wxBoxSizer(wxVERTICAL);

  wxStaticBox *centerBox = new wxStaticBox(this, wxID_STATIC,
					   "OnePerfectSolve");
  wxStaticBoxSizer *centerSizer = new wxStaticBoxSizer(centerBox, wxVERTICAL);
  centerSizer->Add(new wxStaticText(this, wxID_STATIC,
				    "Find one subgame perfect "
				    "Nash equilibrium"),
		   0, wxALL | wxCENTER, 5);
  centerSizer->Add(new wxStaticText(this, wxID_STATIC,
				    "This algorithm requires no parameters"),
		   0, wxALL | wxCENTER, 5);
  topSizer->Add(centerSizer, 1, wxALL | wxCENTER, 5);

  SetSizer(topSizer);
  topSizer->Fit(this);
  topSizer->SetSizeHints(this);
  Layout();

  Show(false);
}

efgNashAlgorithm *panelEfgOnePerfect::GetAlgorithm(void) const
{
  return new efgOnePerfect;
}

//========================================================================
//                         class efgTwoPerfect
//========================================================================

class efgTwoPerfect : public efgNashAlgorithm {
public:
  gText GetAlgorithm(void) const { return "TwoPerfect"; }
  gList<BehavSolution> Solve(const EFSupport &, gStatus &);
};

gList<BehavSolution> efgTwoPerfect::Solve(const EFSupport &p_support,
					  gStatus &p_status)
{
  gArray<int> players(p_support.GetGame().NumPlayers());
  for (int pl = 1; pl <= players.Length(); pl++) {
    players[pl] = pl;
  }

  try {
    EFSupport support(p_support);

    while (true) {
      gNullStatus status;
      gNullOutput gnull;
      EFSupport newSupport = support.Undominated(true, true, players,