mixed.imp

Gambit 是一个游戏库理论软件

//
// $Source: /home/gambit/CVS/gambit/sources/game/mixed.imp,v $
// $Date: 2002/08/26 05:50:08 $
// $Revision: 1.5 $
//
// DESCRIPTION:
// Implementation of mixed strategy profile classes
//
// 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 "nfg.h"
#include "nfplayer.h"
#include "nfstrat.h"


#include "math/gpvector.h"
#include "mixed.h"

//---------------------------------------------------------------------------
//                    MixedProfile<T> member functions
//---------------------------------------------------------------------------

template <class T> MixedProfile<T>::MixedProfile(const NFSupport &s)
  : gPVector<T>(s.NumStrats()), N(&s.Game()), support(s)
{
  InitPayoffs();
  Centroid();
}

template <class T> MixedProfile<T>::MixedProfile(const MixedProfile<T> &p)
  : gPVector<T>(p), N(p.N), support(p.support)
{ 
  InitPayoffs();
}

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

template <class T>
MixedProfile<T> &MixedProfile<T>::operator=(const MixedProfile<T> &p)
{
  if (this != &p && N == p.N)   {
    // note that a dimensionality change will trigger a failed assertion
    // in the gPVector assignment operator
    support = p.support;
    gPVector<T>::operator=(p);
  }
  return *this;
}

template <class T> void MixedProfile<T>::Centroid(void) 
{
  T center;
  
  for (int i = 1; i <= N->NumPlayers(); i++)  {
    center = ((T) 1) / ((T) support.NumStrats(i));
    for (int j = 1; j <= support.NumStrats(i); j++)
      svptr[i][j] = center;
  }
}

template <class T> T MixedProfile<T>::LiapValue(void) const
{
  static const T BIG1 = (T) 100;
  static const T BIG2 = (T) 100;

  MixedProfile<T> p(*this);
  ((gVector<T> &) p).operator=(*this);
  MixedProfile<T> tmp(p);
  gPVector<T> payoff(p);
  T x, result((T) 0), avg, sum;
  payoff = (T) 0;

  for(int i = 1; i <= N->NumPlayers(); i++) {
    tmp.CopyRow(i, payoff);
    avg = sum = (T) 0;
    // then for each strategy for that player set it to 1 and evaluate
    int j;
    for (j = 1; j <= p.Support().NumStrats(i); j++) {
      tmp(i, j) = (T) 1;
      x = p(i, j);
      payoff(i, j) = tmp.Payoff(i);
      avg += x * payoff(i, j);
      sum += x;
      if (x>(T)0) x=0;
      result += BIG1*x*x;         // add penalty for neg probabilities
      tmp(i,j) = (T) 0;
    }
    tmp.CopyRow(i, p);
    for(j=1;j<=p.Support().NumStrats(i);j++) {
      x=payoff(i,j)-avg;
      if (x<=(T)0) x=(T)0;
      result += x*x;          // add penalty if not best response
    }
    x=sum - ((T) 1);
    result += BIG2*x*x ;          // add penalty for sum not equal to 1
  }
  return result;
}

template <class T> void MixedProfile<T>::Regret(gPVector<T> &value) const
{
  int i, j;
  T pay,x;
  
  for (i = 1; i <= N->NumPlayers(); i++) {
    pay = Payoff(i);
    for (j = 1; j <= N->NumStrats(i); j++) {
      x = Payoff(i, N->Strategies(i)[j]);
      if(x > pay)
	value(i, j) = x - pay;
      // use pay - pay instead of zero for correct precision
      else value(i,j) = pay - pay; 
    }
  }
}

template <class T> T MixedProfile<T>::MaxRegret(void) const
{
  int i;
  T maxgripe = (T)0;

  gPVector<T> v(N->NumStrats());
  Regret(v);
  for(i=v.First(); i<=v.Last(); i++)
    if(v[i] > maxgripe) maxgripe = v[i];
  return maxgripe;
}

template <class T> bool MixedProfile<T>::IsPure(void) const
{
  for (int i = 1; i <= svlen.Length(); i++)
    if (!IsPure(i))  return false;
  return true;
}

template <class T> bool MixedProfile<T>::IsPure(int pl) const
{
  T sum = (T) 0;

  T *val = svptr[pl];

  for (int i = 1; i <= svlen[pl]; sum += *(val++))
    if (*val != (T) 0 && *val != (T) 1)   return false;
  if (sum != (T) 1)  return false;  else return true;
}

template <class T> T MixedProfile<T>::Payoff(int pl) const
{
  return PPayoff(pl, 1, 1);
}

template <class T>
T MixedProfile<T>::Payoff(int pl, int player1, int strat1) const
{
  T value = (T) 0;
  PPayoff(pl, player1, strat1, 1,
	 support.Strategies(player1)[strat1]->Index() + 1, (T) 1, value);
  return value;
}

template <class T> T
MixedProfile<T>::Payoff(int pl, Strategy *strategy) const
{
  T value = (T) 0;
  PPayoff(pl, strategy->Player()->GetNumber(), strategy->Number(), 1,
	  strategy->Index() + 1, (T) 1, value);
  return value;
}

template <class T> T
MixedProfile<T>::Payoff( int pl, int player1, int strat1, int player2,
			int strat2 ) const
{
  if (player1 == player2) return (T) 0;
  T value = (T) 0;
  PPayoff(pl, player1, strat1, player2, strat2, 1,
	 support.Strategies(player1)[strat1]->Index() +
	 support.Strategies(player2)[strat2]->Index() + 1,
	 (T) 1, value);
  return value;
}

template <class T> 
void MixedProfile<T>::Payoff( int pl, int player1, gVector<T> &value) const
{
  value = (T) 0;
  PPayoff(pl, player1, 1, 1, (T) 1, value);
}

template <class T>
bool MixedProfile<T>::operator==(const MixedProfile<T> &mp) const
{
  return (N == mp.N && (const gPVector<T> &) *this == (const gPVector<T> &) mp);
}

template <class T> gOutput &operator<<(gOutput &f, const MixedProfile<T> &p)
{ p.Dump(f);  return f; }


//-------------------------------------- 
// Private Mixed Profile Members
//--------------------------------------

template <class T>
T MixedProfile<T>::PPayoff(int pl, int index, int i) const
{
  Strategy *s;
  int pindex = 0;

  if (i > N->NumPlayers())  {
    if (N->GetOutcome(index))
      return N->Payoff(N->GetOutcome(index), pl);
    else
      return (T) 0;
  }
  T sum = (T) 0;
  for (int j = 1; j <= support.NumStrats(i); j++) {
    s = support.Strategies(i)[j];
    if ((*this)(i, j) != (T) 0) {
      index += s->Index() - pindex;
      pindex = s->Index();
      sum += (*this)(i, j) * PPayoff(pl, index, i + 1);
    }
  }
  return sum;
}

template <class T>
void MixedProfile<T>::PPayoff(int pl, int const_pl, int const_st,
				int cur_pl, long index, T prob, T &value) const
{
  Strategy *s;

  if (cur_pl == const_pl)
    PPayoff(pl, const_pl, const_st, cur_pl + 1, index,
	    prob, value);
  else if (cur_pl > N->NumPlayers())  {
    if (N->GetOutcome(index))
      value += prob * Payoff(N->GetOutcome(index), pl);
  }
  else   {
    for (int j = 1; j <= support.NumStrats(cur_pl); j++)  {
      s = support.Strategies(cur_pl)[j];
      if ((*this)(cur_pl, j) > (T) 0)
	PPayoff(pl, const_pl, const_st, cur_pl + 1,
		index + s->Index(), prob * (*this)(cur_pl, j), value);
    }
  }
}


template <class T>
void MixedProfile<T>::PPayoff(int pl, int const_pl1, int const_st1,
				int const_pl2, int const_st2,
				int cur_pl, long index, T prob, T &value) const
{
  Strategy *s;

  if (cur_pl == const_pl1 || cur_pl == const_pl2)
    PPayoff(pl, const_pl1, const_st1, const_pl2, const_st2,
	    cur_pl + 1, index,prob, value);
  else if (cur_pl > N->NumPlayers())  {
    if (N->GetOutcome(index))
      value += prob *
	Payoff(N->GetOutcome(index), pl);
  }
  else   {
    for (int j = 1; j <= support.NumStrats(cur_pl); j++ ) {
      s = support.Strategies(cur_pl)[j];
      if ((*this)(cur_pl, j) > (T) 0)
	PPayoff(pl, const_pl1, const_st1, const_pl2, const_st2,
		cur_pl + 1, index + s->Index(), prob * (*this)(cur_pl, j),
		value);
    }
  }
}

template <class T>
void MixedProfile<T>::PPayoff(int pl, int const_pl, int cur_pl, long index, 
			   T prob, gVector<T> &value) const
{
  Strategy *s;

  if (cur_pl == const_pl)
    PPayoff(pl, const_pl, cur_pl + 1, index,
	   prob, value);
  else if (cur_pl > N->NumPlayers())  {
    for (int j = 1; j <= support.NumStrats(const_pl); j++ ){ 
      s = support.Strategies(const_pl)[j];
      if (N->GetOutcome(index + s->Index()))
	     value[j] += prob * Payoff(N->GetOutcome(index + s->Index()), pl);
    }
  }
  else   {
    for (int j = 1; j <= support.NumStrats(cur_pl); j++) {
      s = support.Strategies(cur_pl)[j];
      if ((*this)(cur_pl, j) > (T) 0)
	PPayoff(pl, const_pl, cur_pl + 1,
			 index + s->Index(), prob * (*this)(cur_pl, j), value);
    }
  }
}

template <class T>
void MixedProfile<T>::InitPayoffs(void) const
{
  N->InitPayoffs();
}

template <class T>
MixedProfile<T>::MixedProfile(const BehavProfile<T> &p_profile)
  : gPVector<T>(p_profile.GetGame().AssociatedNfg()->NumStrats()),
    N(p_profile.GetGame().AssociatedNfg()), support(*N)
{
  InitPayoffs();
  
  const efgGame &efg = p_profile.GetGame();
  for (int pl = 1; pl <= N->NumPlayers(); pl++)  {
    for (int st = 1; st <= N->NumStrats(pl); st++)  {
      T prob = (T) 1;

      for (int iset = 1; iset <= efg.Players()[pl]->NumInfosets(); iset++) {
	if ((*efg.GetLexicon()->strategies[pl][st])[iset] > 0)
	  prob *= p_profile(pl, iset, (*efg.GetLexicon()->strategies[pl][st])[iset]);
      }
      (*this)(pl, st) = prob;
    }
  }
}