An AI for tic-tac-toe

tictactoe.cpp

#include <iostream>
#include <array>
#include <vector>
#include <algorithm>
#include <random>


constexpr int pow3(int n) {
	if (n == 0) return 1;
	else return 3 * pow3(n-1);
}


enum field { N=0, X=1, O=2 };

std::ostream& operator << (std::ostream& out, field f) {
	switch (f) {
		case N: out << ' '; break;
		case X: out << 'x'; break;
		case O: out << 'o'; break;
	}
	return out;
}


class board {
public:
	unsigned short d = 0;

	constexpr board() = default;
	constexpr board(unsigned short d_) : d(d_) {}

	constexpr field operator[] (const int pos) const {
		auto x = d;
		return static_cast<field>((x / pow3(pos)) % 3);
	}

	// Assign to a field in the board. Return the new board
	// Precondition: The given field must be empty
	constexpr board with(const int pos, const field f) const {
		auto y = static_cast<decltype(d)>(f);
		return board(d + y * pow3(pos));
	}
};

std::ostream& operator << (std::ostream& out, const board& b) {
	out.write("+---+\n", 6);
	for (int y=0; y<3; ++y) {
		out << '|';
		for (int x=0; x<3; ++x) out << b[y*3+x];
		out.write("|\n", 2);
	}
	out.write("+---+", 5);

	return out;
}


constexpr static int streaks[][3] = {
	{ 0, 1, 2 },
	{ 3, 4, 5 },
	{ 6, 7, 8 },

	{ 0, 3, 6 },
	{ 1, 4, 7 },
	{ 2, 5, 8 },

	{ 0, 4, 8 },
	{ 2, 4, 6 },
};

constexpr field find_winner(board b) {
	for (auto streak : streaks) {
		if (b[streak[0]] == N) continue;
		if ((b[streak[0]] == b[streak[1]]) && 
			(b[streak[1]] == b[streak[2]]))
			return b[streak[0]];
	}
	return N;
}

constexpr bool finished(board b) {
	bool has_room = false;
	for (int i = 0; i < 9; ++i) {
		has_room |= (b[i] == N);
	}

	if (!has_room) return true;
	if (find_winner(b) != N) return true;

	return false;
}

constexpr field other_player(field player) {
	if (player == X) return O;
	else return X;
}

constexpr unsigned char calc_score(board b, field player, field to_play) {
	auto winner = find_winner(b);
	if (winner != N) return (winner == player) ? 2 : 0;

	bool any_moves = false;
	int max_score = 0, min_score = 2;
	for (int pos = 0; pos < 9; ++pos) {
		if (b[pos] != N) continue;
		any_moves = true;

		auto recursive_score = calc_score(b.with(pos, to_play), player, other_player(to_play));
		if (recursive_score > max_score) max_score = recursive_score;
		if (recursive_score < min_score) min_score = recursive_score;
	}
	if (!any_moves) return 1;

	return (player == to_play) ? max_score : min_score;
}


constexpr unsigned char calc_score(board b) {
	int xs = 0;
	for (int i=0; i<9; ++i) {
		auto f = b[i];
		if (f == X) xs++;
		else if (f == O) xs--;
	}

	auto to_play = (xs & 1) ? O : X;
	auto interested_player = (xs & 1) ? X : O;

	return calc_score(b, interested_player, to_play);
}


template<std::size_t... Is> struct seq{};
template<std::size_t N, std::size_t... Is>
struct gen_seq : gen_seq<N-1, N-1, Is...>{};
template<std::size_t... Is>
struct gen_seq<0, Is...> : seq<Is...>{};

template<class Generator, std::size_t... Is>
constexpr auto generate_array_helper(Generator g, seq<Is...>)
	-> std::array<decltype(g(std::size_t{}, sizeof...(Is))), sizeof...(Is)>
{
    return {{g(Is, sizeof...(Is))...}};
}

template<std::size_t tcount, class Generator>
constexpr auto generate_array(Generator g)
	-> decltype( generate_array_helper(g, gen_seq<tcount>{}) )
{
    return generate_array_helper(g, gen_seq<tcount>{});
}

template <int Begin>
constexpr unsigned char my_generator(std::size_t curr, std::size_t total)
{
    return calc_score(board(curr + Begin));
}


struct {
	std::array<unsigned char, 1024> scores    = generate_array<1024>(my_generator<0>);
	std::array<unsigned char, 1024> scores_02 = generate_array<1024>(my_generator<1024>);
	std::array<unsigned char, 1024> scores_03 = generate_array<1024>(my_generator<2048>);
	std::array<unsigned char, 1024> scores_04 = generate_array<1024>(my_generator<3072>);
	std::array<unsigned char, 1024> scores_05 = generate_array<1024>(my_generator<4096>);
	std::array<unsigned char, 1024> scores_06 = generate_array<1024>(my_generator<5120>);
	std::array<unsigned char, 1024> scores_07 = generate_array<1024>(my_generator<6144>);
	std::array<unsigned char, 1024> scores_08 = generate_array<1024>(my_generator<7168>);
	std::array<unsigned char, 1024> scores_09 = generate_array<1024>(my_generator<8192>);
	std::array<unsigned char, 1024> scores_10 = generate_array<1024>(my_generator<9216>);
	std::array<unsigned char, 1024> scores_11 = generate_array<1024>(my_generator<10240>);
	std::array<unsigned char, 1024> scores_12 = generate_array<1024>(my_generator<11264>);
	std::array<unsigned char, 1024> scores_13 = generate_array<1024>(my_generator<12288>);
	std::array<unsigned char, 1024> scores_14 = generate_array<1024>(my_generator<13312>);
	std::array<unsigned char, 1024> scores_15 = generate_array<1024>(my_generator<14336>);
	std::array<unsigned char, 1024> scores_16 = generate_array<1024>(my_generator<15360>);
	std::array<unsigned char, 1024> scores_17 = generate_array<1024>(my_generator<16384>);
	std::array<unsigned char, 1024> scores_18 = generate_array<1024>(my_generator<17408>);
	std::array<unsigned char,  227> scores_19 = generate_array< 227>(my_generator<18432>);
} calculated_scores;


template <class Rng>
int best_move(Rng& generator, board b, field player) {
	std::array<int, 9> scores;

	for (int pos=0; pos<9; ++pos) {
		if (b[pos] == N)
//			scores[pos] = calc_score(b.with(pos, player));
			scores[pos] = calculated_scores.scores[b.with(pos, player).d];
		else
			scores[pos] = -1;
	}

	int max = *std::max_element(scores.begin(), scores.end());

	std::vector<int> good_moves;
	for (int i=0; i<9; ++i) if (scores[i] == max) good_moves.push_back(i);

	std::uniform_int_distribution<int> distribution(0, good_moves.size() - 1);
	return good_moves[distribution(generator)];
}


int main() {
	std::default_random_engine generator(std::random_device{}());

	std::cout.sync_with_stdio(false);

	board b;

	for (;;) {
		std::cout << b << '\n';
		std::cout << "X's move: " << std::flush;
		auto move = best_move(generator, b, X);
		std::cout << move << std::endl;
		b = b.with(move, X);
		if (finished(b)) break;

		std::cout << b << '\n';
		std::cout << "O's move: " << std::flush;
		move = best_move(generator, b, O);
		std::cout << move << std::endl;
		b = b.with(move, O);
		if (finished(b)) break;
	}

	std::cout << b << '\n';

	auto winner = find_winner(b);
	if (winner == N) std::cout << "Tie" << std::endl;
	else std::cout << "Winner: " << winner << std::endl;

	return 0;
}