cards.cc

#include <assert.h>
#include <iostream>
#include <random>
#include <memory.h>

const int kNCards = 5;

double dp[1 << kNCards][1 << kNCards][5][5];
bool w[1 << kNCards][1 << kNCards][5][5];

double prob(int c1, int c2, int t1, int t2) {
  double& res = dp[c1][c2][t1][t2];

  if (!w[c1][c2][t1][t2]) {
    w[c1][c2][t1][t2] = true;
    if (c1 == 0) {
      assert(c2 == 0);
      if (t1 > t2) {
        res = 1;
      } else if (t1 == t2) {
        res = 0;
      } else {
        res = -1;
      }
    } else {
      res = -100000;
      int ncards = __builtin_popcount(c1);
      assert(__builtin_popcount(c2) == ncards);
      for (int i=0; i < kNCards; ++i) {
        if (c1 & (1 << i)) {
          double cur = 0;
          for (int j=0; j < kNCards; ++j) {
            if (c2 & (1 << j)) {
              cur += prob(c1 & ~(1 << i), c2 & ~(1 << j), t1 + (i > j), t2 + (j > i));
            }
          }
          cur /= ncards;

          if (cur > res) {
            res = cur;
          }
        }
      }
    }
  }

  return res;
}

int main() {
  memset(w, 0, sizeof(w));
  std::cout << prob((1 << kNCards)-1, (1 << kNCards)-1, 0, 0) << std::endl;;
}