15
\$\begingroup\$

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
                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?

\$\endgroup\$
  • 1
    \$\begingroup\$ I just wanna say this is amazing \$\endgroup\$ – IEatBagels May 16 '18 at 13:17
3
\$\begingroup\$

In general, I have to say: "fascinating". I'm not the best SQL coder out there, but I'm pretty good at games, so I'm going to dare respond to at least one of your questions.

You asked about scaling some of the heuristics. One thing I did not see in your code is a move tree. With 3x3, you can calculate all possible positions and find out which moves would not lose and give your opponent a chance to lose. That sort of construct should scale to larger boards easier (although it may be slower to calculate, it would be trivially fast to play), and gets rid of the heuristics that are artifacts of the 3x3 game.

With 3x3 (and maybe 4x4), you may be able to think about what chess calls an endgame database as well. You may have to put in the concept of rotation and mirrored boards to get the 4x4 down to a reasonable size (I think I came up with 8 million rows). by the time you get to 5x5, you are playing a variation of gomoku, and the first player to move basically wins. You may be interested in Connect6 for something a bit more fair.

Another thought that may be interesting is the concept of "optimal". In drawish games like this, it may not be optimal to play the same sequence that you have played before against the same opponent if the opponent has already drawn the game. For example, there is still a 6x6 Othello/Reversi championship, even though the game has been "solved" by computers. However, since most top players know the "optimal" lines, the key to winning is sometimes making an "inferior" (but perhaps still winning) move, to get the other player into a line that you know more about then your opponent. Top chess players do something similar.

Therefore, the suggestion is to either put a small random factor among the moves that still give you a chance to win without risking losing, or, perhaps better, remember what lines were played previously and go down a different path. You do want to stay within "potentially winning" lines that have no chance of losing, though.

\$\endgroup\$
  • \$\begingroup\$ Thanks for your observations. They are certainly valid for typical programming languages. However, I have to think about what is reasonably achievable within SQL. \$\endgroup\$ – 200_success Jun 29 '14 at 20:03
  • \$\begingroup\$ Fair enough. Well done, anyway. In my experience, portable SQL is difficult and slow, so using array_agg() and unnest() are perfectly allowed. There are ways to do this in other databases, but they sometimes involve writing more code (or writing the stored procedures / functions yourself), so it is perfectly fine to use the tools that are given to you. \$\endgroup\$ – Guy Schalnat Jul 1 '14 at 1:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.