Timeline for When is a game tree the game tree of a board game?
Current License: CC BY-SA 3.0
31 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 27, 2017 at 21:32 | answer | added | Max | timeline score: 0 | |
| Dec 25, 2017 at 19:22 | comment | added | usul | @DanielR. Collins, I agree about the terminology and think it would help to have a list of "board games" that one does and doesn't want to capture in this question. Chess, checkers, Connect 4, and Go seem definitely in. How about Backgammon or Risk (include random chance)? Carcassonne (the board is free-form)? I guess we'd exclude games where there is some private-information and/or off-board "state" that determines what can happen on-board, like Ticket to Ride, Monopoly, or Scrabble. | |
| Dec 25, 2017 at 17:44 | answer | added | usul | timeline score: 1 | |
| Dec 16, 2017 at 17:34 | comment | added | Daniel R. Collins | ... More generally, would games with a random element, in which players are not deterministically choosing moves in the game tree, be counted? Would the ancient game of Snakes & Ladders count (go forward & back, perhaps endlessly)? | |
| Dec 16, 2017 at 17:33 | comment | added | Daniel R. Collins | I might caution against trying to use the phrase board game here, and recommending some other term, as there are many board games which would not satisfy the requirement of a finite game tree (cite: boardgamegeek.com). Any game in which pieces both leave and return to the board would, I think, violate this. E,g.: Risk, Sirocco, etc. Perhaps a technical definition of finite board game is required or somesuch? | |
| Dec 11, 2017 at 2:06 | comment | added | Joel David Hamkins | @immibis Didn't I make exactly the same argument in my post? Read the fifth paragraph, beginning, "Of course." | |
| Dec 10, 2017 at 12:21 | comment | added | მამუკა ჯიბლაძე | @Joel Well frankly speaking I am still thinking on what exactly do I have in mind. But yes, I am going to post an answer when I manage to find it out | |
| Dec 10, 2017 at 11:51 | comment | added | Joel David Hamkins | @მამუკაჯიბლაძე I believe that you are on to something with your comments. May I ask you kindly to elaborate on them and post as an answer? | |
| Dec 10, 2017 at 9:43 | answer | added | Michael Greinecker | timeline score: 3 | |
| Dec 10, 2017 at 7:14 | comment | added | მამუკა ჯიბლაძე | I believe any automaton-generable language may be viewed as a board game in the sense you want, no? | |
| Dec 10, 2017 at 7:13 | comment | added | მამუკა ჯიბლაძე | Another well known thing that looks very relevant to me is generating languages by automata. The language in your case is the collection of all correct sequences of moves describing an actual game each (glued together at coinciding initial subsequences to form a tree), while the automaton encoding this language will be the local description of the game itself: states will be smallest subpositions needed to formulate the rules and transitions will be moves allowed in presence of such subpositions... | |
| Dec 10, 2017 at 6:55 | comment | added | მამუკა ჯიბლაძე | I guess you are asking for something like a partial inverse for the unravelling procedure? Identifying as many bisimilar points as possible? Something like what Aczel uses in his formulation of AFA (presenting sets as rooted graphs to extend the Mostowski collapsing to arbitrary APGs). Also reminiscent of compression algorithms... | |
| Dec 10, 2017 at 6:47 | answer | added | SSequence | timeline score: 2 | |
| Dec 10, 2017 at 3:27 | comment | added | Joel David Hamkins | In any partial order, the lower cone with vertex $x$ is just the set $\{y\mid y\leq x\}$. In a game tree, the lower cone below $p$ is the game tree proceeding from position $p$. | |
| Dec 10, 2017 at 3:23 | comment | added | Tim Carson | @JoelDavidHamkins To terminate my bike-shedding for now, can I ask for a reference which will cover "lower cones"? Try as I may, I can only find the term in some papers which consider rather general situations. | |
| Dec 10, 2017 at 3:22 | answer | added | Joel David Hamkins | timeline score: 4 | |
| Dec 10, 2017 at 2:57 | comment | added | Joel David Hamkins | @TimCarson Every board game has only finitely many game states, and so the lower cones of the game tree realize only finitely many isomorphism types. This is a stronger condition than "finitely branching", and I am beginning to think that this is the actual answer to my question. That is, a game tree is the game tree of a board game just in case there are only finitely many isomorphism types of the lower cones of the tree. Each such lower cone isomorphism type corresponds to a state of the game, and the rules of the game are exactly provided by the reachability of these cones in the game tree. | |
| Dec 10, 2017 at 2:42 | comment | added | Tim Carson | Ultimately I have a clarification request. Surely people study games with a bound on branching. More strictly, there's the condition of having a finite set and function which determine the game tree. What are you looking for besides that? | |
| Dec 10, 2017 at 2:36 | comment | added | Tim Carson | (Ctd) Once we have such a situation, even in the case when the game has unbounded length (e.g. chess without 50 move rule) we can reduce it to moving on a finite set with rules. Now, we can go further and talk about a $n$-parametered family of games (e.g. taking some way to choose a starting position on an $n \times n$ chess board) and take large $n$ and ask about the description of these games. Now, the "exponential" in the answer of @zeb can take on meaning in terms of this parametered family of games, rather than just depth in the game tree. | |
| Dec 10, 2017 at 2:30 | comment | added | Tim Carson | The comment of @zeb is ambiguous, but there are many interesting assumptions that could be meant. For example, every traditional game I can think of has the property that there is a bound on the branching of the game tree. Now, we can ask further that there is a finite set $S$ of states ($S$ is independent of the current depth of the tree), and $F$ from $S$ to its powerset which gives us the transitions. This is also satisfied by most games we play. (Not satisfied by e.g. sprouts) | |
| Dec 10, 2017 at 2:14 | comment | added | Andreas Blass | @zeb In your proposed key property of board games, you probably want to add that there is an efficient algorithm that computes, for any terminal position, who won. I'm inclined to think that even more may be needed, to prevent "silly" descriptions like the following, for chess. A position after $k$ moves is described by a sequence of integers $(a_1,a_2,\dots,a_k)$, where each $a_i$ is the location of the $i$-th move in the lexicographic ordering of all moves available at the $i$-th move. | |
| Dec 10, 2017 at 1:54 | comment | added | Gerhard Paseman | If "pieces" have a bounded width (the players options are always bounded), then that should have implications on how the game tree is shaped. If players can write a number on paper and submit it as a move, there could be a continuum of branches. Gerhard "Is Not Good At Pictionary" Paseman, 2017.12.09. | |
| Dec 10, 2017 at 1:10 | history | edited | Joel David Hamkins | CC BY-SA 3.0 |
added 354 characters in body
|
| Dec 10, 2017 at 1:00 | history | edited | Joel David Hamkins | CC BY-SA 3.0 |
added 573 characters in body
|
| Dec 10, 2017 at 0:54 | comment | added | Joel David Hamkins | @zeb Your last comment is very interesting. I don't view this ultimately as a question of complexity theory, but rather just a question about formalizing the mathematics of the situation. What does it mean to say that game tree is the game tree of a board game? | |
| Dec 10, 2017 at 0:41 | comment | added | zeb | Testing whether a given game tree can be realized as a board game in the sense I described would then seem to be as hard as checking if a given boolean function (described by a truth table) can be computed by a small circuit - this is the Minimum Circuit Size Problem, and whether it is NP-complete is an open question. | |
| Dec 10, 2017 at 0:34 | comment | added | zeb | I think the key property of board games is that although there may be exponentially many positions in the game tree, each position is compactly described by a small number of bits (i.e. the positions of the pieces), and there is an efficient algorithm which takes such a compact description as input and produces as output a list of descriptions of positions which the current player can move to. | |
| Dec 9, 2017 at 23:40 | comment | added | Sylvain JULIEN | Perhaps some people from Deepmind could be helpful! | |
| Dec 9, 2017 at 23:35 | history | edited | Joel David Hamkins | CC BY-SA 3.0 |
added 22 characters in body
|
| Dec 9, 2017 at 23:20 | history | edited | Joel David Hamkins | CC BY-SA 3.0 |
added 124 characters in body
|
| Dec 9, 2017 at 23:14 | history | asked | Joel David Hamkins | CC BY-SA 3.0 |