Play 1xN Go minmax dirty and possibly buggy implementation

play1n.cc

#include <algorithm>
#include <cstdlib>
#include <iomanip>
#include <iostream>
#include <set>
#include <string>
#include <vector>

using namespace std;

constexpr int inf = 999999;

inline char opturn(char c) { return c == 'B' ? 'W' : 'B'; }

pair<int, int> score(string s) {
  char l = '-';
  int k = 0, b = 0, w = 0;
  for (int i = 0; i < s.size(); ++i) {
    switch (s[i]) {
      case '-':
        ++k;
        break;
      case 'B':
        if (l == '-') { b += k+1; }
        else if (l == 'B') { b += k+1; }
        else b++;
        l = 'B';
        k = 0;
        break;
      case 'W':
        if (l == '-') { w += k+1; }
        else if (l == 'W') { w += k+1; }
        else w++;
        l = 'W';
        k = 0;
        break;
    }
  }
  if (k > 0) {
    if (l == 'B') b += k;
    else if (l == 'W') w += k;
  }
  return {b, w};
}

inline bool captured(const string& s, int i, int j) {
    return (i == 0 || s[i-1] != '-') && (j == s.size()-1 || s[j+1] != '-');
}

string removeDead(string s, char turn) {
  int l = -1;
  bool bcap = false, wcap = false;
  for (int i = 0; i < s.size(); ++i) {
    if (s[i] != '-') {
      if (l == -1) l = i;
      else if (s[l] != s[i]) {
          // process group [l..i-1]
          if (captured(s, l, i-1)) {
            if (s[l] == 'B') bcap = true;
            if (s[l] == 'W') wcap = true;
            if (s[l] != turn) fill(s.begin()+l, s.begin()+i, 'x');
          }
          l = i;
      }
    } else if (l != -1) {
      // process group [l..i-1]
      if (captured(s, l, i-1)) {
        if (s[l] == 'B') bcap = true;
        if (s[l] == 'W') wcap = true;
        if (s[l] != turn) fill(s.begin()+l, s.begin()+i, 'x');
      }
      l = -1;
    }
  }
  if (l != -1) {
    // process group [l..s.size()-1]
    if (captured(s, l, s.size()-1)) {
      if (s[l] == 'B') bcap = true;
      if (s[l] == 'W') wcap = true;
      if (s[l] != turn) fill(s.begin()+l, s.begin()+s.size(), 'x');
    }
  }
  // suicide
  if (turn == 'B' && bcap && !wcap) return "";
  if (turn == 'W' && wcap && !bcap) return "";

  for (int i = 0; i < s.size(); ++i) if (s[i] == 'x') s[i] = '-';
  return s;
}

string stateStr(vector<int>& mvs) {
    string s;
    for (int mv : mvs) {
        if (mv == -1) s += "p";
        else s += to_string(mv);
    }
    return s;
}

pair<int, int> genmove(string s, char turn, set<string>& seen, vector<int>& mvs) {
  int mv = -1;
  int best = turn == 'B' ? -inf : +inf;

  // pass
  {
    mvs.push_back(-1);
    int val;
    if (mvs.size() > 1 && mvs[mvs.size() - 2] == -1) {
        const auto [b, w] = score(s);
        val = b - w;
    } else {
        val = genmove(s, opturn(turn), seen, mvs).second;
    }
    if (turn == 'B' && best < val) {
        mv = -1;
        best = val;
    } else if (turn == 'W' && best > val) {
        mv = -1;
        best = val;
    }
    mvs.pop_back();
  }

  if (turn == 'B' && best > 0) return {mv, best};
  if (turn == 'W' && best < 0) return {mv, best};

  for (int i = 0; i < s.size(); ++i) {
    if (s[i] != '-') continue;

    s[i] = turn;

    const string t = removeDead(s, turn);
    if (!t.empty() && !seen.count(t)) {
        seen.insert(t);
        mvs.push_back(i);
        const auto [j, val] = genmove(t, opturn(turn), seen, mvs);
        if (turn == 'B' && best < val) {
            mv = i;
            best = val;
        } else if (turn == 'W' && best > val) {
            mv = i;
            best = val;
        }
        mvs.pop_back();
        seen.erase(t);
    }

    s[i] = '-';

    if (turn == 'B' && best > 0) return {mv, best};
    if (turn == 'W' && best < 0) return {mv, best};
  }

  return {mv, best};
}

int main(int argc, char *argv[]) {
  if (argc != 2) {
    cout << "usage: play1n <size>" << endl;
    return 1;
  }

  const int n = atoi(argv[1]);
  string board(n, '-');

  set<string> seen;
  vector<int> moves;
  seen.insert(board);

  char turn = 'B';
  while (moves.size() < 2 || moves.back() != -1 || moves[moves.size()-2] != -1) {
    const auto [mv, score] = genmove(board, turn, seen, moves);
    cout << "move " << setw(2) << moves.size()+1 << ": " << board << endl;
    if (mv != -1) board[mv] = turn;
    seen.insert(board);
    moves.push_back(mv);
    turn = opturn(turn);
  }

  {
    const auto [b, w] = score(board);
    cout << "res: ";
    if (b > w) cout << "B+" << b-w;
    else if (w > b) cout << "W+" << w-b;
    else cout << "Draw";
    cout << endl;
  }

  return 0;
}