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:

  1. 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.

  2. 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.

  • 1
    $\begingroup$ It depends on the opponent's choices: if he already have a 2.000.000 sum, maybe a 1 million stone is not so bad. My point is that intuition here can be unreliable, so I was searching for mathematical certainty. :-) Besides, I'm really interested to know how game theory and computer science can handle this kind of games. $\endgroup$ – Matteo Perlini Apr 9 '13 at 9:37
  • 2
    $\begingroup$ Can you argue that on a board of a given size every game is equivalent to a game in which the stones are bounded by some small polynomial of the board size with an additional constraint on which stones may be placed on a given turn? $\endgroup$ – Peter Taylor Apr 9 '13 at 9:51
  • 2
    $\begingroup$ @MatteoPerlini While that's true, there could be some arguments that say "without loss of generality", we can reduce the $k^{th}$ move to one of several finite options such that the game has the same result. Edit: For example, if there are 64 squares on the board and all the past moves have been low, is there ever a reason to play $3,000,000$ over some much smaller number? At each stage, reduce the choices of numbers one should play with to obtain all 'equivalent games' and then you are left with something finite to work with. (up to some sort of isomorphism) $\endgroup$ – muzzlator Apr 9 '13 at 10:04
  • 1
    $\begingroup$ @user45195 That $0$ is or is not a natural number is a matter of convention. See, for example, here. $\endgroup$ – user1729 Dec 1 '14 at 9:17
  • 1
    $\begingroup$ I think it suffices to restrict to a stone greater than all stones of the opponent (one choice) or any available below this. The reasoning is that the opponent can get a greater number on the board anyways so there is no need to take a higher stone, the opponent would then just take an even higher number to place if he wants to. The only flaw may be that the number of stones below this may influence the optimal strategy, but it should be considered as a starting point I think. $\endgroup$ – AlexR Dec 1 '14 at 14:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.