sgsolver_maxminmax.hpp

// This file is part of the SGSolve library for stochastic games
// Copyright (C) 2019 Benjamin A. Brooks
// 
// SGSolve 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 3 of the License, or
// (at your option) any later version.
// 
// SGSolve 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, see
// <http://www.gnu.org/licenses/>.
// 
// Benjamin A. Brooks
// ben@benjaminbrooks.net
// Chicago, IL
 
#ifndef _SGSOLVER_MAXMINMAX_HPP
#define _SGSOLVER_MAXMINMAX_HPP
 
#include "sgcommon.hpp"
#include "sgutilities.hpp"
#include "sgenv.hpp"
#include "sggame.hpp"
#include "sgaction_maxminmax.hpp"
#include "sgexception.hpp"
#include "sgsolution_maxminmax.hpp"
 
 
class SGSolver_MaxMinMax
{
private:
  // Data
 
  const SGEnv & env;
  const SGGame & game; 
  SGSolution_MaxMinMax soln;
 
  // References to objects in the game
  const double delta; 
  const int numPlayers; 
  const int numStates; 
  const vector< vector<bool> > & eqActions; 
  const vector< vector<SGPoint> > & payoffs; 
  const vector< vector< vector<double> > > & probabilities; 
  const vector< vector<int> > numActions; 
  const vector< int > numActions_totalByState; 
  list<SGPoint> directions; 
  list< vector<double> > levels; 
  SGTuple threatTuple; 
  vector< list<SGAction_MaxMinMax> > actions; 
  const SGPoint dueEast = SGPoint(1.0,0.0); 
  const SGPoint dueNorth = SGPoint(0.0,1.0); 
  int numIter; 
  double errorLevel; 
public:
  SGSolver_MaxMinMax(); 
 
 
  SGSolver_MaxMinMax(const SGEnv & _env, 
       const SGGame & _game);
 
  ~SGSolver_MaxMinMax() {}
 
 
  void solve_fixed();
 
 
  void solve();
 
 
  double iterate();
 
double pseudoHausdorff(const list<SGPoint> & newDirections,
                       const list<vector<double> > & newLevels) const;
 
  void initialize();
 
  std::string progressString() const;
 
  void robustOptimizePolicy(SGTuple & pivot,
                vector<double> & penalties,
                vector<SGActionIter> & actionTuple,
                vector<SG::Regime> & regimeTuple,
                vector<bool> & bestAPSNotBinding,
                SGTuple & bestBindingPayoffs,
                const SGPoint currDir,
                const vector<list<SGAction_MaxMinMax> > & actions) const;
 
  double sensitivity(const SGTuple & pivot,
             const vector<double> & penalties,
             const vector<SGActionIter> & actionTuple,
             const vector<SG::Regime> & regimeTuple,
             const SGPoint currDir,
             const vector<list<SGAction_MaxMinMax> > & actions) const;
 
  void policyToPayoffs(SGTuple & pivot,
               const vector<SGActionIter>  & actionTuple,
               const vector<SG::Regime> & regimeTuple) const;
 
  void policyToPenalties(vector<double> & penalties,
             const vector<SGActionIter>  & actionTuple,
             const vector<SG::Regime> & regimeTuple) const;
 
 
  bool lexComp(const SGPoint & a,
           const double aPenalty,
           const SGPoint & b,
           const double bPenalty,
           const SGPoint & dir ) const;
 
  bool computeBestBindingPayoff(const SGActionIter ait,
                int & bestBindingPlayer,
                int & bestBindingPoint,
                const SGPoint & dir) const;
 
  void updateBestBinding(const vector<SGActionIter> & actionTuple,
             const vector<SG::Regime> & regimeTuple,
             const SGPoint & dir,
             SGTuple & bestBindingPayoffs,
             vector<bool> & bestAPSNotBinding) const;
 
  void minimizeRegimes(SGTuple & pivot,
               vector<double> & penalties,
               const vector<SGActionIter> & actionTuple,
               vector<SG::Regime> & regimeTuple,
               const SGPoint & dir,
               const SGTuple & bestBindingPayoffs,
               const vector<bool> & bestAPSNotBinding) const;
 
 
  bool lexAbove(const SGPoint & a, const SGPoint & b ) const;
  
  const SGSolution_MaxMinMax& getSolution() const {return soln;}
};
 
 
#endif