Combinatorial game with infinite width game-tree

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

epicurus
Posts: 10
Joined: Thu Apr 11, 2013 3:41 pm UTC

Combinatorial game with infinite width game-tree

Postby epicurus » Thu Apr 11, 2013 3:45 pm UTC

Hi everybody.

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 in particular and mathematics in general have to study this type of games?


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:

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.

User avatar
chridd
Has a vermicelli title
Posts: 846
Joined: Tue Aug 19, 2008 10:07 am UTC
Location: ...Earth, I guess?
Contact:

Re: Combinatorial game with infinite width game-tree

Postby chridd » Fri Apr 12, 2013 6:19 pm UTC

My first thought is that it seems like there should be a highest number that matters—some n for each move where playing a number higher than n won't affect future moves, thus higher-numbered moves don't need to be considered. Suppose you have a 2-square board; the only meaningful choice for the second player would be whether to play a number higher or lower than the first player, and for the first player the only meaningful choice would be whether to play a 1 and let the second player play a lower number, or a 0 and not let them play a lower number. For a 3-square board, there's no point for the first player to play more than a 3, because that allows all the possible meaningful moves in the second turn (play 0 and not let player 1 play something lower, play 1 and have every in-between number available, play 2 and not let player 1 play between the 2 and the 3, play another 3 (I think this is allowed), play a 4 and not allow a number between 3 and 4, or play a 5 or higher and, again, allow any number in between), and so on.

This assumes that the only thing of importance is whether one piece's number is higher, lower, or equal to another piece's number; it doesn't take into account that, for instance, choosing between removing a 1 and a 3 vs. removing a 4 is different than choosing between removing a 1 and a 3 vs. removing a 6, but there may still be some (possibly really high) highest number that matters. (I'm also not sure how well this generalizes.)
~ chri d. d. /tʃɹɪ.di.di/ (Phonotactics, schmphonotactics) · she · Forum game scores
mittfh wrote:I wish this post was very quotable...

nadando
Posts: 33
Joined: Wed Apr 21, 2010 8:33 pm UTC

Re: Combinatorial game with infinite width game-tree

Postby nadando » Fri Apr 12, 2013 6:57 pm UTC

My idea for how to study the game would be first to limit the number of stones, and then see what happens to the game as the number approaches infinity and see what you can generalize.

User avatar
LaserGuy
Posts: 4585
Joined: Thu Jan 15, 2009 5:33 pm UTC

Re: Combinatorial game with infinite width game-tree

Postby LaserGuy » Fri Apr 12, 2013 7:31 pm UTC

Well, I don't think that the highest number matters specifically, except insofar as that you can always place a stone that is one point larger than the opponent's largest stone--you're only hurting yourself to play stones that are any larger than this. In practice, then, you'd never need a stone with a value of above 63--in fact, you likely don't need a stone with a value above 31. I did a quick test on a 4x4 board, and the highest value that was ever played was a 5, which was the last stone played (and also the losing play).

Роберт
Posts: 4285
Joined: Wed May 14, 2008 1:56 am UTC

Re: Combinatorial game with infinite width game-tree

Postby Роберт » Fri Apr 12, 2013 7:38 pm UTC

LaserGuy wrote:you can always place a stone that is one point larger than the opponent's largest stone--you're only hurting yourself to play stones that are any larger than this
I'm not convinced this is true.
The Great Hippo wrote:[T]he way we treat suspected terrorists genuinely terrifies me.

User avatar
Naurgul
Posts: 623
Joined: Mon Jun 16, 2008 10:50 am UTC
Location: Amsterdam, The Netherlands
Contact:

Re: Combinatorial game with infinite width game-tree

Postby Naurgul » Fri Apr 12, 2013 8:00 pm UTC

No matter what, you'll have to place some limits on what numbers the computer can place. Now, to the issue at hand: even if the available moves at each position are not infinite but just a large number, you still have a huge problem. You'll have a combinatorial explosion in your hands if you try to solve it by min-maxing the game tree.

Therefore, you'll need to find some clever game-specific heuristics to prune the tree. You need to aim to no more than 50 possible moves per position, I'd say (for comparison, chess has 20-30 moves at each position on average; this is the principle reason games like chess are considered "solved" but that is not the case for games like go). Another option is to forget the game tree and instead do some nice reinforcement learning. It doesn't work with infinite possible next moves but in general it's good for games that have many possible moves at each position. Or if you want something more exotic, may I suggest a co-evolutionary algorithm to optimise a rules-based script as a strategy?
Praised be the nightmare, which reveals to us that we have the power to create hell.

epicurus
Posts: 10
Joined: Thu Apr 11, 2013 3:41 pm UTC

Re: Combinatorial game with infinite width game-tree

Postby epicurus » Mon Apr 15, 2013 8:50 am UTC

chridd wrote:My first thought is that it seems like there should be a highest number that matters—some n for each move where playing a number higher than n won't affect future moves, thus higher-numbered moves don't need to be considered. Suppose you have a 2-square board; the only meaningful choice for the second player would be whether to play a number higher or lower than the first player, and for the first player the only meaningful choice would be whether to play a 1 and let the second player play a lower number, or a 0 and not let them play a lower number.

With a 2-square board, it is a draw. Both player will play 0.
chridd wrote:For a 3-square board, there's no point for the first player to play more than a 3, because that allows all the possible meaningful moves in the second turn (play 0 and not let player 1 play something lower, play 1 and have every in-between number available, play 2 and not let player 1 play between the 2 and the 3, play another 3 (I think this is allowed), play a 4 and not allow a number between 3 and 4, or play a 5 or higher and, again, allow any number in between), and so on.

With a 3-square board, it is a win for the second player: first player places 0; second player places 0; first player places 1.
(Anyway, it is not possible to have two identical stones, same number and same colour, on the board.)

You cannot take conclusion from this special case, because here you don't use use the optional movement and the rule of replacement.

chridd wrote:This assumes that the only thing of importance is whether one piece's number is higher, lower, or equal to another piece's number; it doesn't take into account that, for instance, choosing between removing a 1 and a 3 vs. removing a 4 is different than choosing between removing a 1 and a 3 vs. removing a 6, but there may still be some (possibly really high) highest number that matters. (I'm also not sure how well this generalizes.)

I'm not convinced. :D

epicurus
Posts: 10
Joined: Thu Apr 11, 2013 3:41 pm UTC

Re: Combinatorial game with infinite width game-tree

Postby epicurus » Mon Apr 15, 2013 8:55 am UTC

nadando wrote:My idea for how to study the game would be first to limit the number of stones, and then see what happens to the game as the number approaches infinity and see what you can generalize.

Hi nadando, the problem is that even if you fix the maximum number, for example to 64, the game is so complex that I wouldn't be able to analyze this finite variant too. And I don't think computers could help for the same reasons.

epicurus
Posts: 10
Joined: Thu Apr 11, 2013 3:41 pm UTC

Re: Combinatorial game with infinite width game-tree

Postby epicurus » Mon Apr 15, 2013 8:58 am UTC

Роберт wrote:
LaserGuy wrote:you can always place a stone that is one point larger than the opponent's largest stone--you're only hurting yourself to play stones that are any larger than this
I'm not convinced this is true.

I'm not convinced too, because we are not taking into account the winning condition and the topological proprieties of the board, of the movement of the pieces and the blocking neutral stones.

epicurus
Posts: 10
Joined: Thu Apr 11, 2013 3:41 pm UTC

Re: Combinatorial game with infinite width game-tree

Postby epicurus » Mon Apr 15, 2013 9:09 am UTC

Naurgul wrote:No matter what, you'll have to place some limits on what numbers the computer can place. Now, to the issue at hand: even if the available moves at each position are not infinite but just a large number, you still have a huge problem. You'll have a combinatorial explosion in your hands if you try to solve it by min-maxing the game tree.

I agree, this is what I was saying to Nadando.

Naurgul wrote:Therefore, you'll need to find some clever game-specific heuristics to prune the tree. You need to aim to no more than 50 possible moves per position, I'd say (for comparison, chess has 20-30 moves at each position on average; this is the principle reason games like chess are considered "solved" but that is not the case for games like go).

I think this is impossible without distort the original spirit of the game. Even if you unrealistically fix a upper limit to 10 to the stones value, you have a huge game-tree.

Naurgul wrote:Another option is to forget the game tree and instead do some nice reinforcement learning. It doesn't work with infinite possible next moves but in general it's good for games that have many possible moves at each position. Or if you want something more exotic, may I suggest a co-evolutionary algorithm to optimise a rules-based script as a strategy?

I don't know neither. :oops: :)

epicurus
Posts: 10
Joined: Thu Apr 11, 2013 3:41 pm UTC

Re: Combinatorial game with infinite width game-tree

Postby epicurus » Mon Apr 15, 2013 10:12 am UTC

My original goal was to design a undecidable game with a finite number of turns, that is a game which cannot even in principle be played perfectly by any algorithm.

I don't think Infinito is undecidable because I believe there is a upper limit to good moves, but I would like to have a mathematical proof about it. :wink:

User avatar
Xenomortis
Not actually a special flower.
Posts: 1455
Joined: Thu Oct 11, 2012 8:47 am UTC

Re: Combinatorial game with infinite width game-tree

Postby Xenomortis » Mon Apr 15, 2013 10:20 am UTC

I'd have expected undecidability to have been achieved the minute you allowed each player to have pick an unbounded natural number for each stone.
Image

User avatar
LaserGuy
Posts: 4585
Joined: Thu Jan 15, 2009 5:33 pm UTC

Re: Combinatorial game with infinite width game-tree

Postby LaserGuy » Mon Apr 15, 2013 4:58 pm UTC

epicurus wrote:
Роберт wrote:
LaserGuy wrote:you can always place a stone that is one point larger than the opponent's largest stone--you're only hurting yourself to play stones that are any larger than this


I'm not convinced this is true.


I'm not convinced too, because we are not taking into account the winning condition and the topological proprieties of the board, of the movement of the pieces and the blocking neutral stones.


I don't see why this matters. If my opponent's largest stone is a 5, then stones of value 6+ are all functionally equivalent. If the goal is to minimize your score, it seems doubtful that there'd be any strategic benefit to overplays of this nature.

User avatar
Yakk
Poster with most posts but no title.
Posts: 11129
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: Combinatorial game with infinite width game-tree

Postby Yakk » Tue Apr 16, 2013 8:04 pm UTC

There may or may not be an advantage to playing a 7 when the highest enemy stone is a 5 currently, because maybe you intend to later play your 6, and reclaim the 7.

Had you played the 6 first, the reclaim would leave the board in a strictly worse position.

What is worse is that your threat of being able to play that 6 and reclaim that 7 is something your enemy has to take into account, and may change the enemies decisions, so even if you don't (or cannot) do the 6 remove 7.

Basically, the "but not the stone you moved" subrule makes playing higher stones possibly optimal.
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

Draconaes
Posts: 44
Joined: Fri Jan 04, 2013 7:20 pm UTC

Re: Combinatorial game with infinite width game-tree

Postby Draconaes » Tue Apr 16, 2013 10:39 pm UTC

LaserGuy wrote:
epicurus wrote:
Роберт wrote:
LaserGuy wrote:you can always place a stone that is one point larger than the opponent's largest stone--you're only hurting yourself to play stones that are any larger than this


I'm not convinced this is true.


I'm not convinced too, because we are not taking into account the winning condition and the topological proprieties of the board, of the movement of the pieces and the blocking neutral stones.


I don't see why this matters. If my opponent's largest stone is a 5, then stones of value 6+ are all functionally equivalent. If the goal is to minimize your score, it seems doubtful that there'd be any strategic benefit to overplays of this nature.


(Define "Capture" as process by which a stone moves adjacent to an enemy stone in order to replace stone(s) with neutrals)

I'd have to play a game to see how useful this might be, but if you play a 7 in that situation, you can later still play your unused 6. Additionally, if you are not using your highest stone for capturing, you can remove your highest stone, so it doesn't matter how high a value it is.

Also, playing a 7 forces the opponent to use an even higher stone if they wish to capture it (assuming all lower value stones of yours have been blocked off already).

edit: pretty much ninja'd

Surfer
Posts: 54
Joined: Sat Aug 11, 2012 6:26 pm UTC

Re: Combinatorial game with infinite width game-tree

Postby Surfer » Fri Apr 26, 2013 9:18 pm UTC

Without loss of generality, if the maximum number on the board is M, and the board currently has N open spaces, then you can limit yourself to playing numbers not greater than then M+(N^2). That is high enough that if you and your opponent decide to play future numbers in a pattern like a binary search, you'll never run out of space between numbers before the game ends. So playing M+(N^2) is just as good or bad as playing any number higher than that.

The game is guaranteed to have finite length. It is equivalent to having a finite branching factor. Therefore, the game does have a solution. Either the first player always wins, or the second player. But discovering which is the case, looks nontrivial.

The next step would be to try proving PSPACE completeness for the game. But that looks nontrivial, too.

User avatar
Yakk
Poster with most posts but no title.
Posts: 11129
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: Combinatorial game with infinite width game-tree

Postby Yakk » Fri Apr 26, 2013 9:58 pm UTC

There are 2 squares.

Player 1 plays an integer in square 1. Player 2 places an integer in square 2.

If player2's integer, interpreted as a proof, demonstrates that player 1s integer, interpreted as a turning machine, halts or does not halt, then player 2 wins.

Otherwise, player 1 wins.

5 minutes per move. Adjudication time at the end may be longer than that.

This game generally is considered favorable for player 1. ;)

Variations of the game change the TM encoding, the proof encoding, and the logical framework the proof is interpreted in.
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

epicurus
Posts: 10
Joined: Thu Apr 11, 2013 3:41 pm UTC

Re: Combinatorial game with infinite width game-tree

Postby epicurus » Mon Apr 29, 2013 9:20 am UTC

Xenomortis wrote:I'd have expected undecidability to have been achieved the minute you allowed each player to have pick an unbounded natural number for each stone.

Why? Can you elaborate it more?

epicurus
Posts: 10
Joined: Thu Apr 11, 2013 3:41 pm UTC

Re: Combinatorial game with infinite width game-tree

Postby epicurus » Mon Apr 29, 2013 9:22 am UTC

LaserGuy wrote:
epicurus wrote:
Роберт wrote:
LaserGuy wrote:you can always place a stone that is one point larger than the opponent's largest stone--you're only hurting yourself to play stones that are any larger than this


I'm not convinced this is true.


I'm not convinced too, because we are not taking into account the winning condition and the topological proprieties of the board, of the movement of the pieces and the blocking neutral stones.


I don't see why this matters. If my opponent's largest stone is a 5, then stones of value 6+ are all functionally equivalent. If the goal is to minimize your score, it seems doubtful that there'd be any strategic benefit to overplays of this nature.

I can be wrong, but the existence of an upper limit is not obvious to me. I can see a player choosing a very high number, betting he can replace it with a neutral stone later... and the opponent have to choose to follow him or not.

epicurus
Posts: 10
Joined: Thu Apr 11, 2013 3:41 pm UTC

Re: Combinatorial game with infinite width game-tree

Postby epicurus » Mon Apr 29, 2013 9:24 am UTC

Surfer wrote:Without loss of generality, if the maximum number on the board is M, and the board currently has N open spaces, then you can limit yourself to playing numbers not greater than then M+(N^2). That is high enough that if you and your opponent decide to play future numbers in a pattern like a binary search, you'll never run out of space between numbers before the game ends. So playing M+(N^2) is just as good or bad as playing any number higher than that.

The game is guaranteed to have finite length. It is equivalent to having a finite branching factor. Therefore, the game does have a solution. Either the first player always wins, or the second player. But discovering which is the case, looks nontrivial.

The next step would be to try proving PSPACE completeness for the game. But that looks nontrivial, too.

Surfer, can you elaborate more your theory?

epicurus
Posts: 10
Joined: Thu Apr 11, 2013 3:41 pm UTC

Re: Combinatorial game with infinite width game-tree

Postby epicurus » Mon Apr 29, 2013 9:26 am UTC

Yakk wrote:There are 2 squares.
Player 1 plays an integer in square 1. Player 2 places an integer in square 2.
If player2's integer, interpreted as a proof, demonstrates that player 1s integer, interpreted as a turning machine, halts or does not halt, then player 2 wins.
Otherwise, player 1 wins.
5 minutes per move. Adjudication time at the end may be longer than that.
This game generally is considered favorable for player 1. ;)
Variations of the game change the TM encoding, the proof encoding, and the logical framework the proof is interpreted in.

Yakk, thanks for the game but I was searching for a fun and playable game. :mrgreen:

User avatar
LaserGuy
Posts: 4585
Joined: Thu Jan 15, 2009 5:33 pm UTC

Re: Combinatorial game with infinite width game-tree

Postby LaserGuy » Mon Apr 29, 2013 6:56 pm UTC

epicurus wrote:I can be wrong, but the existence of an upper limit is not obvious to me. I can see a player choosing a very high number, betting he can replace it with a neutral stone later... and the opponent have to choose to follow him or not.


Sure, but does it matter what number he chooses? Does it actually make a difference to the play whether he chooses a 7, 184, 1308489 as a "very high number"? Or does it only matter if the number chosen is greater or less than the other stones on the field? Because the number of available locations on the board is finite, I think that the number of useful values for stones to carry must also be. What the exact numerical values will be may change from game to game, but there will be a mapping between the chosen values and the functions of the stones in play.

User avatar
Qaanol
The Cheshirest Catamount
Posts: 3069
Joined: Sat May 09, 2009 11:55 pm UTC

Re: Combinatorial game with infinite width game-tree

Postby Qaanol » Mon Apr 29, 2013 7:58 pm UTC

Can you “defend” your small stones with large stones (by proximity, not interposing)?

Specifically, if you have a 0 and a 4 (possibly adjacent, possibly just nearby), and I move a 2 so it is next to them both, do I gain credit for “capturing” your 0, or does the presence of your 4 “protect” against my 2?
wee free kings

User avatar
Sizik
Posts: 1260
Joined: Wed Aug 27, 2008 3:48 am UTC

Re: Combinatorial game with infinite width game-tree

Postby Sizik » Mon Apr 29, 2013 9:46 pm UTC

If a player has no pieces on the board at the end of the game, are they assumed to have a score of 0?
she/they
gmalivuk wrote:
King Author wrote:If space (rather, distance) is an illusion, it'd be possible for one meta-me to experience both body's sensory inputs.
Yes. And if wishes were horses, wishing wells would fill up very quickly with drowned horses.

mike-l
Posts: 2758
Joined: Tue Sep 04, 2007 2:16 am UTC

Re: Combinatorial game with infinite width game-tree

Postby mike-l » Tue Apr 30, 2013 2:18 am UTC

Sizik wrote:If a player has no pieces on the board at the end of the game, are they assumed to have a score of 0?

That's not a possibility, as you always place a stone after removing any of your stones.

Anyway, this game seems to me to be equivalent to a game with a large but finite number of stones. All that matters is what sequences of higher and lower are possible after a given play, eg in a 2 square case, all initial moves are isomorphic to either 1 (no possible plays below) and 2 (a possible play below). I think the game is the same if at each move you are not allowed to play any stone higher than the the highest stone plus the number of empty squares, so you could have 64 possible choices for the opening stone, but then as few as 64 but up to 127 possible second second stone depending on how large they picked for the opener.

Edit - Maybe not, that gives isomorphic choices, but not isomorphic scores. Suppose I can make a play that the opponent can counter but will result in him having 2 stones higher than mine at the end, while I will not have to place a new higher stone. Then there can be game states where I would lose if I played 'minimally' but win if I inflated the value of my chosen stone.
addams wrote:This forum has some very well educated people typing away in loops with Sourmilk. He is a lucky Sourmilk.

User avatar
Sizik
Posts: 1260
Joined: Wed Aug 27, 2008 3:48 am UTC

Re: Combinatorial game with infinite width game-tree

Postby Sizik » Tue Apr 30, 2013 5:10 pm UTC

mike-l wrote:
Sizik wrote:If a player has no pieces on the board at the end of the game, are they assumed to have a score of 0?

That's not a possibility, as you always place a stone after removing any of your stones.

Not if you've got a 1-square board.
she/they
gmalivuk wrote:
King Author wrote:If space (rather, distance) is an illusion, it'd be possible for one meta-me to experience both body's sensory inputs.
Yes. And if wishes were horses, wishing wells would fill up very quickly with drowned horses.

mike-l
Posts: 2758
Joined: Tue Sep 04, 2007 2:16 am UTC

Re: Combinatorial game with infinite width game-tree

Postby mike-l » Tue Apr 30, 2013 5:43 pm UTC

Sizik wrote:
mike-l wrote:
Sizik wrote:If a player has no pieces on the board at the end of the game, are they assumed to have a score of 0?

That's not a possibility, as you always place a stone after removing any of your stones.

Not if you've got a 1-square board.


Fine, but that game is trivially isomorphic to (depending on your choice of null score) one of the three games: Player 1 wins, Player 1 loses, Player 1 picks who wins.


Anyway, I think it's probably true that any deterministic game with a maximum number of moves is necessarily isomorphic to a game with only finitely many moves at each stage, simply working backwards from the maximum move position. To have an infinite width game tree that isn't isomorphic to a finite one, you would have to require that the game length be arbitrarily long. I do think the bounds given (my bound of M + N and the other proposed bound of M + N^2) are both too low though, due to the scoring being the sum. I think that if S is the sum of all played stones, S*2^M should be sufficient though.
addams wrote:This forum has some very well educated people typing away in loops with Sourmilk. He is a lucky Sourmilk.


Return to “Mathematics”

Who is online

Users browsing this forum: No registered users and 11 guests