tic-tac-toe 게임은 3x3 게임판에서 O, X 한 쪽을 택하고,
가로/세로/대각선으로 먼저 한 줄(3개)을 만드는 쪽이 승리한다.
3x3이라는 점을 제외하면 5목이 아니라 3목, 또는 빙고 게임과 같다.
연관문제: tic-tac-toe-game
플레이어 vs. AI tic-tac-toe 게임을 만든다.
세부 규칙:
Kevin Crowley, Robert S. Siegler (1993). "Flexible Strategy Use in Young Children's Tic-Tac-Toe". Cognitive Science. 17 (4): 531–561. doi:10.1016/0364-0213(93)90003-Q.
다음 중 첫 번째로 "가능한" 수를 둔다:
Fork:
아래 예에서 O가 둔 자리.
주의: 원문에는 "두 개 이상"이 아니라 "두 개"라고 되어 있음.
_ _ _
_ X _
_ _ O
Blocking Fork의 마지막 부분:
다음 상태1 에서, O가 코너에 두면(2) X의 승리가 확정된다(3).
1:
X _ _
_ O _
_ _ X
2:
X _ O
_ O _
_ _ X
3:
X _ O
_ O _
X _ X
3개의 풀이가 있습니다.
어... 생각보다 빡세네요;;
pygame으로 만들어 봤습니다.
너무 길다 싶으면 TTTGame.run(), TTTGame.do_AI() 만 보시면 됩니다.
from itertools import cycle, combinations
import random
import typing
import pygame
debug = print
class TTTGUI:
WHITE, BLACK, BLUE = (255, 255, 255), (0, 0, 0), (0, 0, 255)
def __init__(self):
pygame.init()
self.scr = pygame.display.set_mode((470, 470))
# self.img = {'O':pygame.image.load('O.png'), 'X':pygame.image.load('X.png')}
# pygame.transform.scale(self.img['O'], (150, 150))
# pygame.transform.scale(self.img['X'], (150, 150))
def eventloop(self):
while True:
for event in pygame.event.get():
if event.type == pygame.QUIT:
self.quit()
elif event.type == pygame.MOUSEBUTTONDOWN and 10<=event.pos[0]<=460 and 10<=event.pos[1]<=460:
i, j = (event.pos[1]-10)//150, (event.pos[0]-10)//150
return i*3+j
def _txtsurf(self, size, txt):
return pygame.font.SysFont("comicsansms", size).render(txt, False, TTTGUI.BLUE)
def intro(self, players):
self.scr.fill(TTTGUI.WHITE)
txt1 = self._txtsurf(36, 'X: ' + players[0].name)
txt2 = self._txtsurf(36, 'O: ' + players[1].name)
self.scr.blit(txt1, (100, 150))
self.scr.blit(txt2, (100, 250))
pygame.display.flip()
self.eventloop()
def display(self, brd):
self.scr.fill(TTTGUI.WHITE)
pygame.draw.line(self.scr, TTTGUI.BLACK, (160, 0), (160, 470))
pygame.draw.line(self.scr, TTTGUI.BLACK, (310, 0), (310, 470))
pygame.draw.line(self.scr, TTTGUI.BLACK, (0, 160), (470, 160))
pygame.draw.line(self.scr, TTTGUI.BLACK, (0, 310), (470, 310))
for i in range(3):
for j in range(3):
if brd[i*3+j] == 'O':
pygame.draw.circle(self.scr, TTTGUI.BLACK, (85+j*150, 85+i*150), 60)
elif brd[i*3+j] == 'X':
rect = pygame.Rect(25+j*150, 25+i*150, 120, 120)
pygame.draw.line(self.scr, TTTGUI.BLACK, (rect.topleft), (rect.bottomright))
pygame.draw.line(self.scr, TTTGUI.BLACK, (rect.topright), (rect.bottomleft))
pygame.display.flip()
def ending(self, msg=''):
self.scr.blit(self._txtsurf(72, msg), (100, 200))
pygame.display.flip()
self.eventloop()
self.quit()
def quit(self):
pygame.quit()
exit()
class Player(typing.NamedTuple):
name: str
char: str
do: typing.Callable
class TTTGame:
ROWS = ((0, 1, 2), (3, 4, 5), (6, 7, 8), (0, 3, 6), (1, 4, 7), (2, 5, 8), (0, 4, 8), (2, 4, 6))
def __init__(self):
self.brd = [' ' for _ in range(9)]
#P1 = Player('User', random.choice('OX'), self.do_player)
P1 = Player('User', 'X', self.do_player)
P2 = Player('AI', 'OX'.replace(P1.char, ''), self.do_AI)
self.players = (P1, P2) if P1.char=='X' else (P2, P1)
self.view = TTTGUI()
self.view.intro(self.players)
def _rowstr(self, row):
return [self.brd[p] for p in row]
def run(self):
assert any(p.do == self.do_player for p in self.players), "at least 1 user"
self.view.display(self.brd)
for player in cycle(self.players):
pos = player.do(player.char)
self.brd[pos] = player.char
self.view.display(self.brd)
rows = [self._rowstr(r) for r in TTTGame.ROWS]
debug('brd:', self.brd, 'rows:', [''.join(r).replace(' ','_') for r in rows])
if all('O' in set(r) and 'X' in set(r) for r in rows):
self.view.ending('draw')
elif [player.char]*3 in rows:
self.view.ending(player.name + ' win!')
def do_player(self, me):
ret = self.view.eventloop()
return ret if self.brd[ret] == ' ' else self.do_player(me)
def do_AI(self, me):
CENTER, CORNERS, SIDES = 4, (0, 2, 6, 8), (1, 3, 5, 7)
enemy = 'OX'.replace(me, '')
rows = list(zip(TTTGame.ROWS, [self._rowstr(r) for r in TTTGame.ROWS]))
def winnable_rows(c):
for r, s in rows:
if c in s and s.count(' ') == 2:
yield (r, s)
def winnable_pos(c) -> set:
ret = set()
for r, s in winnable_rows(c):
ret.add(r[s.index(' ')])
return ret
def winning_pos(c) -> set:
ret = set()
for r, s in rows:
if s.count(c) == 2 and ' ' in s:
ret.add(r[s.index(' ')])
return ret
def forkable_pos(c) -> set:
ret = set()
for r1, r2 in combinations(winnable_rows(c), 2):
ret |= set(r1[0]) & set(r2[0])
return {x for x in ret if self.brd[x] == ' '}
# WIn
w = winning_pos(me)
if w:
debug('Win')
return w.pop()
# Block
ew = winning_pos(enemy)
if ew:
debug('Block')
return ew.pop()
# Fork
f = forkable_pos(me) - {CENTER}
if f:
debug('Fork')
return f.pop()
# Blocking fork
ewn, ef = winning_pos(enemy), winnable_pos(enemy)
if len(ef) == 1:
debug('Blocking fork(1)')
return ef.pop()
elif ef & ewn:
debug('Blocking fork(2)')
return (ef & ewn).pop()
else:
for p in winnable_pos(me):
self.brd[p] = me
if not forkable_pos(enemy):
self.brd[p] = ' '
debug('Blocking fork(3)')
return p
self.brd[p] = ' '
# Center
if self.brd[CENTER] == ' ':
debug('Center')
return CENTER
# Opposite corner
for c, oc in combinations(CORNERS, 2):
if (self.brd[c], self.brd[oc]) == (enemy, ' '):
debug('Opposite corner')
return oc
# Empty corner
for c in CORNERS:
if self.brd[c] == ' ':
debug('Empty corner')
return c
# Empty side
debug('Empty side')
return self.brd.index(' ')
TTTGame().run()
ttt.win <- function(x, ply, emy){
for (i in 1:3){
for (j in 1:3){
if (sum(x[i, ] == ply) == 2 & sum(x[i, ] == '_') == 1){
x[i, which(x[i, ] == '_')] <- ply
return(x)
} else if (sum(x[, j] == ply) == 2 & sum(x[, j] == '_') == 1){
x[which(x[, j] == '_'), j] <- ply
return(x)
} else if (sum(diag(x) == ply) == 2 & sum(diag(x) == '_') == 1){
x[which(diag(x) == '_'), which(diag(x) == '_')] <- ply
return(x)
} else if (sum(diag(x[1:3, 3:1]) == ply) == 2 & sum(diag(x[1:3, 3:1]) == '_') == 1){
x[which(diag(x[1:3, 3:1]) == '_'), which(diag(x[1:3, 3:1]) == '_')] <- ply
return(x)
} else {
}
}
}
return(x)
}
ttt.block <- function(x, ply, emy){
for (i in 1:3){
for (j in 1:3){
if (sum(x[i, ] == emy) == 2 & sum(x[i, ] == '_') == 1){
x[i, which(x[i, ] == '_')] <- ply
return(x)
} else if (sum(x[, j] == emy) == 2 & sum(x[, j] == '_') == 1){
x[which(x[, j] == '_'), j] <- ply
return(x)
} else if (sum(diag(x) == emy) == 2 & sum(diag(x) == '_') == 1){
x[which(diag(x) == '_'), which(diag(x) == '_')] <- ply
return(x)
} else if (sum(diag(x[1:3, 3:1]) == emy) == 2 & sum(diag(x[1:3, 3:1]) == '_') == 1){
x[which(diag(x[1:3, 3:1]) == '_'), which(diag(x[1:3, 3:1]) == '_')] <- ply
return(x)
} else {
}
}
}
return(x)
}
ttt.fork <- function(x, ply, emy){
du <- x
ct <- 0
for (i in 1:3){
for (j in 1:3){
if (du[i, j] == '_'){
du[i, j] <- ply
if (sum(du[i, ] == ply) == 2 & sum(du[i, ] == '_') == 1){
ct <- ct + 1
}
if (sum(du[, j] == ply) == 2 & sum(du[, j] == '_') == 1){
ct <- ct + 1
}
if (sum(diag(du) == ply) == 2 & sum(diag(du) == '_') == 1){
ct <- ct + 1
}
if (sum(diag(du[1:3, 3:1]) == ply) == 2 & sum(diag(du[1:3, 3:1]) == '_') == 1){
ct <- ct + 1
}
if (ct >= 2){
return(du)
}
du <- x
ct <- 0
}
}
}
return(x)
}
ttt.block.fork <- function(x, ply, emy){
du <- x
ct <- 0
for (i in 1:3){
for (j in 1:3){
if (du[i, j] == '_'){
du[i, j] <- emy
if (sum(du[i, ] == emy) == 2 & sum(du[i, ] == '_') == 1){
ct <- ct + 1
}
if (sum(du[, j] == emy) == 2 & sum(du[, j] == '_') == 1){
ct <- ct + 1
}
if (sum(diag(du) == emy) == 2 & sum(diag(du) == '_') == 1){
ct <- ct + 1
}
if (sum(diag(du[1:3, 3:1]) == emy) == 2 & sum(diag(du[1:3, 3:1]) == '_') == 1){
ct <- ct + 1
}
if (ct >= 2){
du[i, j] <- ply
return(du)
}
du <- x
ct <- 0
}
}
}
return(x)
}
ttt.center <- function(x, ply, emy){
if (x[2, 2] == '_')
x[2, 2] <- ply
return(x)
}
ttt.opposite.corner <- function(x, ply, emy){
if (x[1, 1] == emy & x[3, 3] == '_'){
x[3, 3] <- ply
return(x)
} else if (x[1, 3] == emy & x[3, 1] == '_'){
x[3, 1] <- ply
return(x)
} else if (x[3, 1] == emy & x[1, 3] == '_'){
x[1, 3] <- ply
return(x)
} else if (x[3, 3] == emy & x[1, 1] == '_'){
x[1, 1] <- ply
return(x)
} else {
return(x)
}
}
ttt.empty.corner <- function(x, ply, emy){
if (x[1, 1] == '_'){
x[1, 1] <- ply
return(x)
} else if (x[1, 3] == '_'){
x[1, 3] <- ply
return(x)
} else if (x[3, 1] == '_'){
x[3, 1] <- ply
return(x)
} else if (x[3, 3] == '_'){
x[3, 3] <- ply
return(x)
} else {
return(x)
}
}
ttt.empty.side <- function(x, ply, emy){
for (i in 1:3){
for (j in 1:3){
if (x[i, j] == '_'){
x[i, j] <- ply
return(x)
}
}
}
}
ply_set <- c('O', 'X')
ttt <- function(x, ply, emy){
du <- ttt.win(x, ply, emy)
if (!all(du == x)){
print(du)
return(du)
}
du <- ttt.block(x, ply, emy)
if (!all(du == x)){
print(du)
return(du)
}
du <- ttt.fork(x, ply, emy)
if (!all(du == x)){
print(du)
return(du)
}
du <- ttt.block.fork(x, ply, emy)
if (!all(du == x)){
print(du)
return(du)
}
du <- ttt.center(x, ply, emy)
if (!all(du == x)){
print(du)
return(du)
}
du <- ttt.opposite.corner(x, ply, emy)
if (!all(du == x)){
print(du)
return(du)
}
du <- ttt.empty.corner(x, ply, emy)
if (!all(du == x)){
print(du)
return(du)
}
du <- ttt.empty.side(x, ply, emy)
if (!all(du == x)){
print(du)
return(du)
}
}
ply <- 'O'
emy <- 'X'
x <- matrix('_', nrow = 3, ncol = 3)
ttt_run <- function(x, ply, emy){
while (sum(x == '_') != 0){
x <- ttt(x, ply, emy)
ply <- ply_set[which(ply_set == ply) %% 2 + 1]
emy <- ply_set[which(ply_set == emy) %% 2 + 1]
}
}
ttt_run(x, ply, emy)
{-# LANGUAGE TupleSections #-}
import Data.List
import Data.Ord
import Data.Maybe
import Control.Applicative
import Control.Monad
sortOnM f xs = liftM (map fst . sortBy (comparing snd)) $ mapM (\x -> liftM (x,) (f x)) xs
ifM b t f = do b <- b; if b then t else f
-- rules of the game
newgame = const Nothing
place i g n = if n == i then Just True else g n
look = flip ($)
invert = fmap $ fmap not
emptySlots = filterM (fmap (== Nothing) . look) [1..9]
cohorts = [[1,2,3], [4,5,6], [7,8,9], [1,4,7], [2,5,8], [3,6,9], [1,5,9], [3,5,7]]
data GameResult = Won | Lost | Undecided | Draw deriving (Eq, Ord, Show)
gameState = minimum . fmap cohortState . mapM (mapM look) cohorts
where
cohortState s = case sort . nub $ s of
[Just True] -> Won
[Just False] -> Lost
[Nothing, Just _] -> Undecided
[Nothing] -> Undecided
otherwise -> Draw
won = (== Won) . gameState
done = (/= Undecided) . gameState
-- strategy
bestMove = head . mconcat [win, block, fork, blockFork, center, opposite, corner, side]
where
win = findMovesM $ won
fork = findMovesM $ (==2) . length . win
blockFork1 = findMovesM $ null . fork . invert
blockFork2 = (findMovesM $ (&&)
<$> not . null . win
<*> null . liftA2 intersect fork block . invert)
>>= sortOnM (fmap (fork . invert) . place)
blockFork = ifM (null . fork . invert) (pure []) $ blockFork1 <> blockFork2
opposite = corner >>= filterM (fmap (== Just False) . look . negate . subtract 10)
block = win . invert
center = filterAvailable [5]
corner = filterAvailable [1,3,7,9]
side = filterAvailable [2,4,6,8]
findMovesM p = emptySlots >>= filterM (fmap p . place)
filterAvailable = liftA2 intersect emptySlots . pure
-- I/O
render f = (<> "\n---\n") $ [[1,2,3], [4,5,6], [7,8,9]] >>= (>>= (r . f)) <> const "\n"
where
r Nothing = " "
r (Just True) = "O"
r (Just False) = "X"
main = mapM_ putStrLn $ fmap render $ takeWhile (not.done) $ iterate (invert . (bestMove >>= place)) newgame