强化学习作业 1

#include <string>

using int64 = long long;
using uint64 = unsigned long long;
using uint32 = unsigned int;

struct state {
    uint32 u;

    inline constexpr state(uint32 u) : u(u) {}
    inline constexpr operator uint32() const { return u; }
    inline constexpr state(const std::string& str) : u(0) {
        for (int i = 0; i < 9; i++) {
            uint32 val = 0;
            if (str[i] == 'x') {
                val = 1;
            } else if (str[i] == 'o') {
                val = 2;
            } else {
                val = 0;
            }
            u |= val << (i * 2);
        }
    }

    int check_win();
    inline constexpr int get(int idx) const { return (u >> (idx * 2)) & 0x3; }
    inline constexpr void set(int idx, int val) {
        u &= ~(0x3 << (idx * 2));
        u |= uint32(val) << (idx * 2);
    }
};

inline state final_state[] = {
    state("xxx      "), state("   xxx   "), state("      xxx"),
    state("x  x  x  "), state(" x  x  x "), state("  x  x  x"),
    state("x   x   x"), state("  x x x  "),
};

inline int state::check_win() {
    for (int i = 0; i < 8; i++) {
        if ((final_state[i].u & u) == final_state[i].u) return 1;
        if (((final_state[i].u << 1) & u) == (final_state[i].u << 1)) return -1;
    }
    return 0;
}

#include <iostream>
#include <map>
#include <utility>

void print_state(state st) {
  for (int i = 0; i < 9; i++) {
    if (st.get(i) == 0)
      std::cout << i << " ";
    else if (st.get(i) == 1)
      std::cout << "X ";
    else
      std::cout << "O ";
    if (i % 3 == 2)
      std::cout << std::endl;
  }
  std::cout << std::endl;
}

std::map<state, double> memo;

double dfs(state st, bool current_x) {
  if (memo.find(st) != memo.end())
    return memo[st];
  int res = st.check_win();
  if (res != 0) {
    if (res == 1)
      return memo[st] = 1;
    else
      return memo[st] = 0;
  }
  if (current_x) {
    // X's turn
    // Choose the best move
    double best = 0;
    for (int i = 0; i < 9; i++) {
      if (st.get(i) == 0) {
        state new_st = st;
        new_st.set(i, 1);
        best = std::max(best, dfs(new_st, false));
      }
    }
    return memo[st] = best;
  } else {
    // O's turn
    // Prevent X from instantly winning, otherwise move in equal probability
    double total = 0;
    int cnt = 0;
    for (int i = 0; i < 9; i++) {
      if (st.get(i) == 0) {
        state new_st = st;
        new_st.set(i, 1);
        if (new_st.check_win() == 1) {
          new_st.set(i, 2);
          return memo[st] = dfs(new_st, true);
        }
        new_st.set(i, 2);
        total += dfs(new_st, true);
        cnt++;
      }
    }
    return memo[st] = total / cnt;
  }
}

int main() {
  state st("x   o    ");
  dfs(st, true);
  for (int i = 0; i < 9; i++) {
    if (st.get(i) == 0) {
      state new_st = st;
      new_st.set(i, 1);
      print_state(new_st);
      std::cout << "Winning probability: " << memo[new_st] << std::endl;
    }
  }
}