I recently designed a combinatorial game (sequential game of perfect information) with an infinite branching factor, that is it has a game-tree of infinite width.
I'm wondering how is it possible to solve this game? How can I find the best move each turn? Which tools Game Theory has to study this type of games?
Best regards, Matteo Perlini
Infinito is a two-player game, played on a (for the moment) 8x8 square board . One player owns the black stones, the other player owns the white stones. Grey neutral stones are needed.
Each player has an infinite number of stones with an unique natural number printed on them: 0, 1, 2, 3, and so on...
Players move alternately, starting with the player controlling the white stones. Each turn consists of two actions, performed in this order:
Optional move: you can move a stone exactly as a Queen’s moves in Chess, i.e. any number of cells horizontally, vertically or diagonally. If your stone ends its move next to one enemy stone whose value is less than your stone, and your stone wasn’t next to that enemy stone to start its move, replace any friendly stone – but the stone just moved – on the board with a neutral grey stone with “∞” printed on it. In one move you can end up close to more enemy stones whose value are less than your stone, in that case you replace your stones with neutral stones for each of those stones. When you remove your stones from the board, those stones will be available for future placements.
Compulsory placement: you must place a stone onto any empty space.
The game ends when the board is full, whoever has the least sum of his values wins.