# Tag Info

## Hot answers tagged combinatorial-game-theory

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,338

### 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

### 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,333

### 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,286

### 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

### 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
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 ...

### 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.5k

### 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 ...
• 82k

### 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.8k

### Is there a specific optimal first move for white or black?

From a game-theory standpoint, from each opening, either: White can win for sure, Black can win for sure, Both players can force a draw. This is known as Zermelo's theorem and it is true to any ...
• 4,338
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 ...
• 3,983
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,338
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 ...
• 3,007
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.5k
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,338
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 ...
• 14.3k
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,338
1 vote
Accepted

### How many possible starting moves are there in Abalone?

I agree with 44. Here's my break down: Diagonal X2 (once for each diagonal direction): 6 moves with a single marble 5 in-line moves with 2 marbles 4 broadside moves with 2 marbles 3 in-line moves ...
• 17.8k
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 ...
• 3,007
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

### 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 ...
• 218

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