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
1  
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. –  Matteo Perlini Apr 9 '13 at 9:37
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
2  
@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
1  
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. –  AlexR Dec 1 at 14:49

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.