Ataxx

README.md

Ataxx

This is a tool that understands the board game Ataxx, and generates moves for it based on a board. Before using the tool, make it (and other included scripts, see below) executable

$ chmod +x main.py board.py play

The input should have separated by newlines a height, width, playing token, and rows of the board. For example:
The spec provided by Adoxography perscribes the first 2 lines be height and width, but they are discarded since we aren't going to do any allocation ahead of time. With this, we might get something like:

4
4
X
_ _ _ O
_ X _ _
_ _ _ O
_ _ _ X

Using main.py

main.py is primarially used to make a move on an ataxx board. It's usage is

usage: main.py [-h] [-b] [-p] [-f FILE] [-i]

optional arguments:
  -h, --help            show this help message and
                        exit
  -b, --best            try to choose the best move
  -p, --playable        write results so that they can
                        be understood by this program
  -f FILE, --file FILE  read the board from this file
                        instead of stdin
  -i, --interactive     run interactive and do nothing
                        in main()

It understands boards given to it in the format mentioned. By default, given some token that should move token and a board board, It will return a board for ever move doable by token, where each board is board with that move haven been done.

For example given the following board

4
4
X
X O _ _
_ _ O _
_ _ O _
_ _ X _

it should produce a list of boards

$ cat board ./main.py
X O _ _
X _ O _
_ _ O _
_ _ X _

X O _ _
_ X O _
_ _ O _
_ _ X _

_ O _ _
_ _ O _
X _ O _
_ _ X _

...and so on (in this case, 10 moves) If there are no available moves (no tokens present, full board, or just blocked) then nothing is returned

Finding the best board

If -b | --best is passed, it will return what it thinks is the best move to make Following the board from the last example, it should produce

_ X X _
_ _ O _
_ _ O _
_ _ X _

The basic flow for determining a "good" board is to generate possible boards, score them, and pick the top scoring board. If there is a tie for top scoring boards, pick a random one of those to add variety

The scoring algorithm looks at:

• The population of the playing token
• The population of opponent tokens
• The number of times that the playing token may jump an opponent
• The number of times that the playing token may be jumped by an opponent

Recursable

If -p | --playable is passed, the same things happen but the board(s) returned is able to be understood by this script. This is useful for feeding results into the program again. The returned token represents the next token that should play

Using the same board from before, we could

$ cat board | ./main.py -bp | ./main.py -bp
4
4
X
_ X X _
_ _ O _
_ _ O O
_ _ X _

Other arguments

-f | --file [file] can be used to read a board from a file instead of stdin

$ ./main.py -f board

-i | --interactive can be used when you are starting the script interactively

$ python -i main.py -i
>>>

Other fun stuff

board.py

board.py is a tool for generating random boards at random game states. It does not try to generate valid game states, but rather randomly populates a board with tokens. This was used for testing.

It's usage is

usage: board.py [-h] [-l LENGTH] [-w WIDTH] [-p POPULATION] [tokens [tokens ...]]

positional arguments:
  tokens                token pool

optional arguments:
  -h, --help            show this help message and exit
  -l LENGTH, --length LENGTH
                        board length
  -w WIDTH, --width WIDTH
                        board width
  -p POPULATION, --population POPULATION
                        token population

It can be used like below, and it's out put right into main.py

8
8
X
_ _ _ O O _ _ _
_ _ _ _ O _ _ X
_ _ _ _ _ _ _ O
_ X _ O X X _ O
_ _ _ O _ _ _ _
_ O _ O _ _ _ _
_ _ _ _ _ _ _ O
X _ O O X _ O X

play

play is a small tool that will use board.py to generate a random board and use it to have main.py play with itself

Its arguments map to ./board.py -l$1 -w$2 -p$3

$ ./play 4 4 4
4
4
X
O O _ _
X _ _ _
_ _ O _
_ _ _ _
4
4
O
O O _ _
X _ _ _
X _ O _
_ _ _ _

...

4
4
X
O O O O
X O O O
X X _ O
X X X X
4
4
O
O O O O
X O O O
X X X O
X X X X

board.py

#!/usr/bin/env python3

import argparse, random
from typing import (
    List,
)

BLANK: str = "_"

def get_args() -> argparse.Namespace:
    parser = argparse.ArgumentParser()
    parser.add_argument("-l", "--length", type = int, default = 4, help = "board length")
    parser.add_argument("-w", "--width", type = int, default = 4, help = "board width")
    parser.add_argument("-p", "--population", type = int, default = 4, help = "token population")
    parser.add_argument("tokens", type = str, nargs="*", default = ["O", "X"], help = "token pool")
    return parser.parse_args()

def blank_board(length, width) -> List:
    return [
        [BLANK for _ in range(width)]
        for _ in range(length)
    ]

def fill_board(tokens: List, population: int, blank: List) -> List:
    fillable: List = [[*row] for row in blank]

    while population:
        for row, row_index in zip(fillable, range(len(fillable) + 1)):
            for space, space_index in zip(row, range(len(row) + 1)):
                if not population:
                    break

                if space == BLANK and random.randrange(0, 100) == 0:
                    fillable[row_index][space_index] = random.choice(tokens)
                    population -= 1

    return fillable

def serialize_board(board: List) -> str:
    return "\n".join([" ".join(it) for it in board])

def serialize_board_playable(token: str, board: List) -> str:
    return "\n".join([
        f"{len(board)}",
        f"{len(board[0])}",
        token,
        serialize_board(board),
    ])

def main():
    args: argparse.Namespace = get_args()
    if len(args.tokens) > args.length * args.width:
        raise Exception(f"{len(args.tokens)} cannot fit on a board {args.length}x{args.width}")

    print(serialize_board_playable(
        random.choice(args.tokens),
        fill_board(args.tokens, args.population, blank_board(
            args.length, args.width
        ))
    ))

main()

main.py

#!/usr/bin/env python3

import argparse, random
from typing import (
    Any,
    Dict,
    List,
    Tuple,
    Union,
)

Move = Dict[str, Any]

BLANK: str = "_"
MOVERS: Dict = {
    "n":  lambda start : (start[0] - 1, start[1]),
    "s":  lambda start : (start[0] + 1, start[1]),
    "e":  lambda start : (start[0], start[1] + 1),
    "w":  lambda start : (start[0], start[1] - 1),
    "ne": lambda start : (start[0] - 1, start[1] + 1),
    "nw": lambda start : (start[0] - 1, start[1] - 1),
    "se": lambda start : (start[0] + 1, start[1] + 1),
    "sw": lambda start : (start[0] + 1, start[1] - 1),
}

def get_args() -> argparse.Namespace:
    parser = argparse.ArgumentParser()
    parser.add_argument("-b", "--best", action = "store_true", help = "try to choose the best move")
    parser.add_argument("-p", "--playable", action = "store_true", help = "write results so that they can be understood by this program")
    parser.add_argument("-f", "--file", type = str, help = "read the board from this file instead of stdin")
    parser.add_argument("-i", "--interactive", action = "store_true", help = "run interactive and do nothing in main()")
    return parser.parse_args()

def between_points(start: Tuple[int, int], stop: Tuple[int, int]) -> Tuple[int, int]:
    return (
        start[0] + (stop[0] - start[0]) // 2,
        start[1] + (stop[1] - start[1]) // 2,
    )

def make_move(start: Tuple[int, int], stop: Tuple[int, int]) -> Move:
    return {
        "start": start,
        "stop": stop,
        "long": (long := abs(stop[0] - start[0]) == 2 or abs(stop[1] - start[1]) == 2),
        "over": between_points(start, stop) if long else None,
    }

def move(start: Tuple[int, int], direction: str, long: bool = False) -> Move:
    mover: function = MOVERS[direction]
    return make_move(
        start,
        mover(mover(start)) if long else mover(start),
    )

def moves_from(where: Tuple[int, int], board: List[str]) -> List[Move]:
    return [
        it for it in [
                move(where, direction) for direction in MOVERS.keys()
            ] + [
                move(where, direction, True) for direction in MOVERS.keys()
            ]
        if validate_move(it, board)
    ]

def possible_moves(token: str, board: List[str]) -> List[Move]:
    return [
        move
        for position in positions(token, board)
        for move in moves_from(position, board)
    ]

def positions(token: str, board: List[str]) -> List[Tuple[int, int]]:
    return [
        (row, column)
        for row in range(len(board))
        for column in range(len(board[row]))
        if board[row][column] == token
    ]

def in_bounds(where: Tuple[int, int], board: Dict) -> bool:
    return all([
        0 <= where[0] < len(board),
        0 <= where[1] < len(board[0]),
    ])

def validate_move(move: Move, board: Dict) -> bool:
    where: Tuple[int, int] = move["stop"]

    if not in_bounds(where, board):
        return False

    return board[where[0]][where[1]] == BLANK

def next_token(token: str, board: List) -> str:
    tokens: List = sorted(list(set([
        it
        for row in board
        for it in row
        if it != BLANK
    ])))


    return (
        tokens[(tokens.index(token) + 1) % len(tokens)]
        if token in tokens else
            tokens[0] if tokens else token
        )

def token_at(where: Tuple[int, int], board: Dict) -> str:
    return board[where[0]][where[1]] if in_bounds(where, board) else None

def with_tokens(token: str, targets: List, board: Dict) -> Dict:
        modified = [
            [
                token if targets[0] == (row, column) else token_at((row, column), board)
                for column in range(len(board[0]))
            ] for row in range(len(board))
        ]

        return with_tokens(token, targets[1:], modified) if targets[1:] else modified

def surrounding_tokens(where: Tuple[int, int], board: Dict) -> List:
    return [
        (row, column)
        for row in range(where[0] - 1, where[0] + 2)
        for column in range(where[1] - 1, where[1] + 2)
        if in_bounds((row, column), board)
        and token_at((row, column), board) != BLANK
    ]

def with_move(move: Move, board: Dict) -> Dict:
    start: Tuple[int, int] = move["start"]
    stop: Tuple[int, int] = move["stop"]

    return with_tokens(
        token_at(start, board),
        [
            *surrounding_tokens(stop, board),
            *([stop] if move["long"] else [stop, start])
        ],
        board
    )

def possible_jumps(token: str, board: Dict) -> List[Move]:
    return [
        move
        for position in positions(token, board)
        for move in jumpable_from(token, position, board)
    ]

def jumpable_from(token: str, where: Tuple[int, int], board: Dict) -> List[Move]:
    return [
        move
        for move in moves_from(where, board)
        if move["long"]
        and not token_at(move["over"], board) in (BLANK, token)
    ]

def score_board(token: str, board: Dict, depth: int = 1) -> int:
    population: List = [
        it
        for row in board
        for it in row
        if it != BLANK
    ]
    others: List = [it for it in set(population) if it != token]

    opp_token: str = next_token(token, board)
    opp_score: List = score_board(
        opp_token,
        best_board(opp_token, possible_boards(opp_token, board), 0),
        depth - 1
    ) if depth else 0

    return sum([
        -2 * sum((len(possible_jumps(it, board)) for it in others)),
         len(possible_jumps(token, board)),
         (token_population := len([it for it in population if it == token])),
         -(len(population) - token_population),
         opp_score * (1 if opp_token == token else -1)
    ])

def score_boards(token: str, boards: List, depth: int = 1) -> List[Tuple[List, int]]:
    return sorted(
        [
            {"board": board, "score": score_board(token, board, depth)}
            for board in boards
        ],
        key = lambda it : it["score"],
    )

def possible_boards(token: str, board: List) -> List:
    return [with_move(move, board) for move in possible_moves(token, board)]

def best_board(token: str, boards: List, depth: int = 3) -> List:
    scores: List[Tuple[List, int]] = score_boards(token, boards, depth)

    return random.choice([
        it for it in scores
        if it["score"] == max([
            nest_it["score"] for nest_it in scores
        ])
    ])["board"] if len(scores) else []

def read_board_string(string: str) -> (str, List):
    split: List = [it.strip() for it in string.split("\n")]
    return data[2], [it.split(" ") for it in data[3:]]

def read_board(path: str = "/dev/stdin") -> (str, List):
    with open(path) as stream:
        data = [it.strip() for it in stream.readlines()]


    return data[2], [
        it.split(" ") for it in
        [it.strip() for it in data[3:]]
    ]

def serialize_board(_: str, board: List) -> str:
    return "\n".join([" ".join(it) for it in board])

def serialize_board_playable(token: str, board: List) -> str:
    return "\n".join([
        f"{len(board)}",
        f"{len(board[0])}",
        next_token(token, board),
        serialize_board(token, board),
    ])

def main():
    args: argparse.Namespace = get_args()
    if args.interactive:
        return

    token, board = read_board(args.file if args.file else "/dev/stdin")
    serializer = serialize_board_playable if args.playable else serialize_board

    moved = possible_boards(token, board)

    print("\n\n".join([
        serializer(token, it) for it
        in ([best_board(token, moved)] if args.best else moved)
    ]))

main()

play

#!/usr/bin/env bash

echo "$(./board.py -l$1 -w$2 -p$3 O X)" > /tmp/board

while true; do
    if [[ -z "$(cat /tmp/board)" ]]; then
        break
    fi

    echo "$(./main.py -pbf /tmp/board)" > /tmp/board
    cat /tmp/board
done