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
Oplay either of the bottom corners, to defend againstXwinning 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
FROM tictactoe AS already
WHERE already.row = opponent.row AND already.col = opponent.col
)
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
FROM tictactoe AS already
WHERE already.row = rc.row AND already.col = rc.col
)
), 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?
