VolgaCTF 2016 Tic-Tac-Toe Writeup

お久しぶりです.たんごです.週末はVolgaCTFとpwn2win CTFが被っていてあびゃーって感じでした.結局あまり集中して解くことが出来ずVolga CTFに出題されていたTic Tac Toeの問題だけ解くことが出来たのでそれのWriteupとしてメモ書きを残しておきます.

Tic-Tac-Toe

問題文:

Tic-Tac-Toe

An important step towards the strong AI is the ability of an artificial agent to solve a well-defined problem. A project by the name 'tic-tac-toe' was one of such test problems. It's still up...

nc tic-tac-toe.2016.volgactf.ru 45679

$ nc tic-tac-toe.2016.volgactf.ru 45679
Welcome to Noughts & Crosses World Championship!
Please, name yourself.
jtwp470
The match is played over 500 rounds, the winner of each round gets 1.0 points, the looser gets 0.0 points, and in case of a draw each player gets 0.5 points.
To make your move choose the empty cell and send it's index followed by '\n', e.g. '4\n'.The indices map:
 0 | 1 | 2
---+---+---
 3 | 4 | 5
---+---+---
 6 | 7 | 8

Round number 1.
Server vs. jtwp470. Current score: 0.0 - 0.0
   |   |
---+---+---
   | X |
---+---+---
   |   |

0
 O |   |
---+---+---
 X | X |
---+---+---
   |   |

5
 O |   | X
---+---+---
 X | X | O
---+---+---
   |   |

6
 O |   | X
---+---+---
 X | X | O
---+---+---
 O | X |

1
 O | O | X
---+---+---
 X | X | O
---+---+---
 O | X | X

Round number 2.
Server vs. jtwp470. Current score: 0.5 - 0.5

こんな感じ.Alpha Goみたいにめっちゃ強いやつ出てきたらどうしようと思っていたけど流石にそんなことはなかったw

Tic-Tac-Toe とは

ぐぐるとWikipediaの記事3目並べとかが見つかる. これ授業でやったなあという感じ.

このゲームでは、先手・後手ともに最善を尽くすと必ず引き分けとなる。

と書いてあるので最善手を打ち続ければ少なくとも負けることはないことがわかる.

またいろいろ調べているとミニマックス法とかアルファベータ法と呼ばれるアルゴリズムが出てくるが結局のところ以下の様な方針で実装すればいいらしい.

3つ並べて勝てる場合はそこにおいて勝つ.
相手が3つ並べて勝てる場合は妨害する
中央が空いていればそこに置く.
四隅が空いていればそこに置く.
置ける場所に適当に置く.

というわけで盤面を読み込み上の方法を使ってこまを置く場所を決定しゲームを進めるスクリプトを書いた.

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
import random
import re
import socket
import itertools


def print_board(b):
    print("{0:^3}|{1:^3}|{2:^3}".format(b[0], b[1], b[2]))
    print("---+---+---")
    print("{0:^3}|{1:^3}|{2:^3}".format(b[3], b[4], b[5]))
    print("---+---+---")
    print("{0:^3}|{1:^3}|{2:^3}".format(b[6], b[7], b[8]))
    print("")

# ['X', '', 'O', 'O', 'X', '', 'X', 'O', 'X']
# ['', 'X', '', '', 'O', '', '', '', '']

"""
一番強い(というか最善手の) AIアルゴリズム

1. 置けば勝てるなら置く
2. 敵が勝ちそうであれば妨害する
3. 優先順位的に真ん中 -> 端 におく
4. それも空いていない場合は 諦めて 適当な場所に置く.
"""

lines = (
    (0, 1, 2), (3, 4, 5), (6, 7, 8),
    (0, 3, 6), (1, 4, 7), (2, 5, 8),
    (2, 4, 6), (0, 4, 8))


# my_hand で勝てるかどうか? 勝てるのであれば置くべき場所を返す
def is_win(board, my_hand):
    for pos in lines:
        for ps in itertools.permutations(pos):
            p = board[ps[0]]
            if p == "" and board[ps[1]] == my_hand and board[ps[2]] == my_hand:
                return ps[0]
    return -1  # わからんw


def is_draw(board):
    rest_board = [x for x, y in enumerate(board) if y == ""]
    if len(rest_board) <= 2:
        if is_win(board, "O") == -1 and is_win(board, "X") == -1:
            return True
    return False


# 今の状態から次にどこに置くかを決定する
def decide_pos(board, my_hand):
    enemy_hand = ""
    if my_hand == "X":
        enemy_hand = "O"
    else:
        enemy_hand = "X"

    # もし勝てるのであれば勝つ
    p = is_win(board, my_hand)
    if p >= 0:
        return p

    # もし負けるのであれば妨害を入れる
    p = is_win(board, enemy_hand)
    if p >= 0:
        return p

    # もし中央が空いていればそこに置く.
    if board[4] == "":
        return 4

    # もし隅が空いていれば隅の適当な場所に置く.
    corner = (0, 2, 6, 8)
    for c in corner:
        if board[c] == "":
            return c

    # それ以外の場合は適当に置く.
    for c in range(9):
        if board[c] == "":
            return c
    return None


def read_board(sc_board):
    """
    t is following input.
     X |   |
    ---+---+---
       |   |
    ---+---+---
       |   |
    """
    board = []
    sc = sc_board.replace("---+---+---", "").split("\n")
    for s in sc:
        if s != "":
            s = map(lambda x: x.strip(), s.split("|"))
            for k in s:
                board.append(k)
    return board


def sock(reip, report):
    s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
    s.connect((reip, report))
    s.setsockopt(socket.SOL_SOCKET, socket.SO_REUSEADDR, 1)
    return s, s.makefile('rw')


def read_until(f, delim='\n'):
    data = ""
    while not data.endswith(delim):
        data += f.read(1)
    return data


def main():
    # HOST = "tic-tac-toe.2016.volgactf.ru"
    # HOST = "95.213.237.93"
    HOST = "95.213.237.91"
    PORT = 45679
    s, f = sock(HOST, PORT)
    print(read_until(f), end="")
    print(read_until(f), end="")
    s.sendall(b'jtwp470\n')
    print(read_until(f, "\n\n"))

    print(read_until(f), end="")  # Round number X.
    print(read_until(f), end="")  # Server vs. k. Current score: 0.5 - 0.5

    # 最初に2行読み込む.
    # もし Round が入っていたら 一度リセット
    my_hand = "O"  # start は 自分が O
    while True:
        inp = ""
        inp += read_until(f)
        inp += read_until(f)
        if "Volga" in inp:
            print("Congrats!")
            print(inp)
            break

        if "Round" in inp:
            m = re.match(r"Round number (\d+).", inp.split("\n")[0])
            round_number = int(m.group(1))

            print("Round : %d " % round_number)
            print(inp)
            # 偶数の時は自分は X
            if round_number % 2 == 0:
                my_hand = "X"
            else:
                my_hand = "O"

            print("my_hand is : " + my_hand)

            inp = ""
            inp += read_until(f)
            inp += read_until(f)

        inp += read_until(f)
        inp += read_until(f)
        inp += read_until(f)
        inp += read_until(f)
        board = read_board(inp)

        x = decide_pos(board, my_hand)
        if x is not None:
            s.sendall((str(x) + "\n").encode())
            print("Send: % d" % x)
        print_board(board)

    s.close()
    f.close()


def test():
    ## test_code
    board = ['X', 'X', '',
             '', '', '',
             '', '', '']
    assert decide_pos(board, "X") == 2
    board = ['X', '', 'O',
             'O', 'O', '',
             '', '', '']

    # 妨害を入れる
    assert decide_pos(board, "X") == 5
    board = ['X', 'O', '',
             'O', '', '',
             '', '', '']
    assert decide_pos(board, "X") == 4

    board = ['X', 'O', 'X',
             'O', 'O', 'X',
             'X', 'X', 'O']

    print(decide_pos(board, "X"))

if __name__ == "__main__":
    main()


    """
    ...
    Round : 500
    Round number 500.
    Server vs. jtwp470. Current score: 73.0 - 426.0

    my_hand is : X
    Send:  4
       |   |
    ---+---+---
       |   |
    ---+---+---
       |   |

    Send:  0
       |   |
    ---+---+---
     O | X |
    ---+---+---
       |   |

    Send:  8
     X |   |
    ---+---+---
     O | X |
    ---+---+---
       | O |

    Congrats!:
    Server vs. jtwp470. Final score: 73.0 - 427.0
    Congratulations! Your flag is: VolgaCTF{tic_t@c_t0e_is_the_e@rly_step_t0wards_AI}
    """

最終スコアは73 - 427 でスクリプトの勝ち.全試合の記録はしていないがあまり負けることはなく大抵アイコになって相手に点数取られるみたいなことが多かった.

辛かった点としては自宅のネットワークからロシアにあるであろうサーバーの間でパケットが途中で喪失してしまうのかConnection refusedに苦しまされ続けた.Wiresharkでパケットを追ったりしつづけ結局動かないので大学のサーバーにアクセスしそこでこのスクリプトを動かしたらうまいこと動いてくれたのでなんとか点数を入れることが出来た.