Author |
Topic: Essay by Christian Freeling on inventing games (Read 522420 times) |
|
christianF
Forum Moderator
Forum Guru
Arimaa player #4019
Gender: 
Posts: 804
|
 |
Re: Essay by Christian Freeling on inventing games
« Reply #600 on: Aug 7th, 2011, 10:02am » |
|
on Aug 7th, 2011, 9:29am, NickBentley wrote:| It would seem so. Although there wouldn't be much satisfaction in beating bots who make mistakes like that. |
|
Losing is more expensive, so I'll gladly accept the loss of satisfaction. My claim was the bots wouldn't be able to do it. If they fail deplorably that's not my problem  .
|
| « Last Edit: Aug 7th, 2011, 10:04am by christianF » |
 IP Logged |
|
|
|
MarkSteere
Forum Guru
Finite games rule
Gender:
Posts: 289
|
|
Re: Essay by Christian Freeling on inventing games
« Reply #601 on: Aug 7th, 2011, 2:28pm » |
|
on Aug 7th, 2011, 10:00am, christianF wrote:
|
|
IP Logged |
|
|
|
christianF
Forum Moderator
Forum Guru
Arimaa player #4019
Gender:
Posts: 804
|
|
Re: Essay by Christian Freeling on inventing games
« Reply #602 on: Aug 9th, 2011, 9:45am » |
|
Chess and Arimaa, Go and Symple, Humans and Bots
Intro
I've always been interested, not so much in how good Chess or Go programs might become, but in why some games are so much harder to program than others. The answer should take into account that some games are much harder than others for humans too. I don't mean that Chess is harder than Tic-tac-toe, but, still by example, that Explocus is harder than Hex. Both are very simple structured games.
Hex is easy to read for the human mind (like it's easy to ride a bike, I'm not talking about winning the Tour de France) and hard for computers, whether by alpha-beta search or by MCTS.
Explocus is hard for humans, but a very simple evaluation function and a fairly shallow alpha-beta search already render a program that is near invincible against humans. It's implemented on the Zillions engine. Considering the game's stucture it's save to assume that MCTS will lead to a similar result.
So the degree of structural simplicity is neither linked to how difficult a game will be for humans to play, nor to how difficult it will be to program.
The human mind simply reads certain patterns a lot easier than others. Blindfold Chess is easier than blindfold Draughts (the link is dutch of course the table shows Year - Place - Player - #Games - #win - #draw - #loss - score - time). It has been suggested that the reason is that the Chess set of pieces is polyform and the Draughts set is uniform.
I know little about blindfold Hex or Go, and I would argue that blindfold Explocus is humanly impossible. "Blindfold Arimaa" on the other hand, though it shows no hits in Google yet, may be just around the corner. I'm sure players like Chessandgo or Fritzlein consider positions in their mind while not at the board.
Multistep moves and the human mind
Arimaa was constructed to be easy for humans (in the 'riding a bike' sense) and difficult for computers. It was achieved by a Chess type structure and 4-step moves.
What Arimaa is for Chess, Symple may prove to be for Go: very similar in structure, but with multiple steps per move, at least optionally.
This is based on the feeling, if not actually the experience that some inventors have, that multistep moves pose a bigger problem for bots than for humans. Omar used it in Arimaa, Nick Bentley uses it in Ketchup and is still playing around with it. I used it before in Medusa, Phalanx and Mu, and recently in Symple and Sygo.
So I feel that Chess and Arimaa are in a competition of sorts regarding the effect of multistep moves, and so imo. are Go and Symple. Or that at least is what I hope.
A comparison
Chess and Go are revered traditional games, Arimaa and Symple are new.
Chess and Arimaa use similar polyform sets of pieces on identical boards, Go and Symple use identical uniform sets of pieces on identical boards.
Chess and Arimaa are human constructions employing chosen mechanics, Go and Symple are 'organic' mechanisms of which the basic ideas point naturally to their implementation.
Chess and Arimaa programs mainly use traditional evaluation and alpha-beta pruning, a method of limited value in Go and (presumably) Symple.
Quote:Despite the difficulties with the large branching factor, all of the current best Arimaa programs use iterative-deepening depth-limited alpha-beta search at their core, although they incorporate varying degrees of additional pruning and other search enhancements. Overall, this
makes them very similar in structure to Chess programs.
Briefly, in alpha-beta search, one searches the game tree in a depth-first manner and computes the minimax value of each node, while also tracking lower (alpha) and upper (beta) bounds on the values of subtrees and pruning whenever a subtree provably cannot affect the minimax value of the root node. Since it is impossible to search the entire game tree, one imposes a depth limit, where one terminates the recursion and applies a heuristic evaluation function to estimate the minimax value of the position. Additionally by iterative-deepening, where one iteratively searches with an increasing depth limit until some time limit is exceeded, one can also search for a specified amount of time rather than to a fixed depth. To gain better alpha-beta pruning, a heuristic move-ordering function is applied to sort the moves at each node in order of likely quality.
Evaluation functions for Arimaa can be very complex. Generally, they are based on material advantage (which player has more/stronger pieces), but take into account a wide variety of positional features, such as control of traps, advancement of pieces, goal threats, and various identified strategic configurations in Arimaa known as blockades, hostages, and frames.
...
Unfortunately, random playout turns out to be a poor way to evaluate positions in Arimaa, even to the point of valuing an extra rabbit more than the elephant, because the extra rabbit better improves the chances of randomly reaching the goal! Because of this, a straightforward implementation of MCTS is barely better than uniform random play. Kozelek attempted to solve this by using only a short random playout followed by a deterministic, traditional evaluation function, but even so, the resulting agent was relatively weak.
Our own observation is that Arimaa in general seems poorly suited to random playout. There are a large number of moves in Arimaa that damage one’s own position greatly, such as sacrificing one’s own pieces in traps or opening paths for opposing rabbits to reach goal. These moves add a lot of noise and there is enough variety that it is extremely challenging to classify.
source: Move Ranking and Evaluation in the Game of Arimaa |
|
Go and (presumably) Symple employ Monte-Carlo Tree Search (MCTS), a method of limited value in Chess and Arimaa.
Quote:For a long time it was a widely held opinion that computer Go posed a problem fundamentally different to computer Chess insofar as it was believed that methods relying on fast global search compared to human experts combined to relatively little domain knowledge would not be effective for Go. Therefore, a large part of the computer Go development effort was during these times focused on ways of representing human-like expert knowledge and combining this with local search to answer questions of a tactical nature. The result of this were programs that handled many situations well but which had very pronounced weaknesses compared to their overall handling of the game. Also, these classical programs gained almost nothing from increases in available computing power per se and progress in the field was generally slow.
A few researchers grasped the potential of probabilistic methods and predicted that they would come to dominate computer game-playing, but many others considered a strong Go-playing program something that could be achieved only in the far future, as a result of fundamental advances in general artificial intelligence technology. Even writing a program capable of automatically determining the winner of a finished game was seen as no trivial matter.
The advent of programs based on Monte Carlo search starting in 2006 changed this situation in many ways, although the gap between strong human players and the strongest Go programs remains considerable.
source: Computer Go - Obstacles to high level performance (wiki) |
|
The advent of MCTS changed it all right. Without it the Havannah challenge would never even have been accepted! The difficulties encountered by the traditional evaluation methods arise in many other games, Symple and Sygo among them. Without MCTS (which does benefit from increased calculation power), attempts to program these games would most likely result in a dead end.
Chess and Go have one-step moves, Arimaa and Symple have multistep moves. Is this part of an evolution towards games that elude programming efforts?
Chess has about 10^47 legal positions, Arimaa has about 10^43 (promotion makes up for much of the difference).
In terms of game-tree complexity however, the number of leaf nodes in a full width decision tree, Chess must do with a mere 10^123 where Arimaa scores 10^402 (here's an example full width decision tree appearing if the mouse is moved over the bare tree).
These numbers are taken from Game complexity (wiki) and should be considered with caution. Yet the difference is clear.
How about Go and Symple? Go has about 10^170 legal positions and a game-tree complexity of about 10^360. Symple will not differ dramatically in terms of legal positions. That's a finite number. But Go's game-tree is not. Cycles force measures to make it finite, while Symple's game-tree is finite.
If we trim a Go tree to 360 ply (just imagine it's finite), then Go has the bulk of the leaf nodes towards the end, while Symple has the same number of possible leaves after 60 ply or so. The tree is far less deep, but of course accordingly wider. What about the game-tree complexity?
Quote:The game-tree complexity of a game is defined to be the number of nodes in shallowest full-width game tree that proves the value of the initial position. For most popular games, this is infeasible to compute, so it is very roughly approximated by taking the average branching factor to the power of the length of the average game in practice.
source: Move Ranking and Evaluation in the Game of Arimaa |
|
Symple's branching factor is impressive but foggy. Say it's 10^8 (where a player on average has 10 groups and 8 places to grow each one). With an average length of 2x30 moves that would make 10^480.
But that's a misleading figure in terms of programmability because the steps in Symple, other than those in Arimaa, can be made irrespective of their order. That makes that the move can be broken down to individual steps without much loss of accuracy.
Acknowledgement
I've made this comparison for the fun of ordering my thoughts about the similarities in relation between Chess and Arimaa on the one hand, and Go and Symple on the other. In addition I want to direct the attention of the programming community to Symple, rather than to Sygo. Symple can't be simplified, at least not as a multi-step moves game. Its bare-bones character makes it an interesting game for the MCTS programming community. Sygo will eventually get the attention it deserves of its own accord, as Havannah did. And by then I hope the progress made in programming Symple will turn out to be useful.
And talking of useful:
Useful links
Game complexity (wiki)
Analysis and Implementation of the Game Arimaa
Move Ranking and Evaluation in the Game of Arimaa
Computer Go - Obstacles to high level performance (wiki)
Go and mathematics (wiki)
Computer Chess (wiki)
|
|
IP Logged |
|
|
|
MarkSteere
Forum Guru
Finite games rule
Gender:
Posts: 289
|
|
Re: Essay by Christian Freeling on inventing games
« Reply #603 on: Aug 9th, 2011, 2:03pm » |
|
on Aug 9th, 2011, 9:45am, christianF wrote:
Multistep moves and the human mind |
|
OT - Just commenting on multistep moves in a general sense, not necessarily relating to the "human mind", lol
I like multistep moves in attack sequences. But just arbitrarily grouping ordinary moves into multi-move turns is bad architecture.
1. Contrary to popular cluelessness, grouping more moves into less turns does not increase game tree size.
2. In fact, just the opposite effectively happens. Imagine a 60 move game grouped into two 30 move turns. Not much of a game, is it? The more moves per turn, the less interaction.
The first 20 moves of your 30 move turn probably wouldn't be real strategic. The order in which they were taken wouldn't matter, a huge redundancy factor, effectively shrinking the game tree.
on Aug 9th, 2011, 9:45am, christianF wrote:
Oh enough with this "Arimaa was constructed" drivel. I construct games. (Flume, Rive) Arimaa was designed, and rather arbitrarily at that.
on Aug 9th, 2011, 9:45am, christianF wrote:
Sygo will eventually get the attention it deserves of its own accord, as Havannah did. |
|
Oh yeah. Total destiny. You're resting on your Havannah laurels.
|
|
IP Logged |
|
|
|
christianF
Forum Moderator
Forum Guru
Arimaa player #4019
Gender:
Posts: 804
|
|
Re: Essay by Christian Freeling on inventing games
« Reply #604 on: Aug 9th, 2011, 2:33pm » |
|
on Aug 5th, 2011, 2:08pm, MarkSteere wrote:
I reflexively shun conventional wisdom as a matter of policy, never more automatically than with "Nick, [you], and others", lol |
|
If we're so shunnable, why are you still here? Stalking stupidity?
|
|
IP Logged |
|
|
|
MarkSteere
Forum Guru
Finite games rule
Gender:
Posts: 289
|
|
Re: Essay by Christian Freeling on inventing games
« Reply #605 on: Aug 9th, 2011, 2:38pm » |
|
on Aug 9th, 2011, 2:33pm, christianF wrote:
You said it, not me.
|
|
IP Logged |
|
|
|
The_Jeh
Forum Guru
Arimaa player #634
Gender:
Posts: 460
|
|
Re: Essay by Christian Freeling on inventing games
« Reply #606 on: Aug 9th, 2011, 2:54pm » |
|
on Aug 9th, 2011, 2:03pm, MarkSteere wrote:
1. Contrary to popular cluelessness, grouping more moves into less turns does not increase game tree size.
2. In fact, just the opposite effectively happens. Imagine a 60 move game grouped into two 30 move turns. Not much of a game, is it? The more moves per turn, the less interaction.
|
|
What makes you think a 60-move game would still take only 60-moves to complete if the number of moves per turn changed? It could be more, it could be fewer, or it could stay the same.
Besides, the distinction between "multistep" and "single-step" is superficial. It depends on how the game is perceived. Any "multistep" game can be represented as a "single-step" game having an isomorphic game tree.
What matters is the branching factor, not the number of pieces moved per turn in the game's representation.
|
|
IP Logged |
|
|
|
MarkSteere
Forum Guru
Finite games rule
Gender:
Posts: 289
|
|
Re: Essay by Christian Freeling on inventing games
« Reply #607 on: Aug 9th, 2011, 3:04pm » |
|
on Aug 9th, 2011, 2:54pm, The_Jeh wrote:
What matters is the branching factor, not the number of pieces moved per turn in the game's representation. |
|
Right, and that's (almost) all I was trying to say. Additionally, in crude, generic, and non-scientific terms (because that's all I've got):
All else being equal, which of course it wouldn't be, but... a 60 turn, 60 move game would be a lot richer than an "equivalent" 60 move, two turn game.
|
|
IP Logged |
|
|
|
christianF
Forum Moderator
Forum Guru
Arimaa player #4019
Gender:
Posts: 804
|
|
Re: Essay by Christian Freeling on inventing games
« Reply #608 on: Aug 9th, 2011, 3:07pm » |
|
on Aug 9th, 2011, 9:45am, christianF wrote:| The tree is far less deep, but of course accordingly wider. |
|
on Aug 9th, 2011, 2:03pm, MarkSteere wrote:| 1. Contrary to popular cluelessness, grouping more moves into less turns does not increase game tree size. |
|
So that's exactly the implication of what I said, and it follow's a known pattern: presenting common knowledge as "cluefull" as opposed to everybody else's cluelessness, and implying that the poster isn't aware of this or even thinks the opposite.
Still Mark, I'm desparately trying to take you serious.
Really.
|
|
IP Logged |
|
|
|
christianF
Forum Moderator
Forum Guru
Arimaa player #4019
Gender:
Posts: 804
|
|
Re: Essay by Christian Freeling on inventing games
« Reply #609 on: Aug 9th, 2011, 3:08pm » |
|
on Aug 9th, 2011, 3:07pm, christianF wrote:Still Mark, I'm desparately trying to take you serious.
Really. |
|
Bazinga! 
|
|
IP Logged |
|
|
|
MarkSteere
Forum Guru
Finite games rule
Gender:
Posts: 289
|
|
Re: Essay by Christian Freeling on inventing games
« Reply #610 on: Aug 9th, 2011, 3:12pm » |
|
on Aug 9th, 2011, 2:33pm, christianF wrote:
...and just to hopefully discuss abstract games. I can't sugarcoat every point of contention, Christian. There are just too many of them. What are you so testy about? Sygo?
on Aug 9th, 2011, 9:45am, christianF wrote:
Sygo will eventually get the attention it deserves of its own accord |
|
The months of interminable Sygo hype would be more convincing if it weren't entirely from you.
|
|
IP Logged |
|
|
|
MarkSteere
Forum Guru
Finite games rule
Gender:
Posts: 289
|
|
Re: Essay by Christian Freeling on inventing games
« Reply #611 on: Aug 9th, 2011, 3:37pm » |
|
on Aug 9th, 2011, 3:07pm, christianF wrote:
a known pattern: presenting common knowledge as "cluefull" as opposed to everybody else's cluelessness, and implying that the poster isn't aware of this or even thinks the opposite. |
|
You have a tendency to direct insults at yourself, Christian. In this case, a rather complex one. I was only commenting on multistep turns in a general, off topic sense, having nothing to do with what you were talking about. A clue might have been the very first thing I said: "OT - Just commenting on multistep moves in a general sense".
|
|
IP Logged |
|
|
|
christianF
Forum Moderator
Forum Guru
Arimaa player #4019
Gender:
Posts: 804
|
|
Re: Essay by Christian Freeling on inventing games
« Reply #612 on: Aug 9th, 2011, 4:17pm » |
|
on Aug 9th, 2011, 3:37pm, MarkSteere wrote:| A clue might have been the very first thing I said: "OT - Just commenting on multistep moves in a general sense". |
|
Yes and I commented on one of these comments you made on multistep moves in a general sense, in which you were displaying common knowledge as your exclusive insights (as opposed to general cluelessness), and implying that I somehow said the opposite, whereas I said precisely what everyone knows: you press about the same number of positions (though not the exactly same positions) in less plies.
But why bother indeed. Consider my missing replies to be "Yes Mark, you've learned me all you could, finite insights rule".
|
| « Last Edit: Aug 9th, 2011, 4:23pm by christianF » |
IP Logged |
|
|
|
MarkSteere
Forum Guru
Finite games rule
Gender:
Posts: 289
|
|
Re: Essay by Christian Freeling on inventing games
« Reply #613 on: Aug 9th, 2011, 4:41pm » |
|
on Aug 9th, 2011, 4:17pm, christianF wrote:
you were displaying common knowledge as your exclusive insights (as opposed to general cluelessness), and implying that I somehow said the opposite, whereas I said precisely what everyone knows...
|
|
[head spinning]
Christian, I pop in on lightheaded breaks in between saxophone practice. I jump on a few grenades and toss a few of my own. There's no malice aforethought, and certainly no sophisticated plots 
I'm not trying to "catch you in your own web", or anything of that nature. Even if I were so inclined, that'd be way too complicated for me.
OT means off topic. I barely read what you wrote, and had zero understanding of it, as usual.
|
|
IP Logged |
|
|
|
MarkSteere
Forum Guru
Finite games rule
Gender:
Posts: 289
|
|
Re: Essay by Christian Freeling on inventing games
« Reply #614 on: Aug 10th, 2011, 12:33pm » |
|
on Aug 9th, 2011, 4:17pm, christianF wrote:
Consider my missing replies...
|
|
I know. It's my fault Sygo's a dud.
Christian, I can't make your game a dud. Only you can do that.
|
|
IP Logged |
|
|
|
|
Home
Help
Search
Members
Login
Register
Notify of replies
Send Topic
Print