6x6nim.cpp

#include <bitset>
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
const int N = 6;
vector<bool> s;
void save() {
    cout << "saving database..." << endl;
    int begin_time = clock();
    ofstream fout("bitset.sav", ios::out | ios::binary);
    std::vector<bool>::size_type n = s.size();
    fout.write((const char*)&n, sizeof(std::vector<bool>::size_type));
    for (std::vector<bool>::size_type i = 0; i < n;)
    {
        unsigned long long aggr = 0;
        for (unsigned long long mask = 1; mask > 0 && i < n; ++i, mask <<= 1)
            if (s.at(i))
                aggr |= mask;
        fout.write((const char*)&aggr, sizeof(unsigned long long));
    }
    fout.close();
    int end_time = clock();
    cout << "save database ok. cost time = " << end_time - begin_time << " ms." << endl;
}

void load() {
    cout << "reading database..." << endl;
    int begin_time = clock();
    ifstream fin("bitset.sav", ios::out | ios::binary);
    std::vector<bool>::size_type n;
    fin.read((char*)&n, sizeof(std::vector<bool>::size_type));
    s.resize(n);

    constexpr size_t buffer_size = 256 * 1024 * 1024;
    unique_ptr<char[]> buffer(new char[buffer_size]);
    size_t bits = 0;
    while (fin)
    {
        fin.read(buffer.get(), buffer_size);
        for (size_t i = 0; i < buffer_size; i++) {
            for (unsigned char mask = 1; mask > 0 && bits < n; ++bits, mask <<= 1) {
                s.at(bits) = buffer[i] & mask;
            }
        }
    }
    fin.close();
    int end_time = clock();
    cout << "read database ok. cost time = " << end_time - begin_time << " ms." << endl;
}

void solve() {
    s.resize(1ll << (N * N));
    s[0] = false;  // last move player win. 
   // s[0] = true;  // last move player lose.
    for (size_t state = 1; state < 1ll << (N*N); state++) {
        if (state % (1 << 24) == 0) {
            cout << state << " iterations completed." << endl;
        }
#define val(x, y) ((bool)(state&(1ll<<((x)*N+y))))
#define xor(z, x, y) ((z)^(1ll<<((x)*N+y)))
#define par(x) if(!s[x]) { s[state]=true; goto nxt; }
#define tes(x) (s[x])
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (val(i, j)) {
                    auto rem = xor (state, i, j);
                    par(rem);
                    auto r = rem;
                    for (int k = 1; i + k < N; k++) {
                        if (val(i + k, j)) {
                            r = xor (r, i + k, j);
                            par(r);
                        }
                        else break;
                    }
                    r = rem;
                    for (int k = 1; j + k < N; k++) {
                        if (val(i, j + k)) {
                            r = xor (r, i, j + k);
                            par(r);
                        }
                        else break;
                    }
                    r = rem;
                    for (int k = 1; i + k < N && j + k < N; k++) {
                        if (val(i + k, j + k)) {
                            r = xor (r, i + k, j + k);
                            par(r);
                        }
                        else break;
                    }
                    r = rem;
                    for (int k = 1; i - k >= 0 &&  j + k < N; k++) {
                        if (val(i - k, j + k)) {
                            r = xor (r, i - k, j + k);
                            par(r);
                        }
                        else break;
                    }
                }
            }
        }
    nxt:;
    }
    save();
}

void use() {
    load();
    while (true) {
        size_t state = (1ll << (N * N)) - 1;
        while (state > 0) {
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if (val(i, j)) {
                        printf(". ");
                    }
                    else {
                        printf("o ");
                    }
                }
                putchar('\n');
            }
            printf("sg = %d\n", (int)(tes(state)));
            if (tes(state)) {
                for (int i = 0; i < N; i++) {
                    for (int j = 0; j < N; j++) {
                        if (val(i, j)) {
                            auto rem = xor (state, i, j);
                            if (!tes(rem)) {
                                printf("win: %d, %d, %d, %d\n", i, j, i, j);
                            }
                            auto r = rem;
                            for (int k = 1; i + k < N; k++) {
                                if (val(i + k, j)) {
                                    r = xor (r, i + k, j);
                                    if (!tes(r)) {
                                        printf("win: %d, %d, %d, %d\n", i, j, i + k, j);
                                    }
                                }
                                else break;
                            }
                            r = rem;
                            for (int k = 1; j + k < N; k++) {
                                if (val(i, j + k)) {
                                    r = xor (r, i, j + k);
                                    if (!tes(r)) {
                                        printf("win: %d, %d, %d, %d\n", i, j, i, j + k);
                                    }
                                }
                                else break;
                            }
                            r = rem;
                            for (int k = 1; i + k < N && j + k < N; k++) {
                                if (val(i + k, j + k)) {
                                    r = xor (r, i + k, j + k);
                                    if (!tes(r)) {
                                        printf("win: %d, %d, %d, %d\n", i, j, i + k, j + k);
                                    }
                                }
                                else break;
                            }
                            r = rem;
                            for (int k = 1; i -k >= 0 && j + k < N; k++) {
                                if (val(i - k, j + k)) {
                                    r = xor (r, i - k, j + k);
                                    if (!tes(r)) {
                                        printf("win: %d, %d, %d, %d\n", i, j, i - k, j + k);
                                    }
                                }
                                else break;
                            }
                        }
                    }
                }
            }
            int a, b, c, d;
            cin >> a >> b >> c >> d;
            for (int i = a, j = b;; (i < c ? i++ : i > c ? i-- : 0), (j < d ? j++ : j > d ? j-- : 0)) {
                state = xor (state, i, j);
                if (i == c && j == d)break;
            }
        }
    }
}

int main() {
    // solve();
    use();
    return 0;
}