Skip to content

Instantly share code, notes, and snippets.

@maghoff
Created November 25, 2014 20:59
Show Gist options
  • Save maghoff/317e670219fc9c3fdfc2 to your computer and use it in GitHub Desktop.
Save maghoff/317e670219fc9c3fdfc2 to your computer and use it in GitHub Desktop.
An AI for tic-tac-toe
#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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment