モンテカルロ法でシャープレイ値を計算

　昨日動的計画法でシャープレイ値を計算してみたが、一般的な計算方法としてよく知られたものだったらしい。他にもモンテカルロ法を使った計算方法もあるとのことなので、モンテカルロ法で計算するプログラムも書いてみた。

問題は昨日のやつと同じく国連理事国のやつ。random_shuffle便利だよねーっていう。

#include <iostream>
#include <vector>

using namespace std;

const int N = 15;  // # of members
const int M = 9;   // required # of members to approve a decision
const int K = 5;   // # of permanent members
const int T = 1e6; // # of MC iteration

inline int payoff(int s) {
  int vetoMask = (1<<K) - 1;

  if ((s & vetoMask) < vetoMask)
    return 0;

  if (__builtin_popcount(s) < M)
    return 0;

  return 1;
}

double sharpleyValue(int p) {
  vector<int> v;
  for (int i = 0; i < N; i++)
    v.push_back(i);

  double ret = 0;
  for (int _ = 0; _ < T; _++) {
    random_shuffle(v.begin(), v.end());
    int s = 0;
    for (auto & x : v) {
      int t = s | 1 << x;
      if (x == p) {
        ret += payoff(t) - payoff(s);
        break;
      }
      s = t;
    }
  }
  
  return ret / T;
}

int main() {

  for (int i = 0; i < N; i++)
    cout << i << " :" << sharpleyValue(i) << endl;

  return 0;
}