SQL & PL/SQL

Challenge (TL;DR)

For every unfinished position predict outcome if both players play optimally.

Challenge (Longer version)

If we number all cells from 1 to 9 then we can encode each sequence of moves.

For example, below game becomes 3175968.

Now, if we generate all possible sequences then they effectively fall into 3 main categories

• completed game
• game in progress
• incorrect sequence (for example, no moves allowed after someone wins)

Below draft returns all sequences along with derived category.

with
winning_ways(name, cells) as
(
    select 'h1', '123' from dual
    union all select 'h2', '456' from dual
    union all select 'h3', '789' from dual
    union all select 'v1', '147' from dual
    union all select 'v2', '258' from dual
    union all select 'v3', '369' from dual
    union all select 'd1', '159' from dual
    union all select 'd2', '357' from dual
),
t9(n) as
(select level from dual connect by level <= 9),
gen(lvl, str) as
(
    select 1, cast(n as varchar(9))
    from t9
    union all
    select lvl + 1, str || n
    from gen, t9 n
    where instr(str, n) = 0
),
split_xo as
(
    -- prefixing with '#' so that translate never returns empty string
    select str, type, '#'||seq seq
    from (select str, regexp_replace(str, '(.).', '\1') x, regexp_replace(str, '.(.)|.', '\1') o from gen)
    unpivot (seq for type in (x, o))
),
flags as
(
    select t.*,
    decode(length(seq)-length(translate(seq,'_'||ww.cells,'_')),3,1,0) chk,
    sign(instr(ww.cells,substr(str,-1))) last_move
    from split_xo t, winning_ways ww
),
checks as
(
    -- nvl to handle cases with a single move (i.e. no data for O)
    select str, length(str) len, x_chk, x_fchk, nvl(o_chk, 0) o_chk, nvl(o_fchk, 0) o_fchk
    from
    (select
        str,
        type,
        -- first check returns number of directions (horizontal/vertical/diagonal)
        -- where all 3 cells selected
        -- second check returns number of directions (horizontal/vertical/diagonal)
        -- where all 3 cells selected AND last move belongs to winning direction
        -- we need second check because if there are any moves after winning direction completed
        -- then sequence is incorrect (no moves can exist after "game over")
        sum(chk) chk,
        sum(chk*last_move) fchk
    from flags
    group by str, type)
    pivot (sum(chk) chk, sum(fchk) fchk for type in ('X' x, 'O' o))
),
t as
(
    select
    c.*,
    case
        when x_chk > 0 and o_chk = 0 then case when x_chk = x_fchk then 'X won' else 'incorrect sequence (X won)' end
        when x_chk = 0 and o_chk > 0 then case when o_chk = o_fchk then 'O won' else 'incorrect sequence (O won)' end
        when x_chk + o_chk > 1 then 'incorrect sequence (both won)'
        when x_chk + o_chk = 0 and len = 9 then 'tie'
        else 'in progress'
    end result
    from checks c
)
select result, count(*) cnt
from t
group by result
order by 1;

RESULT                               CNT
----------------------------- ----------
O won                              77904
X won                             131184
in progress                       294777
incorrect sequence (O won)         70848
incorrect sequence (X won)        214848
incorrect sequence (both won)     150768
tie                                46080

7 rows selected.

Every child from primary school knows that it is impossible to win starting with empty board if opponent plays optimally.

However, for below position X can win no matter what O does.

.|o|o
-----
.|x|. 
-----
x|.|.

So, technically, for each game “in progress” we need to decide how it ends if both players play optimally.

• in progress (X wins)
• in progress (O wins)
• in progress (tie)

If you ask me what the optimal strategy is - well, the is the key point.

PS. Challenge was originally intoduced by James. But let's use pure SQL.

PPS. Draft query may contain bugs and also there is high chance it can be implemented in a more concise/efficient way. So improvements are welcome.