Recommend
7 
 Thumb up
 Hide
96 Posts
Prev «  1 , 2 , 3 , 4  Next »   | 

Abstract Games» Forums » General

Subject: On the pie rule and its use to balance 2-player abstract games rss

Your Tags: Add tags
Popular Tags: [View All]
Joe Joyce
United States
Yonkers
New York
flag msg tools
designer
Avatar
mbmbmbmbmb
twixter wrote:
joejoyce wrote:
NJames wrote:
Ah. As I recall it, Checkers used the cards because best play produces a draw and the best players were able to do it. So the goal of the cards was not the goal of the pie rule.

Has anyone considered how the pie rule formalizes what might occur informally among players in love with a game like Hex? First posit that they love the game. Then that they play frequently and get decently skilled at it. But the challenge is that before too long they find that the first player wins after opening with F6, which is clearly the strongest move. What do they do? By agreement they stop opening with F6, and they continue exploring the game.

Pie rule is a protocol that formalizes that sort of approach to the game. And it does it in a way that guarantees the game goes on as long as there are any openings left to explore. Its quite remarkable for that.
Grin, what you're saying is that best play in checkers led to a draw, and to fix this, the game had to be slightly broken, just enough to put the issue in doubt until analysis solves those variant games of checkers, each of which will be win/lose or draw. And while the argument is similar with your Hex example, it leads me to ask what happens if you remove the F6 hex from the gameboard? Does that solve the 'problem'? (Or is your example just a convenient fiction for illustrative purposes?)
Removing F6 from playable cells for the entire game is very different from removing it from the possible first move cells. It does nothing about first player imbalance, which is the problem we are talking about in this thread. I'm not trying to be rude, but are you talking about some other problem?
I look at the first turn problem in a slightly more general way, if that's what you mean. If on the first turn a player can make a move that guarantees a specific result, win, lose or draw, with perfect play, etc, then that's a problem to me. Since I'm mostly familiar with chess variants and wargames, I've always considered my 2 options to be ignore it like chess or design around it like wargames, generally by adjusting victory conditions. Admittedly, wargames are generally adjusting for a very lopsided battle where it's not a question of which side loses but rather just how fast it happens to the essentially designated loser. These are all aspects of the same general problem: how to balance an unfair game that is only broken on the first moves; if you're past the first turn(s) and the game is fair, you're okay (until that new opening position gets analyzed enough!)

If a chess variant has a very noticeable first move advantage, it gets redesigned or junked. There's a general argument among chess variantists that white always has a first move advantage But I suspect there are games where that is not true or, if true, so slight as to be insignificant in any one game played. I designed Chieftain Chess, which certainly appears to be a chess variant, and has no white first move advantage of any significance. My 'proof' is that I will take black and pass my first turn, allowing white not one but two consecutive 'first moves', with no noticeable effect on the game results.

Now, can the same thing be done for checkers/draughts? Can a variant be designed where white can take the first turn and black pass the first turn without materially affecting game results stats? Well, I don't play checkers (also don't play Hex, but I'll get to that, too.) Still, looking at what was changed from FIDE to Chieftain, you can see checkers is pretty much halfway there already. The pieces in both games are essentially short range, although 'combat' extends range in checkers. The other big difference is a bigger board. This allows you to sort of start the game a few turns "earlier" than the first turn that has the advantage problem that requires the pie rule. Consider that in the original game you have deployed wrong, and you are fixing it by backing up a little and letting the players deploy themselves so whichever side was disadvantaged can deploy differently. No pie rule but you add a few moves onto the beginning of the game, and expand the board enough to give 'maneuvering room'. You may or may not want to make them omnidirectional. Removing the irreversibility in the game is a major change, which I used in Chieftain, and which is important for creating Chief's lack of first turn advantage.

Hex I haven't played in 50 years, and the connection game I played then was called either "Hex" or "John" because bathroom floors with hex tiling were very common mid-last century. My first mental picture was Hex was played on an hexagonally-shaped hex board of side 5, so the F6 hex would be dead center, and the most valuable one to possess in a connection game. Removing it would prevent either side from gaining a unique positional advantage. Wasn't until aftet I posted it that I remembered Hex was played on a rectangular hex board, which allowed the great cheat. Simply subtly change the shape of each board hex a tiny bit, just enough to make the square gameboard remain square, but shave 1 hex off the distance one player has to go. It's visually non-obvious and confers a great advantage; a truly fine cheat if you're into that sort of thing.

So, one way or the other, I hope I answered your question. Just in case, though, I'll restate: generally, no, I have no idea of what I'm talking about.
1 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Russ Williams
Poland
Wrocław
Dolny Śląsk
flag msg tools
designer
badge
Avatar
mbmbmb
joejoyce wrote:
I look at the first turn problem in a slightly more general way, if that's what you mean. If on the first turn a player can make a move that guarantees a specific result, win, lose or draw, with perfect play, etc, then that's a problem to me.
As noted in discussion elsewhere, this is a property of all combinatorial games (including not only Tic-Tac-Toe but also Chess, Macysburg, etc), yet I suppose you don't really have a problem with all combinatorial games...

In practice, players cannot achieve perfect play in good interesting combinatorial games, and hence there's no real reason to be bothered by a player being able to guarantee a specific result with perfect play.

Yet I notice people (not only you) often state that they have a problem with the mathematical existence of perfect play and its consequences... even as they paradoxically continue to play and enjoy combinatorial games.

Quote:
Since I'm mostly familiar with chess variants and wargames, I've always considered my 2 options to be ignore it like chess or design around it like wargames, generally by adjusting victory conditions. Admittedly, wargames are generally adjusting for a very lopsided battle where it's not a question of which side loses but rather just how fast it happens to the essentially designated loser. These are all aspects of the same general problem: how to balance an unfair game that is only broken on the first moves; if you're past the first turn(s) and the game is fair, you're okay (until that new opening position gets analyzed enough!)
FWIW: Some games permit ties, and in some such games perfect play leads to a tie, so I'm not sure that "unfair game" is truly a "general problem" (if you mean "general" in the mathematical sense (i.e. a problem which all combinatorial games share) as opposed to merely the informal sense (i.e. a common or typical problem). But that's a minor nitpick.


Theory aside, there are interesting practical problems for some asymmetrical games (played by real-world imperfect humans) which are e.g. fair in practice when experienced players play them, but unfair in practice when newbies play them (because one side is easier for newbies to play well than the other side). I.e. both sides win equally often between experienced players, but one "easier for newbies" side wins more often between newbies.

(Mr. Jack is a famous example; when newbies play, the murderer loses much more often than when experienced players play.)

I suppose that game publishers sometimes hesitate whether their target audience is casual players who don't play a game many times or serious players who explore a game more deeply. Perhaps they try for some compromise intermediate "balance" which ends up not really working perfectly for newbies or for experienced players...


About asymmetrical wargames and wargame-ish games where one side is stronger: this is a "problem" which was solved decades ago, of course, and isn't really a problem at all. (It's a feature, not a bug, that opposing forces can be very different.)

The game simply needs an appropriate victory condition. I.e. if it's merely a slugfest with no time limit to see who eliminates whom, then of course it's unfair to the player with weaker forces. But there are zillions of other possible victory conditions. E.g. a weaker defender must defend some key terrain vs a stronger attacker who has a limited amount of time to capture the terrain, or defend against a stronger attacker who must move past the defender and exit a certain number of units from the far map edge, or the weaker force only needs to eliminate one specified key unit of the attacker, or ... etc etc etc. There are many diverse ways which unequal forces make fine fun fair scenarios with appropriate victory conditions.

This is all utterly normal standard operating procedure in wargames. E.g. in the past year I had the good fortune to play a couple dozen different scenarios of Advanced Squad Leader Starter Kit with a friend; I doubt that in any of them were the forces on each side equal in strength or even similar in strength, yet most of the scenarios seemed fair and balanced, with a great variety of diverse victory conditions.


Quote:
Hex I haven't played in 50 years
!!! wow You should play Hex more often than that! It's great.
3 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
christian freeling
Netherlands
flag msg tools
designer
Avatar
mbmb
russ wrote:
Yet I notice people (not only you) often state that they have a problem with the mathematical existence of perfect play and its consequences... even as they paradoxically continue to play and enjoy combinatorial games.
I have a problem with gravity, yet I keep enjoying its consequences!
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Adams Tower
United States
Philadelphia
Pennsylvania
flag msg tools
joejoyce wrote:
There's a general argument among chess variantists that white always has a first move advantage But I suspect there are games where that is not true or, if true, so slight as to be insignificant in any one game played.

You might be interested in Dobutsu shogi, a tiny chess variant that is a proven win for the second player to move, with perfect play.
3 
 Thumb up
0.05
 tip
 Hide
  • [+] Dice rolls
Joe Joyce
United States
Yonkers
New York
flag msg tools
designer
Avatar
mbmbmbmbmb
bothros wrote:
joejoyce wrote:
There's a general argument among chess variantists that white always has a first move advantage But I suspect there are games where that is not true or, if true, so slight as to be insignificant in any one game played.

You might be interested in Dobutsu shogi, a tiny chess variant that is a proven win for the second player to move, with perfect play.
Thanks. I know there are games with a guaranteed win for the second player, but am actually unaware of any - now I know one. Might be worth a little research and a comment on the chessvariant pages. Appreciate the info.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Joe Joyce
United States
Yonkers
New York
flag msg tools
designer
Avatar
mbmbmbmbmb
christianF wrote:
russ wrote:
Yet I notice people (not only you) often state that they have a problem with the mathematical existence of perfect play and its consequences... even as they paradoxically continue to play and enjoy combinatorial games. :)
I have a problem with gravity, yet I keep enjoying its consequences!
I'm jealous! Somewhere near 70, I found I didn't enjoy it as much as I used to.
1 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Daniel Blumentritt
United States
Austin
Texas
flag msg tools
Avatar
mbmbmbmbmb
Quote:
As I think about it some more, I realize a potential problem with the pie rule. A player can choose an opening and study best play for both sides ahead of time. If they are selected to move first, they can make the move they studied and gain an advantage over their opponent, who is not likely to have concentrated on that one opening.

Yeah, it gives extra boost to knowing the strengths of specific openings, because now you might be picking an opponent for your opponent and not just for yourself.
1 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Joe Joyce
United States
Yonkers
New York
flag msg tools
designer
Avatar
mbmbmbmbmb
russ wrote:
joejoyce wrote:
I look at the first turn problem in a slightly more general way, if that's what you mean. If on the first turn a player can make a move that guarantees a specific result, win, lose or draw, with perfect play, etc, then that's a problem to me.
As noted in discussion elsewhere, this is a property of all combinatorial games (including not only Tic-Tac-Toe but also Chess, Macysburg, etc), yet I suppose you don't really have a problem with all combinatorial games... :)

In practice, players cannot achieve perfect play in good interesting combinatorial games, and hence there's no real reason to be bothered by a player being able to guarantee a specific result with perfect play.

Yet I notice people (not only you) often state that they have a problem with the mathematical existence of perfect play and its consequences... even as they paradoxically continue to play and enjoy combinatorial games. :)

Quote:
Since I'm mostly familiar with chess variants and wargames, I've always considered my 2 options to be ignore it like chess or design around it like wargames, generally by adjusting victory conditions. Admittedly, wargames are generally adjusting for a very lopsided battle where it's not a question of which side loses but rather just how fast it happens to the essentially designated loser. These are all aspects of the same general problem: how to balance an unfair game that is only broken on the first moves; if you're past the first turn(s) and the game is fair, you're okay (until that new opening position gets analyzed enough!)
FWIW: Some games permit ties, and in some such games perfect play leads to a tie, so I'm not sure that "unfair game" is truly a "general problem" (if you mean "general" in the mathematical sense (i.e. a problem which all combinatorial games share) as opposed to merely the informal sense (i.e. a common or typical problem). But that's a minor nitpick. :)
You are getting me for sloppy language, a fault I am all too familiar with, since I employ it so often. I mean 'general' in the general conversational sense, not general in the specific mathematical sense of general. Further, the problem I have is with solved games, like the small chess variant mentioned between our two comments. Shoot, if it's complex enough but solved, I could enjoy letting one player set up in the winning first move, and see if that player can hold on to the win, so you are not wrong. I just seem to have a pathological sense of fairness, so if I know there is a guaranteed result from a specific first move, it bothers me in my design parts, wherever they may be.

In a more (conversationally) general sense, I'm interested in the specific structure of the Macysburg game tree, because it has to incorporate features which would seem to complicate at least its fine structure a bit. For starters, there are not just multiple ways to win the game, there are different levels of victory based on what each side achieved in the game. Players get 1 point for occupying Macysburg; 2 points for chasing the enemy army completely off the board; and 3 points for reducing the enemy army to 20 or fewer units. So a player may score from 0 to 6 points. Subtract the smaller from the larger for the level of victory.

Since this is a military simulation, various tactics and strategies may be employed by each player. You should be able to get the situation where strategy/tactic A beats B, B beats C, and C beats A. So your path to victory depends on what your opponent does. And even if you can't get that sort of cycle, it is still the case that you must respond to your opponent's moves, and fight where you find the enemy. It's clear your level of victory depends on what your opponent's strategy is, at least partially, since the enemy army can just flee off the board.

So just what the heck does the 'game tree' actually look like in Macysburg's case, assuming there's a winner/loser instead of a draw situation? Does it always go to the 1 point win? Does it always go to the 6 point win? How do the individual pieces move each turn? Why do they move that way? Are there now multiple won/lost end points? Weren't there always? It seems to me you might well get a sheaf of winning moves in some places and times in the game, at least. And I'm not quite sure what the 'unit of interest' is. At first blush, it seems it would be the individual piece. But on further consideration, a somewhat larger "unit" might be more appropriate, the combat formation. What's the math book on variable units? :)

1 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
christian freeling
Netherlands
flag msg tools
designer
Avatar
mbmb
joejoyce wrote:
christianF wrote:
russ wrote:
Yet I notice people (not only you) often state that they have a problem with the mathematical existence of perfect play and its consequences... even as they paradoxically continue to play and enjoy combinatorial games.
I have a problem with gravity, yet I keep enjoying its consequences!
I'm jealous! Somewhere near 70, I found I didn't enjoy it as much as I used to.
Yes, quite so. I can't carry Carolientje down the stairs anymore, let alone up. But my point was that I, like Russ, sometimes encounter opinions that don't seem to recognise that fact. Something cannot be more a fact than gravity but gravity isn't quite understood. The class of games we discuss here is proven to be completely determined and that fact is totally understood. And it doesn't change anything regarding play, either by humans or machines, so I've never quite understood the problem some posters seem to have with it.
1 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Nathan James
United States
Covington
Ohio
flag msg tools
designer
mbmbmb
It seems those who have a problem with the determined nature of abstracts also tend to be a bit fuzzy on whether and how they are determined.
1 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Joe Joyce
United States
Yonkers
New York
flag msg tools
designer
Avatar
mbmbmbmbmb
christianF wrote:
joejoyce wrote:
christianF wrote:
russ wrote:
Yet I notice people (not only you) often state that they have a problem with the mathematical existence of perfect play and its consequences... even as they paradoxically continue to play and enjoy combinatorial games. :)
I have a problem with gravity, yet I keep enjoying its consequences!
I'm jealous! Somewhere near 70, I found I didn't enjoy it as much as I used to.
Yes, quite so. I can't carry Carolientje down the stairs anymore, let alone up. But my point was that I, like Russ, sometimes encounter opinions that don't seem to recognise that fact. Something cannot be more a fact than gravity but gravity isn't quite understood. The class of games we discuss here is proven to be completely determined and that fact is totally understood. And it doesn't change anything regarding play, either by humans or machines, so I've never quite understood the problem some posters seem to have with it.
Grin, so we've got 2 problems here. Your problem is that your pet keeps getting larger as you mature. We solved that in my family by getting smaller and smaller dogs, for which I'm glad, because we've had 3 - 5 in the 85 - ... oops ~40 kg - 60 kg. range. And at one time or another, I've had to carry them all. And we have lots of stairs. But now we're down to just 2 dogs, at 11.3 and 4.5 kg. I can still manage those weights.

My problem is that I lost the math at 4 dimensions or more - couldn't visualize it. And apparently if I can't 'see' something, I can't understand it. That's why I'm so interested in the exact structure of game trees. I need to see for myself how things work to understand them. And I don't see 'game tree' as a specifically useful concept when it is effectively impossible to draw. So you don't know where you are or where the game tree of winning moves is. It's difficult to tell if you're on it or anywhere near it at most times, and if you are by chance on it, which way you're going. Game tree is a nice idealized concept, but isn't useful. But game state is a nice simple concept that makes it 'easy'* to see how you get from one state to another. This seems to me to have a little bit of potential to be useful in a particular complex game, unlike an invisible game tree. Comparisons of game states and sequences of game states with known results will give indications of what parts of the game tree should/must look like.

Now let's wander a little, and just in passing mention Godel's incompleteness theorem to scare you and Russ just when you thought I was getting it. First, the pie rule and random card openings act to reduce the size of the game tree significantly. So much so that in many cases, the original game tree is pruned from this 'pied' version. This effectively creates a new game tree. It's great for those who want to look at new openings and those who want to analyze the game (to death?) My prejudice is the other way, to expand the possible game states by separating the sides a little more at the beginning, adding a little 'maneuvering room' before the original game starts. This makes the game harder to analyze to death.

Why are the game trees different for abstracts and wargames with dice-determined combat results? An abstract has 1 result from 1 action. A wargame may have multiple results for 1 action, and some of the results are impossible to achieve in the abstract game. Or are they? Yes, from the same initial game state, they are impossible, but there are other possible game states from which to start, which *can* give the 'impossible' results, albeit in a different area of the game state space. This should mean a 'game tree' has to be a trajectory through game space, which is obvious anyway, but it also means that any 2 or 3 (or any N less than the total number of separate actions in the game) game states do not in any way determine the game tree. And so, a different area of the game state space is wrong; it's the different trajectory.

The point about dice is that they are a completely separate chaotic system with no influence in their operation from the the rules, pieces, or gameboard. It is the interaction of two totally distinct chaotic systems, of which Macysburg and its parents, the old Gettysburg games, represent one system and the die/dice the other. So abstracts have a different type of trajectory through the same game space than wargames with semi-random results tables do. It's easily demonstrable with Macysburg by adding a simple table with 5-6 different results, Attacker Eliminated, Attacker Retreats full movement, Both Attacker and Defender Eliminated, Defender Retreats full movement, Defender Eliminated (and No Result, both Attacker and Defender remain in place.) The game state-space is just every single possible combination of pieces and positions the rules allow. Clearly, both trajectories exist within the game state space, and just as clearly, they must generally be different, with semi-random games being far more bushy and less guaranteed - you can still lose through nothing you can do on a generally winning line. Every abstract victory trajectory exists within the victory trajectories of the random game, although it would be rather difficult picking them out.

*Now that I've gotten all the way down here, I take back that "easy" comment! I hope I've gotten the ideas right. I don't even want to think about the equations that would describe trajectories through such a multidimensional space. Each individual game state is easy: 3 numbers: position, terrain, unit describe the entire board and contents, the board state. A 4th number, time, indicates which and whose turn it is, and makes absolutely clear "trajectory is everything".
1 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Russ Williams
Poland
Wrocław
Dolny Śląsk
flag msg tools
designer
badge
Avatar
mbmbmb
joejoyce wrote:
Now let's wander a little, and just in passing mention Godel's incompleteness theorem to scare you and Russ just when you thought I was getting it.

I don't see how Godel's theorem has any relevance here...? You never seem to refer to it again after this explicit mention!

Quote:
First, the pie rule and random card openings act to reduce the size of the game tree significantly.
For the pie rule, that seems exactly backwards: since the pie rule adds an additional decision to the game (i.e. the second player may choose on their first turn to swap colors), the pie rule does not reduce the size of the game tree, but rather increases its size. Note that every possible playthrough of the original game without the pie rule is also possible with the pie rule (when the second player chooses not to swap), plus additional playthroughs are also possible (when the second player chooses to swap). So clearly the game tree grows larger when the pie rule is added to the game.

But I agree that random card openings reduces the size of the game tree (assuming that the deck of cards does not include all possible openings but only a proper subset of them).
1 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Mircea Pauca
Romania
Bucuresti
flag msg tools
mbmbmbmbmb
The mix of abstract game and dice-type randomness is well understood e.g. for Backgammon AI's. It just adds more forced branching (21 distinct dice on 2d6, considering non-double pairs together e.g. 6-1 same as 1-6) from each reasonable decision of a player (say 3-5).
Objectives of good play become different, either a maximum probability to win from a given position, or maximum expected 'equity'.

For Backgammon, since TD-Gammon discovered temporal difference training for neural networks (then refined in engines like GNU and Snowie), it can give fine weighting of several positional factors far more accurate than most human players, even at 0-ply static evaluation. Then current computers have enough processing speed to calculate all branches 2-3 ply ahead, or random rollouts ahead (in sets of 21^n to reduce variance e.g. start with each dice-combination once, which is equivalent to a systematic tree search for the first 1-2 moves then random rollout).

So, conceptually, backgammon is not much different than, say, Chess - except winning is not certain from most any position, but each side is fighting over probabilities.

Usual wargames are conceptually the same as backgammon, but with much more complex 'moves' (what every unit does at the same time).
2 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Russ Williams
Poland
Wrocław
Dolny Śląsk
flag msg tools
designer
badge
Avatar
mbmbmb
ROMagister wrote:
The mix of abstract game and dice-type randomness is well understood e.g. for Backgammon AI's. It just adds more forced branching (21 distinct dice on 2d6, considering non-double pairs together e.g. 6-1 same as 1-6) from each reasonable decision of a player (say 3-5).
Objectives of good play become different, either a maximum probability to win from a given position, or maximum expected 'equity'.
Yes, the generalization of game tree analysis to games with probabilistic events is conceptually clear indeed, and the notion of generalizing optimum play to moves which maximize the probability of winning instead of moves which guarantee winning (or tying if winning isn't possible, or losing if tying isn't possible...)

In this sense, again the analogy of arithmetic seems applicable (to me anyway) ... Concepts like addition or prime factorization are easy enough to understand and well-defined for all integers, even if for very large numbers it's beyond the ability of our puny human brains to perform them.

So (much as it seems to pain many people to consider the possibility), optimal moves (i.e. maximizing one's probability of winning) exist in Backgammon and even complicated wargames.

(FWIW I've noticed that sometimes people are careless in their language and mix up "the existence of an optimal move" with "concrete knowledge of which specific move is optimal". Even though optimal moves (which maximize my probability of winning) exist when I play a complicated wargame like Advanced Squad Leader: Starter Kit #1, that doesn't mean that I (or anyone else) knows what the optimal moves actually are.)
1 
 Thumb up
0.02
 tip
 Hide
  • [+] Dice rolls
Joe Joyce
United States
Yonkers
New York
flag msg tools
designer
Avatar
mbmbmbmbmb
russ wrote:
joejoyce wrote:
Now let's wander a little, and just in passing mention Godel's incompleteness theorem to scare you and Russ just when you thought I was getting it.

I don't see how Godel's theorem has any relevance here...? You never seem to refer to it again after this explicit mention!
Grin, as I said in the post, it's only there to scare you. ;) I *am* slowly getting an understanding of how things work with game trees and game states, but I have a problem with sloppy language regarding game "tree", game "state", and game "state apace".
russ wrote:
joejoyce wrote:
First, the pie rule and random card openings act to reduce the size of the game tree significantly.
For the pie rule, that seems exactly backwards: since the pie rule adds an additional decision to the game (i.e. the second player may choose on their first turn to swap colors), the pie rule does not reduce the size of the game tree, but rather increases its size. Note that every possible playthrough of the original game without the pie rule is also possible with the pie rule (when the second player chooses not to swap), plus additional playthroughs are also possible (when the second player chooses to swap). So clearly the game tree grows larger when the pie rule is added to the game.

But I agree that random card openings reduces the size of the game tree (assuming that the deck of cards does not include all possible openings but only a proper subset of them).
Sloppy language. Where I said reduce the size of the game "tree", I meant the size of the entire game state-space, as you have removed the possibility of different opening moves, and all the different games that flow from them. I'm a lousy typist, and my mind gets well ahead of my fingers. I use shortcuts sometimes to catch up. I know what they mean, so when I proofread, they seem fine to me. Possibly you should take my comments cum grano salis, or at least consider that I may not be saying exactly what I mean, whether through a twisted sense of humor or sheer ineptness (although many consider both to be the same.)

Now I've reread your pie rule comment here, and find I understand what you are saying and agree, but you are actually speaking of the game tree as opposed to the game state space, as they go in opposite directions here. Guess I need to disambiguate better myself. Because it's always an amazing pain to get game rules 'perfect', or at least good enough that most people cannot screw them up like I can.

In general in this type of discussion where I have little or no knowledge, and am asking more than contributing, I find it very useful to reread the thread and related threads to maybe learn a few things.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Peter Ward
msg tools
mb
I think some of the debate around the existence, or lack thereof, of optimal moves stems around the question if some perfect moves only became perfect after the fact. In essence, can there be a combinatorial abstract game equivalent of throwing a dart at a board your opponent is moving?

There is nothing inherent about combinatorial games which states they can't be NP-Complete (non-deterministic polynomial time complete). Lemmings (PC game), some versions of Minesweeper (PC game), and Candy Crush (mobile app) are all games which lack a "solution" before the particular move was made. While it can be argued that these are either computer games, or have hidden information, there are still examples of problems which are perfect information and NP-Complete, such as Slither Link puzzles. "Unsolvable" board games also exist, but many rely on n x n infinite boards. For example, Trappist-1 (the Chess variant, not Trappist One) is unsolvable while "Chess on an Infinite Plane" is solvable even though they're both infinite because of the existence of the Hyugen piece. These are leapers which jump any number of prime squares. As prime is infinite and there are no factors, any piece following them would necessarily lose efficiency while the Hyugen has infinite options. For infinite depth on a finite board, there's no reason why a board can't have an asymptotic game-tree (sometimes referred to on the forum as "soft infinite") where it could technically go on forever, but diminishing returns results in an end. Usually these are movement/capture games, rather than placement. For infinite branching factor, being above Omega (5000) might be equivalent. This seems like a lot, but can be done. For example, Arimaa has an average branching factor of 17700.

Hypothetically, a game like Battleship where the players can move or rotate a ship after firing could be NP-Complete and make each node's backchain before and after irrelevant - similar to how modern encryption encodes each letter independently of any others. Again this has hidden information, but I'm sure someone could conceive of a competitive game utilizing the "Art Gallery Problem" where one player places/moves security cameras and the other places/moves the exhibits, etc.

Ultimately, I think that unless someone does prove P=NP (and claims the Millennium Prize ) then there is no harm in wondering if an unsolvable (and fun) game can't be made.
1 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Russ Williams
Poland
Wrocław
Dolny Śląsk
flag msg tools
designer
badge
Avatar
mbmbmb
joejoyce wrote:
Where I said reduce the size of the game "tree", I meant the size of the entire game state-space, as you have removed the possibility of different opening moves, and all the different games that flow from them.

...

Now I've reread your pie rule comment here, and find I understand what you are saying and agree, but you are actually speaking of the game tree as opposed to the game state space, as they go in opposite directions here.
What difference or distinction do you perceive between the "game tree" and the "entire game state-space"?

I would say those two terms are referring to roughly the same thing, rather than to opposite things.

The game tree consists exactly of all the possible game states plus links between many pairs of states, such that game state x links to state y exactly when a legal game move can transform state x to state y.

E.g. a simplified example: Tic-Tac-Toe has several hundred game states with many links between them. An example game state is:

. X .
. O .
X . .

and it has several successor (linked) game states, e.g.:

O X .
. O .
X . .


Another example state is:

O X X
. O .
X . O


which is a leaf in the tree (i.e. no further state is reachable from here, since this is a "game over" state).

The initial state of course is:
. . .
. . .
. . .
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Joe Joyce
United States
Yonkers
New York
flag msg tools
designer
Avatar
mbmbmbmbmb
russ wrote:
joejoyce wrote:
Where I said reduce the size of the game "tree", I meant the size of the entire game state-space, as you have removed the possibility of different opening moves, and all the different games that flow from them.

...

Now I've reread your pie rule comment here, and find I understand what you are saying and agree, but you are actually speaking of the game tree as opposed to the game state space, as they go in opposite directions here.
What difference or distinction do you perceive between the "game tree" and the "entire game state-space"?

I would say those two terms are referring to roughly the same thing, rather than to opposite things.

The game tree consists exactly of all the possible game states plus links between many pairs of states, such that game state x links to state y exactly when a legal game move can transform state x to state y.
Hm. I was under the impression that the game tree showed only the best move path(s), and pruned poor moves. The game tree, I thought, was formed with 'perfect play by both sides'. So in chess, the initial moves a3 and b1-a3 would not be in the game tree because they are not 'best' move(s?) Then just what are we talking about? As far as I can see, there is only 1 'perfect game of chess', or at most a few games all of which come to the same conclusion on the same turn, whether it's a win/lose condition or a draw. So in your example I wouldn't have expected to see the win for 'O' since best play is a draw in tic-tac-toe. And it isn't a thing, you say. Okay. Then what's the big deal with best play? You can't know what that is except through retrospection. And comparing abstracts with wargames, you see the abstract game state paths are but a tiny fraction of the wargame game state paths. Is the point that if you can collapse the wargame into an abstract, the original abstract game state paths would represent the 'winning' or an ideal strategy? It can't be, because a wargame works on chance, and its results come out in the form of a bell curve, whereas an abstract's results would be a single spike all the way at one end of that curve. The winning strategies *have* to be different for the 2 games. Which leads me to wonder if adding that simplistic 'crt' to Macysburg would give another similar but different game, or just ruin a decent abstract.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Peter Ward
msg tools
mb
The game-tree shows all possible moves until the game ends. For example, in Chess there are 20 initial moves for White, so the initial node would have 20 branches - one for each possibility. Then each of those nodes would branch to each possible move Black can play, which is also 20. Therefore there would be 400 leaves by the second ply, and so on. This can then identify perfect play by virtue of simply knowing how every move can be responded to, and then how responses can be responded to, ad nauseum. Pruning is then a method of eliminating how far down the path a possible move has to be considered. For example, If I know moving my King now results in a loss after 3 plies, then I don't have to consider what happens after 4 plies. The movement which results in the loss and any which follow no longer have to be considered.

Game trees can account for random chance, such as war games, where the tree branches are shown as joined. These are to demonstrate that the move no longer guarantees the subsequent responses, but can show possibilities all the same. You may not know if the dice is 1,2,3,4,5, or 6, but each possibility can be drawn on the game-tree, not much different than if each option was chosen directly.
2 
 Thumb up
0.02
 tip
 Hide
  • [+] Dice rolls
christian freeling
Netherlands
flag msg tools
designer
Avatar
mbmb
joejoyce wrote:
Hm. I was under the impression that the game tree showed only the best move path(s), and pruned poor moves. The game tree, I thought, was formed with 'perfect play by both sides'. So in chess, the initial moves a3 and b1-a3 would not be in the game tree because they are not 'best' move(s?) Then just what are we talking about?

Here's a game tree. It contains every possible sequence of legal moves.

It was generated top-down, looping equal positions with the same player to move back to the first appearance.

That being done it was coloured bottom-up, that is: by working back upwards from the leafs. There are two leafs, positions from which no further move is possible. One is a win by North, the other by South.
A line leading to a win is coloured green, for instance the lines leading to the leafs. It follows that a line leading to a position that has a winning line for one player, is a losing line, thus coloured red.
Proceeding in that way the whole truth of every possible position eventually emerges.

You will see the colouring by moving the mouse over it.

There's no intention embedded in the game tree: it's a plain fact. Some trees, like Othello or Hex, don't contain loops.
Usually trees are much bigger and beyond visual representation. But the 'thought procedure' for making them is the same, hence the truth of every position in any such game is a determined win, loss or draw. The fact that we can't figure out which one it is, is the blessing that allows us to play in the first place.

I hope (but frankly doubt) that this clarifies the concept.
3 
 Thumb up
0.05
 tip
 Hide
  • [+] Dice rolls
Russ Williams
Poland
Wrocław
Dolny Śląsk
flag msg tools
designer
badge
Avatar
mbmbmb
joejoyce wrote:
Hm. I was under the impression that the game tree showed only the best move path(s), and pruned poor moves. The game tree, I thought, was formed with 'perfect play by both sides'.

As others have noted: nope.

https://en.wikipedia.org/wiki/Game_tree

Quote:
Then just what are we talking about?
Maybe that wikipedia article will help.

Game trees provide a simple mathematical model of game play, which is useful for thinking about games, for analyzing (often simpler) games, for providing approaches to programming AI players, for proving general properties about games (e.g. the fundamental result that for every position a combinatorial game for which ties are impossible, either the player to move has a guaranteed win, or the player who just moved, or black, or white), etc etc.

Quote:
So in your example I wouldn't have expected to see the win for 'O' since best play is a draw in tic-tac-toe.
Hopefully you now understand better that the game tree represents all possible playouts, not just optimal playout.

Quote:
Then what's the big deal with best play?
I don't know, you tell me; you're the one who said you have a problem with it.

Quote:
And comparing abstracts with wargames, you see the abstract game state paths are but a tiny fraction of the wargame game state paths. Is the point that if you can collapse the wargame into an abstract, the original abstract game state paths would represent the 'winning' or an ideal strategy? It can't be, because a wargame works on chance, and its results come out in the form of a bell curve, whereas an abstract's results would be a single spike all the way at one end of that curve. The winning strategies *have* to be different for the 2 games. Which leads me to wonder if adding that simplistic 'crt' to Macysburg would give another similar but different game, or just ruin a decent abstract.
Certainly games with randomness are a generalization of games without randomness.

And I agree that a "typical" abstract game has a smaller game tree with fewer possible playouts than a "typical" wargame. (Though certainly there are exceptions!)

It's worth noting/reminding that a larger game tree does not automatically imply that a game is harder to play well or strategically deeper. E.g. I like to give the example of this simple game:
1. Player 1 names an integer.
2. Player 2 names a different integer.
Whoever named the larger integer wins.
This simple/stupid game has an infinitely large game tree! Larger than Chess, Go, Macysburg, etc which all have "only" finitely many possible game states. Yet it obviously has a trivially easy win for player 2 and is not at all a deep or difficult game to play well.


In any case, whether we're talking purely combinatorial games, or combinatorial games plus random transitions e.g. from combat resolution, optimal play mathematically exists, just as e.g. the prime factorizations of large million-digit integers exist even though optimal play (and prime factorizations) are not always easy/practical for our puny brains to find. Math is math. If you're not interested in theory at all, then perhaps game trees and optimal play have no interest for you (just like perhaps prime factorization might be of no interest for you); so be it, no problem!
1 
 Thumb up
0.02
 tip
 Hide
  • [+] Dice rolls
Joe Joyce
United States
Yonkers
New York
flag msg tools
designer
Avatar
mbmbmbmbmb
Thank you all for your replies. I only know what I've learned here in Abstract Games about game theory, along with whatever I've worked out correctly while thinking about things. I have no problem thinking of a game tree as what I call game state space. Did I construct a proper game tree for Macysburg by basing it on a 32x32 square array in which each cell has 3 bits of specific info, cell position on the board, terrain type, unit contained? There is another parameter, time, which on first blush, appears universal. You'd initially think "turn 13, blue's move" would apply to the whole board, but on closer examination, that's not so. Each individual unit of importance, blue or red, has its own specific (local) game turn time, and this time advances with each specific action taken in its 'local' area. This leads to micro-game states, the 'transitional states' a player-turn takes as each individual piece is chosen and moved. This is where I had a sticking point before I thought about it, because I didn't see the significant difference between rolling a die and "churning chaos" by choosing one specific piece to move in one specific direction, or not and instead choosing a different piece to move which results in the first idea being now precluded. Stepping back and considering discrete game states to be only in existence at the beginning or the end of a player-turn (which is not necessary but which makes thinking easier) makes clear the line going from a preceeding to a following state is a simple 1D line, not branched.

Thank you Peter for the visualization of a branch splitting after it leaves the node, instead of inside it - it's a much smoother picture than what I was doing, and it puts the info where it should be to illuminate the differences between abstract and crt results.

Thank you Christian, for the game tree for mini Mancala. It's a nice piece of work. And don't despair over whether I understand game trees. The general consensus is that I am at least marginally trainable despite looking at things the wrong way.

Grin, Russ, thanks for putting up with me! To understand something, I have to think it through to the point where I can 'see' it. For the concept of game tree, I had the wrong definition. And while I didn't realize the definition I thought I had was wrong, I did realize it was useless so came up with my own ideas of a game state space that included all possible game positions, and individual games as trajectories through a multidimensional, static, game state-space. That the game state space is the game tree means I just had to shift my definition of game tree over to something I'm already familiar with through considering how chess variants are similar to and different than other chess variants. (As the only active editor for a few years, I had a *lot* of opportunity to do that. In setting up an imaginary universal cataloguing system for all chess variants, I realized I was constructing the game conceptual space of chess. Shrink that down to just one game, and there's the game tree.)

As for the difference between abstract and semi-random games, once I started stepping through how game states connected to each other, it became pretty obvious what an utter idiot I'd been about the idea before. If you take the game down to micro-states [as mentioned above] and consider 1 action of a piece, it's instantly obvious that for abstracts, there is only one result, and for semi-randoms, there are multiple results *from that same starting point*. And Peter's description made that a concrete image in my idea of game tree. That's why I said abstract game trees are but a tiny fraction of the semi-random game trees, and why I look at the distribution of results as a bell curve for s-r's and as a spike at one end of the bell curve for abstracts. Now, is that idea correct, or am I missing something there?
2 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Michael Van Biesbrouck
Canada
St Catharines
Ontario
flag msg tools
designer
badge
Avatar
mbmbmbmbmb
I was surprised to see the pie rule structured so simply. I propose, instead, the Improved Marquisian Method:

Players play normally. After at least N turns per player, either player may call 'your choice' at any point during their turn. The other player picks a colour and plays it from where the game left off. If the game ends before 'your choice' is called, the game is a draw.

Since both players get a non-trivial amount of input into the position of choice (N turns each), the game is only in a potentially pre-studied position if both players wanted it there. Otherwise, players are incentivized to find a balanced position.

Santorini was supposed to use a pie rule for distributing gods, but I ended up with one too many layers of choosing. I considered a power that would basically set up a Chess problem but realized that studied positions would be a problem. The Improved Marquisian Method might solve that, but there probably is much interest in meta-powers with non-trivial rules.
1 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Russ Williams
Poland
Wrocław
Dolny Śląsk
flag msg tools
designer
badge
Avatar
mbmbmb
mlvanbie wrote:
I was surprised to see the pie rule structured so simply. I propose, instead, the Improved Marquisian Method:

Players play normally. After at least N turns per player, either player may call 'your choice' at any point during their turn. The other player picks a colour and plays it from where the game left off. If the game ends before 'your choice' is called, the game is a draw.

Since both players get a non-trivial amount of input into the position of choice (N turns each), the game is only in a potentially pre-studied position if both players wanted it there. Otherwise, players are incentivized to find a balanced position.

I don't know for sure, but I hypothesize that this would bug many players, or at least feel weird. It is arguably irrational, but I think that many players typically get emotionally attached to the side we are playing, and it would feel jarring to have to switch sides after N turns.

Heck, I've seen some people not even invoke the standard pie rule after one turn, evidently for this reason.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
christian freeling
Netherlands
flag msg tools
designer
Avatar
mbmb
russ wrote:
mlvanbie wrote:
I was surprised to see the pie rule structured so simply. I propose, instead, the Improved Marquisian Method:

Players play normally. After at least N turns per player, either player may call 'your choice' at any point during their turn. The other player picks a colour and plays it from where the game left off. If the game ends before 'your choice' is called, the game is a draw.

Since both players get a non-trivial amount of input into the position of choice (N turns each), the game is only in a potentially pre-studied position if both players wanted it there. Otherwise, players are incentivized to find a balanced position.

I don't know for sure, but I hypothesize that this would bug many players, or at least feel weird. It is arguably irrational, but I think that many players typically get emotionally attached to the side we are playing, and it would feel jarring to have to switch sides after N turns.

Heck, I've seen some people not even invoke the standard pie rule after one turn, evidently for this reason.
Generalisation of the pie rule isn't new. Actually you can use it to divide a pie between any number of kids. And I wouldn't call it 'Marquisian' either because that method is based on a preexisting initial position made by one player. A position of which he may know every nook & cranny, the twist being that his opponent gets the choice between choosing colour or moving first.

But you're right that players may dislike it because ideally a game should not need it. And that is sometimes unintentionally the case the case, for instance in some Draughts variants.
1 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Prev «  1 , 2 , 3 , 4  Next »   |