# Tic-tac-toe in SQL with optimal AI

The simplest introduction to this code is to play it! Here's an SQL Fiddle. However, to enjoy it fully, you'll need a more interactive environment, like the psql command prompt. If you don't have PostgreSQL installed already, this may be the killer app that makes you want to install it.

## Capabilities

• Manually make a move for player X, then view the board:

psql=> INSERT INTO tictactoe VALUES ('X', 3, 2);
INSERT 0 1
psql=> SELECT * FROM board;
row | 1 | 2 | 3
-----+---+---+---
1 |   |   |
2 |   |   |
3 |   | X |
(3 rows)

• See the AI analysis for player O:

psql=> SELECT * FROM strategy WHERE sym = 'O';
sym | row | col | offense_reason | offense_score | defense_reason | defense_score | corner_center_response | corner_fork_defense | opposite_corner_offense | corner_offense | priority
-----+-----+-----+----------------+---------------+----------------+---------------+------------------------+---------------------+-------------------------+----------------+----------
O   |   3 |   1 |                |             0 | {"row 3"}      |             1 | f                      | f                   |                         | t              |        1
O   |   3 |   3 |                |             0 | {"row 3"}      |             1 | f                      | f                   |                         | t              |        1
O   |   1 |   2 |                |             0 | {"col 2"}      |             1 | f                      | f                   | f                       | f              |        3
O   |   2 |   2 |                |             0 | {"col 2"}      |             1 | f                      | f                   | f                       | f              |        3
O   |   1 |   3 |                |             0 |                |             0 | f                      | f                   |                         | t              |        5
O   |   1 |   1 |                |             0 |                |             0 | f                      | f                   |                         | t              |        5
O   |   2 |   1 |                |             0 |                |             0 | f                      | f                   | f                       | f              |        7
O   |   2 |   3 |                |             0 |                |             0 | f                      | f                   | f                       | f              |        7
(8 rows)


All legal moves are listed. Moves with priority 1 are the best. Here, it is recommending that O play either of the bottom corners, to defend against X winning on row 3. It chooses those over any the options in column two due to a slight preference for corners (corner_offense = true).

• Automatically make an optimal move by choosing the first row shown in the strategy.

psql=> SELECT * FROM make_best_move('O');
row | 1 | 2 | 3
-----+---+---+---
1 |   |   |
2 |   |   |
3 | O | X |
(3 rows)

• To detect if a player has won:

psql=> SELECT * FROM winner;

• To view the history of moves:

psql=> SELECT * FROM tictactoe ORDER BY seq;

• To start over:

psql=> TRUNCATE tictactoe;
TRUNCATE TABLE


### Sample game 1: AI vs. AI

Let's just let the AI play against itself.

psql=> TRUNCATE tictactoe;
TRUNCATE TABLE
psql=> SELECT * FROM make_best_move('X');
row | 1 | 2 | 3
-----+---+---+---
1 |   |   |
2 |   |   |
3 |   |   | X
(3 rows)

psql=> SELECT * FROM make_best_move('O');
row | 1 | 2 | 3
-----+---+---+---
1 |   |   |
2 |   | O |
3 |   |   | X
(3 rows)

psql=> SELECT * FROM make_best_move('X');
row | 1 | 2 | 3
-----+---+---+---
1 | X |   |
2 |   | O |
3 |   |   | X
(3 rows)

psql=> SELECT * FROM make_best_move('O');
row | 1 | 2 | 3
-----+---+---+---
1 | X |   |
2 |   | O | O
3 |   |   | X
(3 rows)

psql=> SELECT * FROM make_best_move('X');
row | 1 | 2 | 3
-----+---+---+---
1 | X |   |
2 | X | O | O
3 |   |   | X
(3 rows)

psql=> SELECT * FROM make_best_move('O');
row | 1 | 2 | 3
-----+---+---+---
1 | X |   |
2 | X | O | O
3 | O |   | X
(3 rows)

psql=> SELECT * FROM make_best_move('X');
row | 1 | 2 | 3
-----+---+---+---
1 | X |   | X
2 | X | O | O
3 | O |   | X
(3 rows)

psql=> SELECT * FROM make_best_move('O');
row | 1 | 2 | 3
-----+---+---+---
1 | X | O | X
2 | X | O | O
3 | O |   | X
(3 rows)

psql=> SELECT * FROM make_best_move('X');
row | 1 | 2 | 3
-----+---+---+---
1 | X | O | X
2 | X | O | O
3 | O | X | X
(3 rows)


As expected, the game ends in a draw.

### Sample game 2: Human vs. AI

Let X be a human player, who goes first.

psql=> TRUNCATE tictactoe;
TRUNCATE TABLE
psql=> INSERT INTO tictactoe VALUES ('X', 2, 2);
INSERT 0 1
psql=> SELECT * FROM make_best_move('O');
row | 1 | 2 | 3
-----+---+---+---
1 |   |   |
2 |   | X |
3 |   |   | O
(3 rows)

psql=> INSERT INTO tictactoe VALUES ('X', 3, 1);
psql=> SELECT * FROM board;
row | 1 | 2 | 3
-----+---+---+---
1 |   |   |
2 |   | X |
3 | X |   | O
(3 rows)
psql=> SELECT * FROM strategy WHERE sym = 'O';
sym | row | col | offense_reason | offense_score |  defense_reason   | defense_score | corner_center_response | corner_fork_defense | opposite_corner_offense | corner_offense | priority
-----+-----+-----+----------------+---------------+-------------------+---------------+------------------------+---------------------+-------------------------+----------------+----------
O   |   1 |   3 | {"col 3"}      |             1 | {/}               |             2 | f                      | f                   | f                       | t              |        1
O   |   1 |   1 | {"\\"}         |             1 | {"\\","col 1"}    |             1 | f                      | f                   | t                       | t              |        2
O   |   2 |   3 | {"col 3"}      |             1 | {"row 2"}         |             1 | f                      | f                   | f                       | f              |        3
O   |   1 |   2 |                |             0 | {"col 2"}         |             1 | f                      | f                   | f                       | f              |        4
O   |   2 |   1 |                |             0 | {"row 2","col 1"} |             1 | f                      | f                   | f                       | f              |        4
O   |   3 |   2 |                |             0 | {"col 2"}         |             1 | f                      | f                   | f                       | f              |        4
(6 rows)


The AI is choosing the NE corner, because the opponent has two marks along the ╱ diagonal (defense_reason = '/', defense_score = 2). It also notices that that would help its own existing mark in the right column (offense_reason = 'col 3', offense_score = 1), though that's not its primary concern.

psql=> SELECT * FROM make_best_move('O');
row | 1 | 2 | 3
-----+---+---+---
1 |   |   | O
2 |   | X |
3 | X |   | O
(3 rows)

psql=> INSERT INTO tictactoe VALUES ('X', 1, 1);
INSERT 0 1
psql=> SELECT * FROM board;
row | 1 | 2 | 3
-----+---+---+---
1 | X |   | O
2 |   | X |
3 | X |   | O
(3 rows)

psql=> SELECT * FROM strategy WHERE sym = 'O';
sym | row | col | offense_reason | offense_score |  defense_reason   | defense_score | corner_center_response | corner_fork_defense | opposite_corner_offense | corner_offense | priority
-----+-----+-----+----------------+---------------+-------------------+---------------+------------------------+---------------------+-------------------------+----------------+----------
O   |   2 |   3 | {"col 3"}      |             2 | {"row 2"}         |             1 | f                      | t                   | f                       | f              |        1
O   |   2 |   1 |                |             0 | {"row 2","col 1"} |             2 | f                      | t                   | f                       | f              |        2
O   |   1 |   2 |                |             0 | {"col 2"}         |             1 | f                      | t                   | f                       | f              |        3
O   |   3 |   2 |                |             0 | {"col 2"}         |             1 | f                      | t                   | f                       | f              |        3
(4 rows)


The human made a blunder. The AI will see its winning opportunity (offense_reason = 'col 3', offense_score = 2).

psql=> SELECT * FROM make_best_move('O');
row | 1 | 2 | 3
-----+---+---+---
1 | X |   | O
2 |   | X | O
3 | X |   | O
(3 rows)

psql=> SELECT * FROM winner;
sym |  how
-----+-------
O   | col 3
(1 row)


## The code

CREATE TABLE tictactoe
( sym CHAR(1) NOT NULL
, row INTEGER NOT NULL
, col INTEGER NOT NULL
, seq SERIAL NOT NULL
, PRIMARY KEY (row, col)
);

CREATE OR REPLACE VIEW players AS
SELECT unnest(array['X', 'O']) AS sym;

CREATE OR REPLACE VIEW all_coords AS
SELECT *
FROM
generate_series(1, 3) AS row
CROSS JOIN
generate_series(1, 3) AS col;

CREATE OR REPLACE VIEW board AS
SELECT row.row
, coalesce(col1.sym, ' ') AS "1"
, coalesce(col2.sym, ' ') AS "2"
, coalesce(col3.sym, ' ') AS "3"
FROM generate_series(1, 3) AS row
LEFT OUTER JOIN tictactoe AS col1
ON row.row = col1.row AND col1.col = 1
LEFT OUTER JOIN tictactoe AS col2
ON row.row = col2.row AND col2.col = 2
LEFT OUTER JOIN tictactoe AS col3
ON row.row = col3.row AND col3.col = 3;

CREATE OR REPLACE VIEW score AS
SELECT sym
, 'row' AS dir
, row AS major
, array_agg(row) AS rows
, array_agg(col) AS cols
, count(sym) AS n
FROM tictactoe
GROUP BY sym, row
UNION ALL
SELECT sym
, 'col' AS dir
, col AS major
, array_agg(row) AS rows
, array_agg(col) AS cols
, count(sym) AS n
FROM tictactoe
GROUP BY sym, col
UNION ALL
SELECT sym
, E'\\' AS dir
, 0 AS major
, array_agg(row) AS rows
, array_agg(col) AS cols
, count(sym) AS n
FROM tictactoe
WHERE row = col
GROUP BY sym
UNION ALL
SELECT sym
, '/' AS dir
, 0 AS major
, array_agg(row) AS rows
, array_agg(col) AS cols
, count(sym) AS n
FROM tictactoe
WHERE row + col = 4
GROUP BY sym;

CREATE OR REPLACE VIEW winner AS
SELECT sym
, dir || CASE WHEN major IS NOT NULL THEN ' ' || major ELSE '' END AS how
FROM score
WHERE n = 3;

-- ----------------------------------------------------------------------
-- Artificial Intelligence
-- ----------------------------------------------------------------------
CREATE OR REPLACE VIEW assessment AS
SELECT offense.sym
, offense.dir
, offense.major
, offense.rows
, offense.cols
, offense.n AS offense_n
, coalesce(defense.n, 0) AS defense_n
FROM score AS offense
LEFT OUTER JOIN score AS defense
ON offense.sym <> defense.sym
AND offense.dir = defense.dir
AND offense.major = defense.major;

CREATE OR REPLACE VIEW offense AS
WITH rowcol AS (
SELECT generate_series(1, 3) AS missing_minor
), row_analysis AS (
SELECT sym, 'row ' || major AS reason, dir AS axis, major, missing_minor, offense_n, defense_n
FROM rowcol
CROSS JOIN (SELECT unnest(cols) AS minor, * FROM assessment) AS assessment
WHERE dir = 'row' AND defense_n = 0
GROUP BY missing_minor, sym, dir, major, offense_n, defense_n
HAVING count(CASE WHEN minor = missing_minor THEN 1 END) = 0
), col_analysis AS (
SELECT sym, 'col ' || major AS reason, dir AS axis, major, missing_minor, offense_n, defense_n
FROM rowcol
CROSS JOIN (SELECT unnest(rows) AS minor, * FROM assessment) AS assessment
WHERE dir = 'col' AND defense_n = 0
GROUP BY missing_minor, sym, dir, major, offense_n, defense_n
HAVING count(CASE WHEN minor = missing_minor THEN 1 END) = 0
), main_diagonal_analysis AS (
SELECT sym, CAST(E'\\' AS TEXT) AS reason, CAST('row' AS TEXT) AS axis, missing_minor AS major, missing_minor, offense_n, defense_n
FROM rowcol
CROSS JOIN (SELECT unnest(rows) AS minor, * FROM assessment) AS assessment
WHERE dir = E'\\' AND defense_n <= 1
GROUP BY missing_minor, sym, dir, offense_n, defense_n
HAVING count(CASE WHEN minor = missing_minor THEN 1 END) = 0
), alt_diagonal_analysis AS (
SELECT sym, CAST('/' AS TEXT) AS reason, CAST('row' AS TEXT) AS axis, missing_minor AS major, 4 - missing_minor AS missing_minor, offense_n, defense_n
FROM rowcol
CROSS JOIN (SELECT unnest(rows) AS minor, * FROM assessment) AS assessment
WHERE dir = E'/' AND defense_n <= 1
GROUP BY missing_minor, sym, dir, offense_n, defense_n
HAVING count(CASE WHEN minor = missing_minor THEN 1 END) = 0
), unnormalized_analysis AS (
-- "major" is the axis ('row' or 'col') along which we are analyzing.
-- "minor" is the other axis.
SELECT * FROM row_analysis
UNION ALL
SELECT * FROM col_analysis
UNION ALL
SELECT * FROM main_diagonal_analysis
UNION ALL
SELECT * FROM alt_diagonal_analysis
), normalized_analysis AS (
-- Convert "major" and "minor" to rows and cols.
SELECT sym, reason, major AS row, missing_minor AS col, offense_n, defense_n
FROM unnormalized_analysis
WHERE axis = 'row'
UNION ALL
SELECT sym, reason, missing_minor AS row, major AS col, offense_n, defense_n
FROM unnormalized_analysis
WHERE axis = 'col'
)
SELECT sym, row, col, array_agg(reason) AS reason, max(offense_n) AS score
FROM normalized_analysis
GROUP BY sym, row, col
ORDER BY sym, max(offense_n) DESC, sum(offense_n) DESC;

CREATE OR REPLACE VIEW defense AS
SELECT players.sym
, opponent.row
, opponent.col
, opponent.reason
, opponent.score
FROM players
INNER JOIN offense AS opponent
ON players.sym <> opponent.sym
WHERE NOT EXISTS (
SELECT sym
)
ORDER BY players.sym DESC, score DESC;

CREATE OR REPLACE VIEW strategy AS
WITH counts AS (
SELECT players.sym
, coalesce(count(CASE WHEN row <> 2 AND col <> 2 THEN 1 END), 0) AS corner_count
FROM players
LEFT OUTER JOIN tictactoe
ON players.sym = tictactoe.sym
GROUP BY players.sym
), summary AS (
SELECT players.sym
, rc.row
, rc.col
, offense.reason AS offense_reason
, coalesce(offense.score, 0) AS offense_score
, defense.reason AS defense_reason
, coalesce(defense.score, 0) AS defense_score
FROM players
CROSS JOIN all_coords AS rc
LEFT OUTER JOIN offense
ON players.sym = offense.sym
AND rc.row = offense.row AND rc.col = offense.col
LEFT OUTER JOIN defense
ON players.sym = defense.sym
AND rc.row = defense.row AND rc.col = defense.col
WHERE NOT EXISTS (
SELECT sym
)
), heuristics AS (
SELECT summary.*
, (defense_reason @> array[E'\\'] OR defense_reason @> array['/'])
AND row = 2 AND col = 2 AS corner_center_response
, opponent.corner_count = 2
AND (row = 2 OR col = 2) AS corner_fork_defense
, (offense_reason @> array[E'\\'] OR offense_reason @> array['/'])
AND row <> 2 AND col <> 2 AS opposite_corner_offense
, row <> 2 AND col <> 2 AS corner_offense
FROM summary
LEFT OUTER JOIN counts AS opponent
ON summary.sym <> opponent.sym
)
SELECT *
, rank() OVER (
PARTITION BY sym
ORDER BY offense_score = 2 DESC     -- Go for an immediate win
, defense_score = 2 DESC     -- Else don't lose
, offense_score DESC         -- Else make best progress
, defense_score DESC         -- Tie-break offensive moves
--   by considering defense

-- Corner center response: 'O' to play on
--
--   X| |
--   -+-+-
--    | |
--   -+-+-
--    | |
--
-- 'O' must play center, else 'X' will take another two corners
-- and win.
, coalesce(corner_center_response, FALSE) DESC

-- Corner center response: 'O' to play on
--
--   X| |
--   -+-+-
--    |O|
--   -+-+-
--    | |X
--
-- 'O' must play any edge, else 'X' will take another corner
-- and win.
, coalesce(corner_fork_defense, FALSE) DESC

-- Corner center response: 'X' to play on
--
--   X| |
--   -+-+-
--    |O|
--   -+-+-
--    | |
--
-- Prefer the opposite (SE) corner, which creates
-- opportunities for the forks illustrated above.
, coalesce(opposite_corner_offense, FALSE) DESC

-- Prefer corners in general.
, coalesce(corner_offense, FALSE) DESC
) AS priority
FROM heuristics
ORDER BY sym
, priority;

CREATE OR REPLACE VIEW best_move AS
WITH strategy_pick AS (
SELECT *, row_number() OVER (PARTITION BY sym) AS pick
FROM strategy
WHERE priority = 1
)
SELECT sym, row, col
FROM strategy_pick
WHERE pick = 1;

CREATE OR REPLACE FUNCTION make_best_move(CHAR(1))
RETURNS TABLE("row" INTEGER, "1" CHAR(1), "2" CHAR(1), "3" CHAR(1)) AS
$$INSERT INTO tictactoe SELECT * FROM best_move WHERE sym = 1; SELECT * FROM board;$$ LANGUAGE SQL;


## Concerns

Is every move optimal? Could the heuristics ("corner center defense", "corner_fork_defense", "opposite corner offense", "corner offense") be improved or simplified? Is it possible to reduce reliance on such heuristics? This approach doesn't scale to larger boards, such as 4 × 4.

Could the views be simplified or made easier to understand?

The use of arrays, and functions like array_agg() and unnest() make me feel dirty. That's not what they taught me in school about relational database theory, and it doesn't seem portable. Your thoughts?

• I just wanna say this is amazing – IEatBagels May 16 '18 at 13:17