Accurding to Zermelo's theorem, in finite two-player games of perfect information in which the players move alternately and no affect of chance, one of those three possibilities is true:
First player can always win.
Second player can always win.
Both players can force a draw.
For example, Tic-Tac-Toe is known to have a strategy by both players that will ...
One of the following is true:
There is a dominant strategy for White.
There is a dominant strategy for Black.
There are strategies for both players that guarantee they don't lose, i.e. perfect play results in a draw (e.g. as in Tic-Tac-Toe).
No one knows which is true. Most experts guess that perfect play leads to a draw, and a few believe White can always ...
No - there need not always be a tie in the general case. Even in games of perfect complete information there may still be a bias towards one player. For example the game of nim cannot end in a tie, and depending on the starting position gives an advantage to either the first or second player - e.g.
Size of heaps | Result with
A | B | perfect play
For third edition rules
Here's one way how:
The numbers show when tiles are placed. Black is the first player to move and always places a meeple where the number is. Blue moves second and never places a meeple.
Proof of optimality
Meeple usage optimality:
The first player to move will have 36 turns and thus only 36 opportunities to place meeples for ...
My co-worker found what I believe is a winning strategy for the first player, but now I find earlier evidence by others as well.
This is for the original version of the game, where you can send your opponent to an already won field and he has to place his mark there. It seems that the question is still open for the updated version where he can then choose ...
This is a generalized version of @Guvante's answer.
O (player 2) always wins in 4. The diagonals are not necessary to achieve a win.
Examples are included in bold, but this strategy works for all choices made by X.
X places a piece at (a,b): (1,1)
O chooses a row that is not a, and places two pieces in that row, but not in column b: (2,2) and (2,5)
Now, O ...
Maximising the number of turns until the loss occurs is a common one.
Chess endgame tablebases often use "distance to zeroing" – the number of turns until either a reset of the count towards the fifty-move rule (that is, a capture or a pawn move) or the end of the game. This can be thought of as optimising for how close to being a draw in that way ...
The winning strategy for such a small Hex board is shown in this basic strategy guide.
Like tic-tac-toe, on a 4x4 board white will always win by opening on the main diagonal, because for every counter that black can make, there is another way for white to force the win. Once white can form a "two-bridge" by placing the second piece in a non-adjacent space ...
This sounds a lot like a strategy-stealing argument. It's often used to prove that one side of a game has an advantage, even if optimal strategy is not known. As a broad example, consider a game with the following properties:
It is a turn-based game
The starting positions are identical except Player A goes first
Player A has the option of skipping the first ...
This is mostly just intuition, but it might be helpful. The "winnable" and "unwinnable" position definitions are based on the assumption that the player in the winnable position always makes a move that puts the other player in an unwinnable position. But, if you do not assume a priori that either player plays optimally, then you have to ...
Optimal play on NxN boards where you need N in a row leads to a draw for all N > 2.
Contemporary Combinatorics, by Bela Bollobas has a proof of it. Below is a summary of this. The images below are from this book.
All board sizes 5x5 and up can be proven to be a draw by the second player employing a pairing strategy, namely where the second player plays a ...
D3C5D6E3B4C3D2C4F4 which is the same sequence Julia gave, not only answers the bonus question, but actually all questions. The least number for both players to not have an option is the 9 move wipe out, so 13 discs including the starting discs. It also is the answer to the first question, unless you want to say "one player of the two players can't make a ...
This is actually deceptively simple. A full set includes every card of that type in the game. If you possess a card in a specific set, then nobody else can complete that set. If you possess cards from every set, then no set can be completed without trading with you.
The flip side is that if there is any set that you lack cards from, then that set can ...
I have flip-flopped a few times, but think that Player 2 has an unbeatable strategy. The trick is that Player 1 needs an X in each row and each column while Player 2 needs a "box". Four O's that form a rectangle with no X's that share a row or column with said rectangle.
First two O's sharing a row with self and separated by 1 square. Never put below or ...
It is very hard to say it without browsing all possible combinations. Another question is are you asking about moves in game that make sense or any random game.
I was playing this game many years and usually one consider move choosing out of 3 maximally 5 possibilities for good move. However in mid-game there are 10-20 legal moves frequently.
You can try ...
This generalization of Tic-Tac-Toe is called m,n,k-game. (the goal is to get k in a row on a (m,n) board).
Some known bounds: (source wikipedia)
(5,5,4) is a draw.
(6,6,5) is a draw.
(7,7,5) and (8,8,5) are draws.
(15,15,5) is a win.
(9,6,6) and (7,7,6) are both draws via pairings.
When the goal is 9 or larger (k>=9) the second player can force a ...
Suppose you're playing a three player game with wheat, barley, and corn. For one of the trading players to win with wheat, the two trading players must have nine wheat between them, which is the same as the shut out player not getting any wheat.
To get a hand, we choose 9 cards out of 27. There are C(27,9) ways of doing that, where C is the binomial ...
(I'm mostly ignoring Bull and Bear rules here, but I think they can be added in with a little fiddling.)
If you just want to know whether it's possible, then it's not a question of probability but of showing that there is at least one arrangement of cards that would allow a player to win without trading. And it's pretty easy to see that this must exist, ...
You are missing a couple of important factors in your question that make it impossible to answer as it stands. Mainly that a game with perfect information available to both players doesn't mean that it is not balanced in one players favor.
While it may be true that there are games out there where it is balanced between both players it is also true that ...
There are several generalizations to tic-tac-toe. The most natural one (imho), is the m,n,k-game, which is the game of k-in-a-row played on an (m,n) board.
In (n,n,n) games, for n>2, the second player can force a draw. See m,n,k-game for many other results.
The term "dominant strategy" is generally used for games with incomplete information (or simultaneous moves, which can be analyzed as a game with incomplete information). In a deterministic game where players take turns and there is no secret information, the term "perfect play" is generally used, rather than "dominant strategy". The term "dominant strategy" ...
essentially, it seems that in a more complex game, it is more likely that there will be a draw. Connect-Four is the most complex game we have solved so far, and although the first player wins, that is due to the mathematical nature of the game (i.e., it is impossible to go back to a previous position like for one side of chess). There is no proof that either ...
The biggest piece of strategy is knowing how to move a pile of cards from one stack to the next.
The basic algorithm is a recursive algorithm.
To move n cards from stack a to stack b, you need to:
move the n-1 cards from stack a to stack c
move the nth card to stack b
move the n-1 cards from stack c to stack b.
To move a stack of three ...
For first edition (and 272 for 2nd edition which is optimal for that edition as well). This question was for the 3rd edition, but the older editions lead to different and interesting ideas so I thought I'd answer it for that as well.
A game with the most 1st edition theoretical points possible would:
Have all roads scored and all end points on separate ...