export Game, showAll, validMoves, randomPlace, place, getGameState, int, PLAYERS

### Game setting

# board size
BOARD_SIZE = Int8(9)
ACTION_SIZE = Int8(9)
HISTORY = Int8(4)

# transition from players
PLAYERS = Dict{Union{String, Int8}, Union{String, Int8}}("O"=>Int8(1), Int8(1)=>"O", "X"=>Int8(-1), Int8(-1)=>"X", zero(Int8)=>".")
NEXT_TURN = Dict{Union{String, Int8}, Union{String, Int8}}("O"=>"X", Int8(1)=>Int8(-1), "X"=>"O", Int8(-1)=>Int8(1))

# The state we need to evaluate winning situtaions
STATE = Array{Array{Int8,1}}([
        [1, 2, 3], [4, 5, 6], [7, 8, 9],
        [1, 4, 7], [2, 5, 8], [3, 6, 9],
        [1, 5, 9], [3, 5, 7]
        ])

# give an action, get all possible winning situations
SLOT = Array{Array{Array{Int8,1},1},1}([
        [[1, 2, 3], [1, 4, 7], [1, 5, 9]],
        [[1, 2, 3], [2, 5, 8]],
        [[1, 2, 3], [3, 5, 7], [3, 6, 9]],
        [[1, 4, 7], [4, 5, 6]],
        [[4, 5, 6], [2, 5, 8], [1, 5, 9], [3, 5, 7]],
        [[4, 5, 6], [3, 6, 9]],
        [[1, 4, 7], [7, 8, 9], [3, 5, 7]],
        [[7, 8, 9], [2, 5, 8]],
        [[7, 8, 9], [3, 6, 9], [1, 5, 9]]
        ])

# offset move -> actual board index
OFFSET = Dict{Tuple{Int8,Int8},Tuple{Int8,Int8}}(
  (3, 5) => (2, 8), (3, 6) => (2, 9), (6, 9) => (6, 9), (4, 4) => (5, 1), (9, 4) => (8, 7), (9, 1) => (7, 7), (8, 9) => (9, 6), (3, 1) => (1, 7), (4, 5) => (5, 2),
  (9, 9) => (9, 9), (2, 4) => (2, 4), (6, 5) => (5, 8), (4, 9) => (6, 3), (8, 4) => (8, 4), (1, 2) => (1, 2), (9, 2) => (7, 8), (5, 1) => (4, 4), (9, 8) => (9, 8),
  (3, 4) => (2, 7), (9, 6) => (8, 9), (8, 2) => (7, 5), (2, 3) => (1, 6), (2, 6) => (2, 6), (5, 4) => (5, 4), (2, 1) => (1, 4), (2, 5) => (2, 5), (8, 5) => (8, 5),
  (5, 9) => (6, 6), (1, 4) => (2, 1), (3, 9) => (3, 9), (2, 8) => (3, 5), (5, 8) => (6, 5), (4, 8) => (6, 2), (7, 8) => (9, 2), (1, 1) => (1, 1), (7, 7) => (9, 1),
  (7, 9) => (9, 3), (5, 7) => (6, 4), (7, 2) => (7, 2), (2, 2) => (1, 5), (6, 3) => (4, 9), (1, 7) => (3, 1), (4, 7) => (6, 1), (6, 1) => (4, 7), (6, 8) => (6, 8),
  (8, 8) => (9, 5), (7, 1) => (7, 1), (1, 3) => (1, 3), (7, 5) => (8, 2), (2, 9) => (3, 6), (3, 2) => (1, 8), (7, 6) => (8, 3), (9, 3) => (7, 9), (3, 7) => (3, 7),
  (6, 6) => (5, 9), (5, 5) => (5, 5), (2, 7) => (3, 4), (4, 1) => (4, 1), (8, 3) => (7, 6), (4, 2) => (4, 2), (1, 6) => (2, 3), (4, 3) => (4, 3), (9, 7) => (9, 7),
  (5, 6) => (5, 6), (8, 6) => (8, 6), (4, 6) => (5, 3), (8, 1) => (7, 4), (3, 3) => (1, 9), (6, 2) => (4, 8), (7, 4) => (8, 1), (1, 9) => (3, 3), (8, 7) => (9, 4),
  (6, 4) => (5, 7), (5, 2) => (4, 5), (1, 8) => (3, 2), (6, 7) => (6, 7), (7, 3) => (7, 3), (5, 3) => (4, 6), (3, 8) => (3, 8), (1, 5) => (2, 2), (9, 5) => (8, 8)
)

int(x::Union{Char, String}, T=Int) = parse(T, x)

mutable struct Game
    _boards::Array{Int8,3}
    board::Array{Int8,2}
    nextPlayer::Int8
    steps::Int8
    winner::Union{Int8, Nothing}
    state::Union{Nothing, String}
end

convertState(state) = [int(i, Int8) for i in state]


function Game(state::Union{Nothing, String}=nothing)
    _boards = zeros(Int8, (BOARD_SIZE, BOARD_SIZE, 1))
    board = zeros(Int8, (BOARD_SIZE, BOARD_SIZE))
    nextPlayer = Int8(-1)
    steps = oneunit(Int8)
    winner = nothing
    if !isnothing(state)
        moves = convertState(state)
        subboard =  moves[1]
        player = oneunit(Int8)
        for currMove in moves[2:end]
            player = NEXT_TURN[player]
            x,y = OFFSET[(subboard, currMove)]
            board[x,y] = player
            steps += Int8(1)
            _boards = cat(dims=3, _boards, copy(board))
            subboard = currMove
        end
        nextPlayer = NEXT_TURN[player]
    end
    Game(_boards, board, nextPlayer, steps, winner, state)
end


function Base.show(io::IO, self::Game)
    "print out the board"
    compact = get(io, :compact, false)
    if !compact
        board = self._boards[:,:,self.steps]
        for i=1:9
            print(io, PLAYERS[board[i,1]]," ", PLAYERS[board[i,2]]," ",PLAYERS[board[i,3]]," | ")
            print(io, PLAYERS[board[i,4]]," ", PLAYERS[board[i,5]]," ",PLAYERS[board[i,6]]," | ")
            print(io, PLAYERS[board[i,7]]," ", PLAYERS[board[i,8]]," ",PLAYERS[board[i,9]],"\n")
            if i in (3, 6)
                print(io, "------+-------+------\n")
            end
        end
        showState = isnothing(self.state) ? "0" : self.state
        print(io, "\nSubboard: ",showState[end],"; next Player: ", PLAYERS[self.nextPlayer], ";\n")
        print(io, "\nGame States: ",showState,"; Steps: ",self.steps-Int8(1),"; ")
        isnothing(self.winner) ? print(io, "Game continue...\n") : print(io, PLAYERS[self.winner], " wins\n")
    end
end

function showAll(self::Game)
    "show each steps' board"
    steps = self.steps
    state = self.state
    winner = self.winner
    print(self)
    self.winner = false
    player = NEXT_TURN[self.nextPlayer]

    for i = Int8(1):steps-Int8(1)
        self.steps-=Int8(1)
        self.state = self.state[1:end-1]
        self.nextPlayer = NEXT_TURN[self.nextPlayer]
        print(self)
    end
    self.winner = winner
    self.steps = steps
    self.state = state
    self.nextPlayer=player
    return
end

function CheckEndGame(self::Game)
    "Check whether the game is end"
    if self.steps==Int8(1)
        return false
    end
    if self.winner!=nothing
        return true
    end
    x, y = convertState(self.state[end-1:end])
    for trip in SLOT[y]
        i1,i2,i3 = trip
        x1,y1 = OFFSET[(x,i1)]
        x2,y2 = OFFSET[(x,i2)]
        x3,y3 = OFFSET[(x,i3)]
        if abs(self.board[x1,y1]+self.board[x2,y2]+self.board[x3,y3])==Int8(3)
            self.winner = -self.nextPlayer
            return true
        end
    end
    return false
end

function validMoves(self::Game, valid::Bool=true)
    "Returns all the legal moves for current subboard"

    isnothing(self.state) && return keys(OFFSET)

    x = int(self.state[end])
    legalMoves = []
    for y=Int8(1):Int8(9)
        if self.board[OFFSET[(x,y)]...]==zero(Int8)
            push!(legalMoves, y)
        end
    end

    isempty(legalMoves) && return rand(Int8(1):Int8(9),1)

    validMoves = Array{Int8}([])
    for move in legalMoves
        IsValidMove = true

        # case 1, the move player can directly win
        for (i1,i2,i3) in SLOT[move]
            x1,y1 = OFFSET[(x,i1)]
            x2,y2 = OFFSET[(x,i2)]
            x3,y3 = OFFSET[(x,i3)]
            if (self.board[x1,y1]+self.board[x2,y2]+self.board[x3,y3]) == 2self.nextPlayer
                return [move]
            end
        end

        # case 2, avoid the next player directly wins
        for (i1,i2,i3) in STATE
            x1,y1 = OFFSET[(move,i1)]
            x2,y2 = OFFSET[(move,i2)]
            x3,y3 = OFFSET[(move,i3)]

            if (self.board[x1,y1]+self.board[x2,y2]+self.board[x3,y3]) == -2self.nextPlayer
                IsValidMove = false
                break
            end
        end

        if IsValidMove
            push!(validMoves, move)
        end
    end

    # if there is no valid moves, we return legal moves
    return length(validMoves) == 0 ? legalMoves : validMoves
end


function place(self::Game, move)
    if self.winner==nothing
        if self.state==nothing
            x,y = OFFSET[move]
            self.board[x,y] = self.nextPlayer
            self.state = "$(move[1])$(move[2])"
            move = y
        else
            x, y = OFFSET[(int(self.state[end]), move)]
            if self.board[x, y] != zero(Int8)
                self.winner = -self.nextPlayer
                return
            end
            self.board[x, y] = self.nextPlayer
            self.state = "$(self.state)$(move)"
        end

        self.steps += Int8(1)
        self._boards = cat(dims=3, self._boards, copy(self.board))
        self.nextPlayer = NEXT_TURN[self.nextPlayer]
    end
    !CheckEndGame(self)
end


function randomPlace(self::Game, times=1)
    for i = 1:times
        self.winner != nothing && break
        moves = validMoves(self)
        place(self, rand(moves))
    end
end


function getGameState(self::Game)
    "Upp is the player X -Int8(1), Bottom is the player O Int8(1)"
    x, y, z = self.steps-Int8(1) <  HISTORY ? (HISTORY-self.steps+Int8(1), Int8(1), HISTORY+self.steps+Int8(1)) : (Int8(1), self.steps-HISTORY+Int8(1), Int8(2)HISTORY+Int8(1))
    GameState = zeros(Float32, (BOARD_SIZE,BOARD_SIZE, 2HISTORY+Int8(1)))
    GameState[:,:,x:z] = cat(dims=3, self._boards[:,:, y:end], fill(self.nextPlayer, BOARD_SIZE,BOARD_SIZE,Int8(1)), self._boards[:,:, y:end][:,:,end:-1:1].*Int8(-1))
    return GameState
end
