Tag Info

Hot answers tagged combinatorial-game-theory

50

Believe it or not, this problem has been studied before (in the superficially different formulation of a pizza sliced into radial slices of unequal size). It turns out that the first player can only guarantee getting $4/9$ of the pizza: there are slicings of the pizza under which the second player can get $5/9$ of the pizza. See, for example, this arxiv ...

27

Call the number of days until expiration the "freshness" of the cookie. A cookie with freshness $1$ is here (and can be eaten) today, but will be gone tomorrow; a cookie with freshness $n+1$ will have freshness $n$ tomorrow. If all the cookies' freshnesses have the same parity, then this will persist for the entire game: one player (Eve) will only see even-...

26

In 3-dimensional chess, it is possible to force checkmate starting with a finite number of rooks. As this fact still appears to be open, I'll post a method of forcing checkmate with 96 rooks, even though it should be clear that this is not optimal. You can remove some of the rooks from the method I'll give below, but I am aiming for a simple explanation of ...

24

Methods Starting from the base url http://www.cross-tables.com/annotated.php?a=1 I used a combination of Python's urllib, multiprocessing and BeautifulSoup to extract the first 10000 games. The games were parsed and turned into numpy 15x15 Boolean matrices. The matrices were then turned into graphs making an edge if two adjacent cells in the matrix were ...

19

I found a bug in the code given in Hooked's answer (which means that my original reanalysis was also flawed): one also have to check for insufficient material when assessing a draw, i.e. int(board.is_stalemate()) should be replaced with int(board.is_insufficient_material() or board.is_stalemate()) This changes things quite a bit. The probabillity of a ...

19

The point is that in the game Hex, it never hurts to have an extra piece on the board. So, suppose there is a strategy for the second player, but you are stuck with being the first player. What should you do? Well, you can place a stone on the board, and then pretend in your own mind that it isn't there! In other words, you are imagining that the other ...

18

Update: The code below has a small, but significant oversight. I was unaware that a stalemate would not be counted the same way as a board with insufficient pieces to play and this changes the answer. @Winther has fixed the bug and reran the simulations. That said, there is still value to the code being posted so I'll leave it up for anyone else to repeat ...

16

An optimum board just before the last number is played on 4x4: $$\begin{array} {|c|c|c|c|} \hline & 256 & 512 & 65536 \\ \hline 4 & 128 & 1024 & 32768 \\ \hline 8 & 64 & 2048 & 16384 \\ \hline 16 & 32 & 4096 & 8192 \\ \hline \end{array}$$ ... and then a 4 luckily falls into the empty square giving the ...

15

Player A has a winning strategy. First, Player A picks $a = 3$. Case I: Player B picks $b = 9$. Then, Player A picks $c = 1$. If Player B picks $d = 7$, Player A can pick $e$ arbitrarily. If Player B picks $d \neq 7$, Player A picks $e = 7$. Following this strategy, $\{1,3,7,9\} \subseteq \{a,b,c,d,e\}$. So Player B is forced to pick $f \in \{0,2,4,5,6,8\... 13 There are several standard texts. You may want to start with a short essay, "The History of Combinatorial Game Theory", by Richard J. Nowakowski. The paper lists the main texts you may want to consult. For a more exhaustive list of references, see "Combinatorial games: Selected bibliography with a succinct GourmetIntroduction", by Aviezri Fraenkel. Thomas ... 12 Imagine all possible positions of the game arranged in a tree structure, with the initial position at the root, and the children of position$P$being the positions that are reachable in one move from$P$by the player whose turn it is to go next. The leaves of the tree are the ending positions in which one of the other player has won, since there are no ... 10 This is a most intriguing problem and took many, many, many thinking hours to solve, I even wrote a script to better understand it. It is possible for the sinners (players) to win every time. The number of players playing is irrelevant and the number of numbers they choose per turn is irrelevant as long as the players get to choose more numbers than the ... 10 Clean-up on previous edits The greedy strategy may be described, as stated in the OP, for large enough$n$, as locally optimal number-picking so as to net the most points on each individual turn. This fails for$1\leq n\leq 500$for the following$n:$$$4, 9, 25, 28, 29, 42, 52, 53, 54, 58, 59, 60, 61, 66, 77, 86, 102, \ 103, 104, 108, 109, 114, 115, 117, ... 10 This problem reminds me of the first problem, "Coins in a Row", in Peter Winkler's Mathematical Puzzles: A Connoisseur's Collection. There are quite a number of discussions of this problem online, for example here's a blog post that looks to maximize a linear version of this problem. Curiously, with the linear version of the problem (where players can ... 9 There is some discussion of this topic at the very end of the second edition (2000) On Numbers and Games by Conway. He describes work by himself, Simon Norton, and Martin Kruskal to define integration. According to the description, it looked good for a while, producing workable logarithm function in terms of the integral of x^{-1}, but then got stuck, and ... 9 It turns out that the maximum possible diameter uses the full hundred tiles! My friend Carl illustrated this in 2008 in a game he made up, here: http://www.cross-tables.com/annotated.php?u=2493#0# . Thanks for the question! 9 X takes 4 Y picks some amount: c X then takes 6-c Y has no option but to take the last one. 9 The m\times n knight's graph is the graph whose vertices are the squares of the m\times n chessboard, two squares being adjacent if a knight can move from one to the other. Player 2 has an obvious winning strategy on the m\times n chessboard if the corresponding knight's graph has a perfect matching; namely, he moves the knight to the square which is ... 9 I can do it with only seven switches. I need to transmit three bits to my friend. Bit one is the parity of the number of switches up among 1,3,5,7. Bit two is the parity of the number of switches up among 2,3,6,7. Bit three is the parity of the number of switches up among 4,5,6,7. I examine the initial setting, find the bits that are wrong, if any,... 8 This is known as Wythoff's game. The losing positions are (\lfloor n \varphi\rfloor, \lfloor n \varphi^2\rfloor) where \varphi is the golden ratio. An interesting way of presenting this game is to have the players move a Queen on a chessboard, which you can find at cut-the-knot here. 8 Astoundingly enough, this has already been studied. And I'm almost embarrassed to say that I'm familiar with the result. I used to freecell a lot. And FYI, 11982 is the impossible Frecell game. But I recommend entering in games -1, -2, -3, etc too. So here are some stats from some studies of freecell. Firstly, the depth of the aces, i.e. how many cards ... 8 Here's one option of a type you didn't suggest. Take any symmetric game. Modify the game as follows: After the first player's first move, give the second player the option to continue the game as usual, or to switch places, taking the first player's position and giving the (former) first player the next move as second player. Assuming that ties are ... 8 Importantly, the natural numbers with \leq 2^n binary digits already form a field F_n of order 2^{2^n} with the nim operations. Let's see how this works inductively. F_n \subset F_{n+1} is a degree 2 extension. We have the (nim) identity (2^{2^n})^2 = 2^{2^n} + 2^{2^n-1}. In other words, 2^{2^n} is a root of the irreducible polynomial T^2 -... 8 This is community wiki because it is JimmyK4542's answer with different reasoning. First note that if the final digit is 0, 2, 4, 5, 6, or 8 then the result is composite and A wins. In other words B can only win if the final digit is 1, 3, 7, or 9 and even then it is not guaranteed. A gets to choose three digits. As in JimmyK4542's answer A chooses 3 first ... 7 Every ordinal number \alpha has a canonical copy as a surreal number \hat\alpha, whose left set has as members \hat\beta for every \beta\lt\alpha, and whose right set is empty. Succinctly,$$\hat\alpha=\{\ \{\hat\beta\mathrel{:} \beta\lt\alpha\ \}\mathrel{|} \}.$$One can prove by induction that$\alpha\mapsto\hat\alpha$is isomorphism of the ... 7 In short, because — as emphasized by the last phrase of your bolded passage — having extra pieces on the board in Tic-Tac-Toe is never bad. It's not just 'having more squares' vs. 'having fewer squares'; it's that if position A is exactly position B with an extra X on it, then position A is always at least as good for player X as position B is. ... 7 Fun question. I don't have enough karma to add this as a comment, so I'll offer it up as an answer, although it is (currently) an incomplete one. Some comments The reference you link to for the$N=3$case does not say that there are$255,168$valid 3-by-3 tic-tac-toe boards, but that there are$255,168$distinct 3-by-3 tic-tac-toe games. That is, if ... 7 Here is an example of a game where the second player (B) has a winning strategy. It is more comfortable to describe it using multisets, this should lead to no confusion. Our base set has$3\times a_i$and$6\times b_i$for$i=0,1,2$, thus a total of$27$elements. The winning sets are (with indices mod$3$) the following. ($3\times a_i);\ (3\times a_i,\ a_{...

7

You seem to be inferring some unintended patterns in the truncated list as it was given. The LHS is simply supposed to be a sample of dyadic fractions which fall short of pi, chosen so that the supremum of the sample is precisely pi, and similarly the RHS a sample of dyadic fractions strictly greater than pi chosen so that the infimum is pi.

Only top voted, non community-wiki answers of a minimum length are eligible