Author |
Topic: Essay by Christian Freeling on inventing games (Read 540000 times) |
|
MarkSteere
Forum Guru
Finite games rule
Gender:
Posts: 289
|
|
Re: Essay by Christian Freeling on inventing games
« Reply #465 on: Jun 21st, 2011, 3:21pm » |
|
on Jun 21st, 2011, 2:56pm, christianF wrote: To get things in perspective, I've never considered Grabber as more than a combinatorial quickie. It is a rather inconsequential game that now appears to reveal a clear bias, for no immediately apparent reason. |
| A "combinatorial quickie" is more likely to have a problem with bias than not. It's the simplicity, and it's also the size. Combinatorials are expected to be small. A 5x6 board with Go stones is typical. I.e. very small, though there's no reason a scalable combinatorial can't be made larger - something that would probably, but not certainly, clear up the problem in this case. A program's measure of move order advantage is also a measure of the program's strength. Without knowing that, the stated advantage is meaningless.
|
|
IP Logged |
|
|
|
MarkSteere
Forum Guru
Finite games rule
Gender:
Posts: 289
|
|
Re: Essay by Christian Freeling on inventing games
« Reply #466 on: Jun 21st, 2011, 3:40pm » |
|
on Jun 21st, 2011, 3:21pm, MarkSteere wrote: A program's measure of move order advantage is also a measure of the program's strength. Without knowing that, the stated advantage is meaningless. |
| ...especially with a combinatorial, which would typically be a lot easier for a computer to evaluate than a person.
|
|
IP Logged |
|
|
|
lightvector
Forum Guru
Arimaa player #2543
Gender:
Posts: 197
|
|
Re: Essay by Christian Freeling on inventing games
« Reply #467 on: Jun 21st, 2011, 4:08pm » |
|
on Jun 21st, 2011, 2:56pm, christianF wrote:To get things in perspective, I've never considered Grabber as more than a combinatorial quickie. It is a rather inconsequential game that now appears to reveal a clear bias, for no immediately apparent reason. For a game that's an interesting property, worthy of investigation. As Greg pointed out, odd/even boardsize seems to reverse the move order advantage. The test with 2/4 men removal are to see if the advantage stays the same or reverses. I presume the former, but then, I presumed there wouldn't be much of a move order advantage to begin with. And that was a wrong assumption too. In other words, I've got no clue. That's the interesting thing. Where does the advantage 'reside'? Is there something like a NIM-like algorithm possible? P.S. Does anybody know why Clobber is played on a 5x6 board? Did it perhaps have a similar issue? |
| If you're really looking to see if there's a parity issue going on, it might also be interesting to examine 4x5, 5x6, and 5x7. Who wins on 3x3, 3x4, and 3x5?
|
|
IP Logged |
|
|
|
christianF
Forum Moderator Forum Guru
Arimaa player #4019
Gender:
Posts: 804
|
|
Re: Essay by Christian Freeling on inventing games
« Reply #468 on: Jun 21st, 2011, 4:19pm » |
|
on Jun 21st, 2011, 4:08pm, lightvector wrote: If you're really looking to see if there's a parity issue going on, it might also be interesting to examine 4x5, 5x6, and 5x7. Who wins on 3x3, 3x4, and 3x5? |
| I've just asked Greg to run 4x5 because Axiom should be able to solve it indeed. I'm just as curious as you are - with even for blue and odd for red, where to go on 4x5 I wonder ... Edit: The behaviour seems to be invariable with regard to the number of men that are removed initially (i.e. 2 or 4): Quote:Can you run a few 6x6 tests with 2 men removed at the start instead of 4?] Yes, still seeing a strong blue advantage which will likely turn out to be a guaranteed win. (see attached image). [You did that 4x4 - what does 4x4 do with 4 men removed? If that's a blue win too it would suggest some invariability regarding the number of a priori removals.] Same behavior, a guaranteed win for blue with 4 men removed. |
| Greg came with more interesting info that I'll have to look through first.
|
« Last Edit: Jun 22nd, 2011, 2:52am by christianF » |
IP Logged |
|
|
|
christianF
Forum Moderator Forum Guru
Arimaa player #4019
Gender:
Posts: 804
|
|
Re: Essay by Christian Freeling on inventing games
« Reply #469 on: Jun 25th, 2011, 7:12am » |
|
Grabber 4x5 turns out to be a blue win regardless whether 2 or 4 men are removed initially. That in itself is no surprise - it's always one or the other. The real surprise is the a-symmetry in the first place. 5x5 is a white win and 6x6 is a blue win (regardless of the number of initial removals). Axiom 'confirms' so much by already leaning one way or the other at a very modest ply depth. This suggests that a game on a 5x6 board is tricky either way. However, I lose against Axiom 6x6 red or blue so instead of considering the human factor - how many people play Clobber or Konane anyway, for that matter - I'd rather understand where the a-symmetry resides in the first place. Slow to understand as I am, I need tables. I love tables. So I've started to categorize the truth of small 2nx1 boards, and I'll follow up with nx2 boards. Just to see what's happening.
|
|
IP Logged |
|
|
|
Sconibulus
Forum Guru
Arimaa player #4633
Gender:
Posts: 116
|
|
Re: Essay by Christian Freeling on inventing games
« Reply #470 on: Jun 25th, 2011, 1:12pm » |
|
Isn't it likely that the player with the advantage varies based on the number of squares on the board, whether that number is even or odd? if this is right, 4xanything should be a win for blue, and 3x5, 3x3, 5x5 should be a win for red. (Axiom is capable of solving the game up to this size I think?)
|
|
IP Logged |
|
|
|
MarkSteere
Forum Guru
Finite games rule
Gender:
Posts: 289
|
|
Re: Essay by Christian Freeling on inventing games
« Reply #471 on: Jun 25th, 2011, 1:54pm » |
|
on Jun 25th, 2011, 7:12am, christianF wrote: The real surprise is the a-symmetry in the first place. 5x5 is a white win and 6x6 is a blue win. |
| It's not a surprise to me. I've long known of this effect which I call Nim-superposition. In crude, generic, and non-scientific terms, a combinatorial game that ends when someone doesn't have a move is only big enough for n number of turns (for a given board size). If n is odd, the game is a win for Player 1. If n is even, it's a win for Player 2. on Jun 25th, 2011, 7:12am, christianF wrote: This suggests that a game on a 5x6 board is tricky either way. |
| No, Christian, this does not suggest anything of the sort. As in Nim, every number is a win for Player 1 or a win for Player 2, with none of the numbers being "tricky either way".
|
|
IP Logged |
|
|
|
christianF
Forum Moderator Forum Guru
Arimaa player #4019
Gender:
Posts: 804
|
|
Re: Essay by Christian Freeling on inventing games
« Reply #472 on: Jun 25th, 2011, 1:56pm » |
|
on Jun 25th, 2011, 1:12pm, Sconibulus wrote:Isn't it likely that the player with the advantage varies based on the number of squares on the board, whether that number is even or odd? if this is right, 4xanything should be a win for blue, and 3x5, 3x3, 5x5 should be a win for red. (Axiom is capable of solving the game up to this size I think?) |
| Quite possible, and 4x5 is a blue win indeed. Except for 5x6 (most likely a blue win to) Axiom has solved everything up to and including 6x6. It would be nice if it were indeed that simple, and if it is there might be some clever proof of it. What's interesting is that the program 'leans' towards the winning side quite early, while still at a modest ply-depth. If 5x6 and 6x7 show this behaviour too, it would mean you're most probably right. There's one problem with the conjecture: 5x5 is a red win while the centersquare is blocked, so the number of squares was even, even then. P.S. Arty was in the process of implementing Grabber at iGGC. I've asked him to postpone that because of the extend of the move order advantage. Interesting as that may be in itself, I think there are better alternatives for iGGC.
|
« Last Edit: Jun 25th, 2011, 2:06pm by christianF » |
IP Logged |
|
|
|
MarkSteere
Forum Guru
Finite games rule
Gender:
Posts: 289
|
|
Re: Essay by Christian Freeling on inventing games
« Reply #473 on: Jun 25th, 2011, 2:33pm » |
|
on Jun 25th, 2011, 1:56pm, christianF wrote: P.S. Arty was in the process of implementing Grabber at iGGC. I've asked him to postpone that because of the extend of the move order advantage. |
| What "extent"? Just because a program wrung out some small boards? I'm sure Clobber would be just as easy to wring out at the same sizes, but people still manage to enjoy Clobber somehow. Just program it with a range of board sizes, offering a trade-off between timeliness and move order advantage.
|
|
IP Logged |
|
|
|
christianF
Forum Moderator Forum Guru
Arimaa player #4019
Gender:
Posts: 804
|
|
Re: Essay by Christian Freeling on inventing games
« Reply #474 on: Jun 26th, 2011, 12:26pm » |
|
Move order advantage in Grabber seems firmly embedded in small boards and my conjecture is that it will stay that way. On 2nx1 boards and nx2 boards the game is definitely 'feeling blue'. Of course the game is flexibly scalable so at a sufficiently large scale humans meet the limits of their powers of calculation, yet I feel the a-symmetry is too much of a bad thing. Barring the discovery of a format where things even out in terms of the numbers of won/lost positions - and that's not likely, given the picture emerging from small boards - I feel Grabber is flawed.
|
|
IP Logged |
|
|
|
MarkSteere
Forum Guru
Finite games rule
Gender:
Posts: 289
|
|
Re: Essay by Christian Freeling on inventing games
« Reply #475 on: Jun 26th, 2011, 2:34pm » |
|
on Jun 26th, 2011, 12:26pm, christianF wrote: I feel Grabber is flawed. |
| It's your call. An overwhelming first move advantage certainly ruins a game. At first I thought you were just buying into the program data, but I now sense it's more than that. As you said, Grabber was only a "quicky combinatorial" so no great loss. Monkey Queen (with pie) may have a slight second move advantage, though the data is insufficient to make a determination. Player 1 W/L/D= 41/45/0 at Game Site X. Monkey Queen rule sheet: http://www.marksteeregames.com/Monkey_Queen_rules.html
|
|
IP Logged |
|
|
|
MarkSteere
Forum Guru
Finite games rule
Gender:
Posts: 289
|
|
Re: Essay by Christian Freeling on inventing games
« Reply #476 on: Jun 27th, 2011, 12:50pm » |
|
on Jun 26th, 2011, 12:26pm, christianF wrote: Move order advantage in Grabber seems firmly embedded in small boards |
| Move order advantage is firmly embedded in all abstract games if the board is small enough. Rive can get away with small boards because of its massive stone recycling, e.g. 5x3x3 (29 cells). But even Rive has its limits. Rive rule sheet: http://www.marksteeregames.com/Rive_rules.pdf on Jun 26th, 2011, 12:26pm, christianF wrote: Of course the game is flexibly scalable so at a sufficiently large scale humans meet the limits of their powers of calculation, yet I feel the a-symmetry is too much of a bad thing. |
| The "asymmetry" you're referring to is more of a normal thing than a bad thing. Possibly even a good thing. I hate to see a designer bowled over by program data. And I don't even think Greg was trying to bowl you over. You're bowling yourself over at his expense. I love Greg. He's done an outstanding job of programming a bunch of my games. MSG downloads: http://www.marksteeregames.com/MSG_downloads.html
|
|
IP Logged |
|
|
|
MarkSteere
Forum Guru
Finite games rule
Gender:
Posts: 289
|
|
Re: Essay by Christian Freeling on inventing games
« Reply #477 on: Jun 27th, 2011, 3:24pm » |
|
It's like, "I found a ten dollar bill but I don't like it because it smells like money." You designed a combinatorial that behaves like a combinatorial. What's the problem?
|
|
IP Logged |
|
|
|
christianF
Forum Moderator Forum Guru
Arimaa player #4019
Gender:
Posts: 804
|
|
Re: Essay by Christian Freeling on inventing games
« Reply #478 on: Jun 28th, 2011, 10:39am » |
|
Grabber is a given game, which landed out of nowhere as "Konane columnified" on my table during coffee (of course), so I don't complain. But I consider it flawed. Of the possible initial positions on a 4x3 board, three quarters is a win for the second player. I feel this shadow is a long one, falling over even sized nxn boards as well as nx(n+1) boards (and actually over all sizes, it seems). Not that I want to discourage players: Greg's Axiom program is quite stong enough to beat me regardless of color, and at MindSports we'll keep it in the Pit just the same, but with the addition of these pages and a short commentary regarding its large move order advantage. 2nx1 boards nx2 boards nx3 boards I feel it's not much of a signboard though, and I've asked Arty to consider an alternative for iGGC.
|
|
IP Logged |
|
|
|
MarkSteere
Forum Guru
Finite games rule
Gender:
Posts: 289
|
|
Re: Essay by Christian Freeling on inventing games
« Reply #479 on: Jun 28th, 2011, 12:53pm » |
|
on Jun 28th, 2011, 10:39am, christianF wrote: I consider [Grabber] flawed. |
| I haven't seen anything that supports that claim. on Jun 28th, 2011, 10:39am, christianF wrote: Of the possible initial positions on a 4x3 board, three quarters is a win for the second player. |
| 1. 4x3 is teensy. Checkers, which is too small, has 32 squares - a lot more than 12. Of course Grabber has the third dimension, but stacking into that space doesn't create enough extra game tree to compensate for the teensy 4x3. 2. At least 3/4 of the first moves in Hex are wins for Player 1 - at any board size. Hence the pie rule. No biggy. on Jun 28th, 2011, 10:39am, christianF wrote: I feel this shadow is a long one... |
| One day you're promoting magical games and the next you're withdrawing a seemingly normal game from iggc development because of a perceived "long shadow". You gotta get centered.
|
|
IP Logged |
|
|
|
|