Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

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.

share|improve this question
    
What is the size of the board? Are you trying to determine a size of the board that will make this game interesting? I am asking because with a small size brute-force can work, but with a bigger size, monte-carlo approach might be better. –  Djaian Apr 9 '13 at 9:15
    
Hi Djaian, yes, the exact board size in not determined yet, but we can assume for now a standard 8x8 board. How can you use a brute-force if the branching factor is unlimited? –  Matteo Perlini Apr 9 '13 at 9:22
    
Well, technically you have infinite number of stones, but you can suppose it's only finite. After all, the goal of the game is to have the smallest possible sum. So it seems not a good idea to play a stone higher than 1 million for example. –  Djaian Apr 9 '13 at 9:29
1  
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? –  Peter Taylor Apr 9 '13 at 9:51
1  
@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) –  muzzlator Apr 9 '13 at 10:04

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.