24
votes
Accepted
In two-player games with perfect information, if both players play optimally, will the game always end in a draw?
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 ...
- 4,105
21
votes
Dominant strategy in chess
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 ...
- 11.1k
9
votes
In two-player games with perfect information, if both players play optimally, will the game always end in a draw?
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, ...
- 9,283
5
votes
Is there a standard definition of "optimal losing strategy" in games with a winning strategy; Chess, Connect 4, etc?
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 ...
- 1,256
5
votes
What's the least amount of pieces on an Othello board where black or white can't make a move?
For the bonus, the shortest possible game that results in all pieces the same colour (9 moves) is here: https://www.youtube.com/watch?v=6ehiWOSp_wk
- 533
4
votes
Othello - Most number of legal moves in a given turn
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 ...
- 229
3
votes
Winning strategy for NxN Tic-Tac-Toe
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 ...
- 17.9k
3
votes
Accepted
What's the least amount of pieces on an Othello board where black or white can't make a move?
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 ...
3
votes
Can a Pit Card Game be Won if two players refuse to trade with another particular player?
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 ...
- 12.6k
3
votes
Is there a standard definition of "optimal losing strategy" in games with a winning strategy; Chess, Connect 4, etc?
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 ...
- 80.9k
1
vote
Is there a standard definition of "optimal losing strategy" in games with a winning strategy; Chess, Connect 4, etc?
The definition of "optimal" varies from game to game, but I see similarities in definitions across different game types. Generally speaking, "optimal" play is taking a game action ...
- 4,083
1
vote
Winning strategy for NxN Tic-Tac-Toe
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 ...
- 4,105
1
vote
Accepted
in Tic-tac-toe on an NxN board, what is the minimum goal (number in a row) that guarantees a tie?
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 (...
- 4,105
1
vote
Can a Pit Card Game be Won if two players refuse to trade with another particular player?
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 ...
- 2,797
1
vote
Can a Pit Card Game be Won if two players refuse to trade with another particular player?
(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 ...
- 11.2k
1
vote
Strategy for Ultimate Tic Tac Toe
The following ai-agents evaluate game-states using the following features. It is a reasonable assumption that an expert human player should consider those features as well.
AI Approaches to Ultimate ...
- 4,105
1
vote
In two-player games with perfect information, if both players play optimally, will the game always end in a draw?
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 ...
- 13.9k
1
vote
Dominant strategy in chess
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 ...
- 2,797
1
vote
Dominant strategy in chess
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 ...
- 11
1
vote
1
vote
Maximum attainable points for a single player in a two player game of Carcassonne
285
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 ...
- 208
Only top scored, non community-wiki answers of a minimum length are eligible