Author |
Topic: Essay by Christian Freeling on inventing games (Read 522069 times) |
|
MarkSteere
Forum Guru
Finite games rule
Gender: 
Posts: 289
|
 |
Re: Essay by Christian Freeling on inventing games
« Reply #510 on: Jul 21st, 2011, 6:24pm » |
|
on Jul 21st, 2011, 5:20am, christianF wrote:
It must have been in the air. |
|
Or in the gas.
|
|
 IP Logged |
|
|
|
christianF
Forum Moderator
Forum Guru
Arimaa player #4019
Gender:
Posts: 804
|
|
Re: Essay by Christian Freeling on inventing games
« Reply #511 on: Jul 23rd, 2011, 2:30pm » |
|
Programming Symple
Here's an update. I've had several responses from Havannah programmers and I'll pick one by the programmer of the strongest bot, that provides a good outline.
Quote:The main thing you need to understand about MCTS/UCT is that the basic algorithm works surprisingly well, but can be vastly improved by adding heuristics and understanding about how the game works.
The key question is not about branching factor or strategy. The key question is can we come up with heuristics that allow it to play a not horrible mainly random game, and does it even matter that the random games are horrible. My guess is that yes, we can come up with decent heuristics that allow semi-sensible move choices without needing to do much search, and that we can learn from those moves such that we can make smarter final move choices.
I think Voronoi Diagrams will be a decent heuristic for early move choice, as in which area, if placed, would allow largest growth or cut off the opponent the most. I think some small local patterns will be enough to make sensible growth placements and RAVE will allow learning from these not so good placements to give good final placements. The rest will be found through the normal course of MCTS. |
|
So that's not too pessimistic. Though the branching factor is impressive, it's not a main obstacle since the program can easily break down a sequence of like colored placements and consider them one by one.
Yet, for comparison, playing against the best bots still reveals very good programs playing mediocre games of Havannah.
I should know, because my current rank at LG is #21. How mediocre can you get? But I still beat the bots.
RAVE is a programming language able to handle huge amounts of data in a way that suits the search protocols, but that's about all I understood so far. Any insights are welcome.
Edit - I replied:
On the face of it it would seem easier than for havannah. But I'm not convinced that it indeed is. The bot would break down a multimove to individual moves and take them one by one. Humans consider them in relation, during 'processing'. Moreover the sequential approach takes calculation time for every separate move.
The Voronoi diagrams are directly linked to the value of the group penalty. 'P' determines how much space a new group must have available to grow to (at least) neutral in the final count.
I'll have to read a bit more about RAVE and the role it plays in the programs.
I'm not in any particular hurry. Symple is a game with an innovative move protocol that brings some unusual dilemmas to the world of 'simple games that are hard to program'. A real challenge as far as I can see.
It may well be that Sygo is even harder to program (tactics run a very long trajectory, you can kill a group long before it actually dies) and in that case I think programmers will figure that out themselves eventually, and hopefully find it more challenging than Go.
But Symple is the fundamental representative of its theme. Sygo isn't. And, though chess programmers might disagree, I feel advances in game programming should be made against games that are as 'basic' as possible. The only thing to learn from Chess programming is Chess programming, not how the human mind plays.
|
| « Last Edit: Jul 24th, 2011, 2:43pm by christianF » |
IP Logged |
|
|
|
christianF
Forum Moderator
Forum Guru
Arimaa player #4019
Gender:
Posts: 804
|
|
Re: Essay by Christian Freeling on inventing games
« Reply #512 on: Jul 24th, 2011, 4:22pm » |
|
Programming Symple
Here's another update. I appreciate that Timo Ewalds, programmer of Castro (a strong Havannah program) has no objection to be cited on the subject. So here he elaborates regarding my answer.
on Jul 23rd, 2011, 2:30pm, christianF wrote:| On the face of it it would seem easier than for havannah. But I'm not convinced that it indeed is. The bot would break down a multimove to individual moves and take them one by one. Humans consider them in relation, during 'processing'. Moreover the sequential approach takes calculation time for every separate move. |
|
It is likely quite a bit harder than Havannah due to the large amount of moves. It's not quite clear yet how to represent multi-moves like this. Even still, it is quite doable to make the programs only consider a smaller subset of the moves. The true branching factor is something like the factorial of the number of groups, but if each can be considered independently, that makes it much smaller. Even if neighbouring pairs in the voronoi diagram need to be considered, that's still less than N^2, which is big but not absurdly huge. Go uses quite a few learned patterns to suggest good moves, as most of them are bad at any given time. There isn't a large set of games to learn from here, but I'd guess that patterns will work similarly well in Symple.
Quote:| The Voronoi diagrams are directly linked to the value of the group penalty. 'P' determines how much space a new group must have available to grow to (at least) neutral in the final count. |
|
Exactly. Voronoi diagrams are not that slow to generate, and while they wouldn't be very accurate, they would give a fairly good approximation.
They would show which groups are next to each other and may be worth joining and suggesting which empty areas are big and worth attacking.
Quote:| I'll have to read a bit more about RAVE and the role it plays in the programs. |
|
Basic UCT only uses the outcome of the random game to add experience to the tree. RAVE is based on the realisation that the win is made up of good moves even if they were chosen randomly, and so gives a bonus to making those winning moves earlier in the tree. It is good at finding moves that are good on average and encouraging them to be explored earlier. This works great in Go and Havannah and other games where moves made later on are valid earlier, and the order in which they are made has little relevance. This would not work in Chess for example.
Quote:| I'm not in any particular hurry. Symple is a game with an innovative move protocol that brings some unusual dilemmas to the world of 'simple games that are hard to program'. A real challenge as far as I can see. |
|
As interesting as Symple is, I'm not in any hurry to work on it. I'm currently writing my masters thesis, titled "Playing and Solving Havannah". I've got a few more improvements to Castro I may put live on LG soon too. Once my thesis is done I'm planning on open sourcing Castro so others can read it, learn from it, and improve it. I'd like to encourage more discussion on a solid platform.
Quote:It may well be that Sygo is even harder to program (tactics run a very long trajectory, you can kill a group long before it actually dies) and in that case I think programmers will figure that out themselves eventually, and hopefully find it more challenging than Go.
But Symple is the fundamental representative of its theme. Sygo isn't. And, though chess programmers might disagree, I feel advances in game programming should be made against games that are as 'basic' as possible. The only thing to learn from Chess programming is Chess programming, not how the human mind plays. |
|
There certainly are many general purpose game playing algorithms, but it'll be a long time before they are good enough to play at human level on these harder games like Go, Havannah, Symple or Sygo. To be fair though, humans don't use a general algorithm either. We also learn game specific strategies, tactics and patterns. There are few programs that continually learn through playing more games the way humans do, but that may come one day too.
|
|
IP Logged |
|
|
|
christianF
Forum Moderator
Forum Guru
Arimaa player #4019
Gender:
Posts: 804
|
|
Re: Essay by Christian Freeling on inventing games
« Reply #513 on: Jul 30th, 2011, 8:11am » |
|
Here's an endgame position in Pommel, a checkers variant invented by Michael Howe of Connecticut, USA in 2010. It has two interesting features found in no other checkers variant, linear capture and compulsory alignment with opposing pieces for captains (kings).
Several games contributed to Pommel's emergence. Hexdame inspired the general concept of checkers on a hexagonal tesselation. Dameo inspired linear movement. Linear capture by leaping however, is unique to Pommel. Mark Steere's Mad Bishops inspired the "movement to align" rule for captains, the rule that eventually goes a long way in preventing the game from ending in a draw. But does it go all the way?
The game has no hard finitude: the position shown allows cycles. The question is does it have soft finitude? A game has soft finitude if and only if both players are required to cooperate to reach a draw.
Zillions gives a white (to move) win in 13 in the above position. Zillions doesn't make mistakes in establishing a win (I haven't tried to find it, the info comes from Michael).
So this position gives no clue regarding the general question of soft finitude versus no finitude. What is required to declare a game non-finite is a position where one player can force a draw against the best opposition.
A nice puzzle for those who like puzzles 
Pommel rules
|
|
IP Logged |
|
|
|
MarkSteere
Forum Guru
Finite games rule
Gender:
Posts: 289
|
|
Re: Essay by Christian Freeling on inventing games
« Reply #514 on: Jul 30th, 2011, 2:58pm » |
|
on Jul 30th, 2011, 8:11am, christianF wrote:
A game has soft finitude if and only if both players are required to cooperate to reach a draw.
|
|
I'm not buying your "soft finitude" nonsense, Christian. Soft finitude does exist, but only in games with a random element such as Backgammon. Not in abstract games such as Pommel.
One could definitely have a non-cooperative draw in an abstract game anointed "softly finite" by the intuitive one, lol, in a manner inexplicably unintuited.
|
|
IP Logged |
|
|
|
christianF
Forum Moderator
Forum Guru
Arimaa player #4019
Gender:
Posts: 804
|
|
Re: Essay by Christian Freeling on inventing games
« Reply #515 on: Jul 30th, 2011, 3:50pm » |
|
on Jul 30th, 2011, 2:58pm, MarkSteere wrote:| Soft finitude does exist, but only in games with a random element such as Backgammon. Not in abstract games such as Pommel. |
|
Since according to you it exist only in games with a random element, and since it can exist only by defining it, please enlighten us with a definition.
Since it can exist only by defining it, there's nothing to keep me from doing so in the realm of abstract games.
So I gave a definition, if only to clarify the Pommel puzzle. That the position contains cycles makes that players can cooperate to reach a draw (for whatever reason).
Your own Cage has no cycles (how could it) hence the players reach an end regardless of their intentions. I'm not sure if you understand the difference, but let's say you do.
The latter case one could call 'hard finite'. So Pommel is not 'hard finite'. In that case it must be 'non-finite' or 'soft finite'.
'Non-finite' means that there are cycles that can be enforced by one side, like keeping a king in check in Chess.
'Soft finite' means that one side can break any cycle and win.
In Jump Sturdy a one piece against one piece game is always a win for one side, but both pieces can move sideways, so nothing prevents the players from endlessly doing so.
It's finite, unless both players cooperate to reach a draw. Soft finite by definition ... there's nothing to buy, really.
Claiming not to buy this nonsense shows the genius of showing one's intelligence by hiding it  .
|
|
IP Logged |
|
|
|
MarkSteere
Forum Guru
Finite games rule
Gender:
Posts: 289
|
|
Re: Essay by Christian Freeling on inventing games
« Reply #516 on: Jul 30th, 2011, 4:44pm » |
|
on Jul 30th, 2011, 3:50pm, christianF wrote:
In Jump Sturdy a one piece against one piece game is always a win for one side, but both pieces can move sideways, so nothing prevents the players from endlessly doing so.
|
|
Great. In a game of Checkers with only one checker on the board, the guy with no checkers loses. You've made a point.
It's your burden to you to prove Pommel is soft finite, Christian, not the burden of others to disprove it. It's your claim.
|
|
IP Logged |
|
|
|
christianF
Forum Moderator
Forum Guru
Arimaa player #4019
Gender:
Posts: 804
|
|
Re: Essay by Christian Freeling on inventing games
« Reply #517 on: Jul 30th, 2011, 4:54pm » |
|
on Jul 30th, 2011, 4:44pm, MarkSteere wrote:| Great. In a game of Checkers with only one checker on the board, the guy with no checkers loses. You've made a point. |
|
on Jul 30th, 2011, 3:50pm, christianF wrote:| I'm not sure if you understand the difference, but let's say you do. |
|
I was too optimistic there, obviously 
on Jul 30th, 2011, 4:44pm, MarkSteere wrote:| It's your burden to you to prove Pommel is soft finite, Christian, not the burden of others to disprove it. It's your claim. |
|
No Mark, it's not my claim, that was the puzzle
on Jul 30th, 2011, 8:11am, christianF wrote:| The game has no hard finitude: the position shown allows cycles. The question is does it have soft finitude? |
|
Or are you dyslexic?
|
| « Last Edit: Jul 30th, 2011, 5:14pm by christianF » |
IP Logged |
|
|
|
MarkSteere
Forum Guru
Finite games rule
Gender:
Posts: 289
|
|
Re: Essay by Christian Freeling on inventing games
« Reply #518 on: Jul 30th, 2011, 5:22pm » |
|
on Jul 30th, 2011, 4:54pm, christianF wrote:
Showing your genius again? |
|
Who said I was a genius? I thought Kris Burm was the genius.
on Jul 30th, 2011, 4:54pm, christianF wrote:
Entirely not.
|
|
IP Logged |
|
|
|
MHowe
Forum Junior Member
Arimaa player #6693
Gender:
Posts: 6
|
|
Re: Essay by Christian Freeling on inventing games
« Reply #519 on: Jul 30th, 2011, 7:22pm » |
|
I am the inventor of Pommel. Personally, I accept Christian's definition of soft finitude as both precise and useful. Neither he nor I claim that Pommel has this property, despite Mark's attempt to put such words in our mouths. I wondered about it to Christian and he wondered about it here. I think it will be extremely difficult to prove that it does have soft finitude. Proving that it does not only takes one counterexample, so that will be easier, although it will take analysis or a brute force search to prove that there is no forced win in the counterexample.
|
|
IP Logged |
|
|
|
MarkSteere
Forum Guru
Finite games rule
Gender:
Posts: 289
|
|
Re: Essay by Christian Freeling on inventing games
« Reply #520 on: Jul 30th, 2011, 7:31pm » |
|
on Jul 30th, 2011, 7:22pm, MHowe wrote:
I am the inventor of Pommel.
...
I think it will be extremely difficult to prove that it does have soft finitude. |
|
I rest my case.
|
|
IP Logged |
|
|
|
MHowe
Forum Junior Member
Arimaa player #6693
Gender:
Posts: 6
|
|
Re: Essay by Christian Freeling on inventing games
« Reply #521 on: Jul 30th, 2011, 7:38pm » |
|
No, Mark, your "case" misrepresented the issue in the first place.
|
|
IP Logged |
|
|
|
MarkSteere
Forum Guru
Finite games rule
Gender:
Posts: 289
|
|
Re: Essay by Christian Freeling on inventing games
« Reply #522 on: Jul 30th, 2011, 8:08pm » |
|
on Jul 30th, 2011, 7:38pm, MHowe wrote:| No, Mark, your "case" misrepresented the issue in the first place. |
|
lol, Leave some bait for Christian.
|
|
IP Logged |
|
|
|
MHowe
Forum Junior Member
Arimaa player #6693
Gender:
Posts: 6
|
|
Re: Essay by Christian Freeling on inventing games
« Reply #523 on: Jul 30th, 2011, 8:26pm » |
|
Baiting is not my game.
|
|
IP Logged |
|
|
|
MarkSteere
Forum Guru
Finite games rule
Gender:
Posts: 289
|
|
Re: Essay by Christian Freeling on inventing games
« Reply #524 on: Jul 30th, 2011, 9:01pm » |
|
on Jul 30th, 2011, 8:26pm, MHowe wrote:
I'm not asking you to leave new bait, Mike. Just stop eating what's there.
|
|
IP Logged |
|
|
|
|
Home
Help
Search
Members
Login
Register
Notify of replies
Send Topic
Print