Difference between revisions of "Passing"

From HexWiki
Jump to: navigation, search
(Added a page on passing.)
 
(Added proof that the ability to pass does not affect the outcome.)
Line 1: Line 1:
 
To ''pass'' means not to make a move when it is one's turn to do so. It then becomes the other player's turn again.
 
To ''pass'' means not to make a move when it is one's turn to do so. It then becomes the other player's turn again.
  
The most common formulations of the rules of Hex do not envision passing as a possibility. For example, most [[online playing]] sites do not allow passing. Indeed, it is easy to see that passing is theoretically unnecessary in Hex: if passing were allowed, it is never to a player's advantage to pass. In other words, playing a piece (no matter which piece) always leaves the player in an equal or better position than passing would do.
+
The most common formulations of the rules of Hex do not envision passing as a possibility. For example, most [[online playing]] sites do not allow passing. Indeed, offering the possibility of passing is theoretically unnecessary in Hex: since passing is never to a player's advantage, a rational player in a normal game should never want to pass, and therefore the outcome of the game is not affected by whether passing is permitted or not. In other words, playing a piece (no matter which piece) always leaves the player in an equal or better position than passing would do. Nevertheless, there are a number of good reasons for why the rules of Hex (on game sites or otherwise) should include the ability to pass.
  
 
== Reasons for passing ==
 
== Reasons for passing ==
  
However, there are several theoretical and practical uses for passing:
+
There are several theoretical and practical uses for passing:
  
* Theory: many theoretical arguments about winning positions become easier to state and analyze if passing is allowed. For example, the well-known property that Hex (without the swap rule) is a [[Hex theory#No_winning_strategy_for_Blue|first-player win]] is easiest to prove with passing: if the second player had a winning strategy, the first player could simply pass, thereby effectively becoming the second player. Since this would be a winning strategy for the first player, the second player cannot have had a winning strategy.
+
* Theory: many theoretical arguments about winning positions become easier to state and analyze if passing is allowed. For example, the well-known property that Hex (without the swap rule) is a [[Hex theory#No_winning_strategy_for_Blue|first-player win]] is easiest to prove with passing: if the second player had a winning strategy, the first player could simply pass, thereby effectively becoming the second player. Since this would be a winning strategy for the first player, the second player cannot have had a winning strategy. More generally, strategy-stealing arguments are often easier to formulate if passing is permitted.
  
 
* Handicap: for unevenly matched players, the game is often more enjoyable if the more experienced player gives the less experienced player a [[handicap]]. One way of implementing a handicap is for the weaker player to be permitted two or more consecutive moves at the beginning of the game. In practice, the stronger player would do this by passing one or more times at the beginning of the game. However, since many online sites do not permit passing, playing with handicap is difficult on these sites. Players sometimes have to resort to playing deliberately weak moves instead of passing.
 
* Handicap: for unevenly matched players, the game is often more enjoyable if the more experienced player gives the less experienced player a [[handicap]]. One way of implementing a handicap is for the weaker player to be permitted two or more consecutive moves at the beginning of the game. In practice, the stronger player would do this by passing one or more times at the beginning of the game. However, since many online sites do not permit passing, playing with handicap is difficult on these sites. Players sometimes have to resort to playing deliberately weak moves instead of passing.
  
* Strength of win: sometimes a player's position is so strong that they can pull off a win even if the opponent gets two or more moves in a row. In that case, the player may choose to pass as a way of demonstrating the strength of their position to the opponent. In a friendly or teaching game, this can have a pedagogical value by illustrating a point. In a competitive game, it can be a way of making a win more impressive.
+
* Strength of win: sometimes a player's position is so strong that they can pull off a win even if the opponent gets two or more moves in a row. In that case, the player may choose to pass as a way of demonstrating the strength of their position to the opponent. In a friendly or teaching game, this can have a pedagogical value by illustrating a point about the strength of connections. In a competitive game, it can be a way of making a win more impressive.
  
 
* Losing play: once a player realizes that they will lose the game, they would customarily resign. However, sometimes resigning is not possible or desirable for some reason. For example, some game sites do not allow resigning unless a certain percentage of the board has been filled. In that case, the losing player often resorts to playing nonsense moves to allow the winning player to complete a connection as quickly as possible. Passing would be more elegant than playing nonsense moves.
 
* Losing play: once a player realizes that they will lose the game, they would customarily resign. However, sometimes resigning is not possible or desirable for some reason. For example, some game sites do not allow resigning unless a certain percentage of the board has been filled. In that case, the losing player often resorts to playing nonsense moves to allow the winning player to complete a connection as quickly as possible. Passing would be more elegant than playing nonsense moves.
 +
 +
* Strategy puzzles: many Hex strategy puzzles, such as [http://www.mseymour.ca/hex_puzzle/hexpuzzle.html Matthew Seymour's puzzles], are concerned with a particular area of the board. The object of the puzzle is to make sure that certain groups are [[strong connection|connected]] or not connected. If a player's groups are already connected, moving in that area of the board would waste a move for that player. In a real game, the player might choose to play elsewhere on the board. In a strategy puzzle, the player should be allowed to pass instead. Recognizing situations where one can or cannot pass, or equivalently, recognizing which groups are connected, is an important learning objective of the puzzles.
  
 
== The ability to pass does not affect the outcome ==
 
== The ability to pass does not affect the outcome ==
  
To do.
+
In Hex, passing never gives the player who passes an advantage. Specifically:
 +
 
 +
* If a player can win by passing, then the same player can also win by moving anywhere.
 +
 
 +
The intuitive reason for this is that, since the objective of Hex is to connect a player's two edges, having additional pieces of that player's color on the board cannot hurt the player.
 +
 
 +
More formally, consider Hex without passing. Given two Hex positions P and Q, we say that P ≤ Q if Q is obtained from P by adding zero or more red stones and removing zero or more blue stones. We claim that if Red has a winning strategy for P (with some player to move), then Red also has a winning strategy for Q (with the same player to move). This is easily proved by induction on the number of empty cells in the position P. The base case is when P has no empty cells; since we assumed P is winning for Red, Red's two edges are connected in P, and therefore in Q, so Q is also winning for Red. For the induction step, first consider the case where it is Red's turn. Red's winning strategy calls for playing in some empty cell of the position P to arrive at a new position P' that is a second-player win for Red. If the corresponding cell is empty in Q, then Red can just play there. If the corresponding cell is not empty in Q, then it must be occupied by a red stone (since P ≤ Q). In that case, Red can play anywhere. In either case, Red arrives at a new position Q' that satisfies P' ≤ Q'. Since P' is a second-player win for Red, by induction hypothesis, so is Q', and therefore Q was winning for Red. Second, consider the case where it is Blue's turn. We have assumed that Red has a second-player winning strategory for P, and we must show that Red has a second-player winning strategy for Q. Suppose Blue moves in some empty cell of Q, arriving at a new position Q'. If the corresponding cell in P is empty, imagine that Blue moves there. If the corresponding cell in P is not empty, then it must be occupied by a blue stone (since P ≤ Q). In that case, imagine Blue moves anywhere in P. Let P' be the resulting position. In either case, we have P' ≤ Q'. Since P' is a first-player win for Red, by induction hypothesis, so is Q', and therefore, since Blue's move in Q was arbitrary, Q was a second-player win for Red, as required.
 +
 
 +
The above statement, "If a player can win by passing, then the same player can also win by moving anywhere", now follows. Namely, if it is Red's turn in a position P, then passing would result in the same position P (with Blue to move), and not passing would result in a position Q with one additional red piece (and Blue also to move). Since P ≤ Q, if P is winning then so is Q.
 +
 
 +
The analogous result of course also holds from Blue's point of view.
 +
 
 +
In particular, any player who has a winning strategy with passing also has a winning strategy without passing that is just as easy to carry out. Therefore, the outcome of the game does not depend on whether passing is permitted or not.
 +
 
 +
Many sites seem to take the above fact as a reason why passing 'should not' be allowed. But it is equally valid as a reason for why passing 'should' be allowed.
  
 
== Implementations of passing ==
 
== Implementations of passing ==
Line 23: Line 39:
 
* No online playing sites currently permit passing. However, this ought to be changed.
 
* No online playing sites currently permit passing. However, this ought to be changed.
  
* The current version of the [[Smart Game Format|SGF file format]] for Hex does not provide for a passing move. It does, however, permit consecutive moves by the same player. It would be desirable to add an explicit passing move to the file format, as this would allow passing moves to be recorded and documented. For example, a comment attached to such a move might explain why the player passed (e.g., to give a handicap). This is not quite the same as simply omitting the move; for example, for some handicapping methods, after the first move, the second player can choose to swap (and then the first player will get two consecutive moves) or not to swap (and then the first player gets to move again). If there is no possibility of an explicit passing move, the second player must verbally announce "I am not going to swap", which is not elegant and will not be recorded in the game tree.
+
* The current version of the [[Smart Game Format|SGF file format]] for Hex does not provide for a passing move. It does, however, permit consecutive moves by the same player. It would be desirable to add an explicit passing move to the file format, as this would allow passing moves to be recorded and documented. For example, a comment attached to such a move might explain why the player passed (e.g., to give a handicap). This is not quite the same as simply omitting the move; for example, for some handicapping methods, after the first move, the second player can choose to swap (and then the first player will get two consecutive moves) or not to swap (and then the first player gets to move again). If there is no explicit way of passing, the second player must verbally announce "I am not going to swap" before the first player can move again. This is not elegant. A passing move would permit this information to appear in the game tree.

Revision as of 21:21, 10 October 2020

To pass means not to make a move when it is one's turn to do so. It then becomes the other player's turn again.

The most common formulations of the rules of Hex do not envision passing as a possibility. For example, most online playing sites do not allow passing. Indeed, offering the possibility of passing is theoretically unnecessary in Hex: since passing is never to a player's advantage, a rational player in a normal game should never want to pass, and therefore the outcome of the game is not affected by whether passing is permitted or not. In other words, playing a piece (no matter which piece) always leaves the player in an equal or better position than passing would do. Nevertheless, there are a number of good reasons for why the rules of Hex (on game sites or otherwise) should include the ability to pass.

Reasons for passing

There are several theoretical and practical uses for passing:

  • Theory: many theoretical arguments about winning positions become easier to state and analyze if passing is allowed. For example, the well-known property that Hex (without the swap rule) is a first-player win is easiest to prove with passing: if the second player had a winning strategy, the first player could simply pass, thereby effectively becoming the second player. Since this would be a winning strategy for the first player, the second player cannot have had a winning strategy. More generally, strategy-stealing arguments are often easier to formulate if passing is permitted.
  • Handicap: for unevenly matched players, the game is often more enjoyable if the more experienced player gives the less experienced player a handicap. One way of implementing a handicap is for the weaker player to be permitted two or more consecutive moves at the beginning of the game. In practice, the stronger player would do this by passing one or more times at the beginning of the game. However, since many online sites do not permit passing, playing with handicap is difficult on these sites. Players sometimes have to resort to playing deliberately weak moves instead of passing.
  • Strength of win: sometimes a player's position is so strong that they can pull off a win even if the opponent gets two or more moves in a row. In that case, the player may choose to pass as a way of demonstrating the strength of their position to the opponent. In a friendly or teaching game, this can have a pedagogical value by illustrating a point about the strength of connections. In a competitive game, it can be a way of making a win more impressive.
  • Losing play: once a player realizes that they will lose the game, they would customarily resign. However, sometimes resigning is not possible or desirable for some reason. For example, some game sites do not allow resigning unless a certain percentage of the board has been filled. In that case, the losing player often resorts to playing nonsense moves to allow the winning player to complete a connection as quickly as possible. Passing would be more elegant than playing nonsense moves.
  • Strategy puzzles: many Hex strategy puzzles, such as Matthew Seymour's puzzles, are concerned with a particular area of the board. The object of the puzzle is to make sure that certain groups are connected or not connected. If a player's groups are already connected, moving in that area of the board would waste a move for that player. In a real game, the player might choose to play elsewhere on the board. In a strategy puzzle, the player should be allowed to pass instead. Recognizing situations where one can or cannot pass, or equivalently, recognizing which groups are connected, is an important learning objective of the puzzles.

The ability to pass does not affect the outcome

In Hex, passing never gives the player who passes an advantage. Specifically:

  • If a player can win by passing, then the same player can also win by moving anywhere.

The intuitive reason for this is that, since the objective of Hex is to connect a player's two edges, having additional pieces of that player's color on the board cannot hurt the player.

More formally, consider Hex without passing. Given two Hex positions P and Q, we say that P ≤ Q if Q is obtained from P by adding zero or more red stones and removing zero or more blue stones. We claim that if Red has a winning strategy for P (with some player to move), then Red also has a winning strategy for Q (with the same player to move). This is easily proved by induction on the number of empty cells in the position P. The base case is when P has no empty cells; since we assumed P is winning for Red, Red's two edges are connected in P, and therefore in Q, so Q is also winning for Red. For the induction step, first consider the case where it is Red's turn. Red's winning strategy calls for playing in some empty cell of the position P to arrive at a new position P' that is a second-player win for Red. If the corresponding cell is empty in Q, then Red can just play there. If the corresponding cell is not empty in Q, then it must be occupied by a red stone (since P ≤ Q). In that case, Red can play anywhere. In either case, Red arrives at a new position Q' that satisfies P' ≤ Q'. Since P' is a second-player win for Red, by induction hypothesis, so is Q', and therefore Q was winning for Red. Second, consider the case where it is Blue's turn. We have assumed that Red has a second-player winning strategory for P, and we must show that Red has a second-player winning strategy for Q. Suppose Blue moves in some empty cell of Q, arriving at a new position Q'. If the corresponding cell in P is empty, imagine that Blue moves there. If the corresponding cell in P is not empty, then it must be occupied by a blue stone (since P ≤ Q). In that case, imagine Blue moves anywhere in P. Let P' be the resulting position. In either case, we have P' ≤ Q'. Since P' is a first-player win for Red, by induction hypothesis, so is Q', and therefore, since Blue's move in Q was arbitrary, Q was a second-player win for Red, as required.

The above statement, "If a player can win by passing, then the same player can also win by moving anywhere", now follows. Namely, if it is Red's turn in a position P, then passing would result in the same position P (with Blue to move), and not passing would result in a position Q with one additional red piece (and Blue also to move). Since P ≤ Q, if P is winning then so is Q.

The analogous result of course also holds from Blue's point of view.

In particular, any player who has a winning strategy with passing also has a winning strategy without passing that is just as easy to carry out. Therefore, the outcome of the game does not depend on whether passing is permitted or not.

Many sites seem to take the above fact as a reason why passing 'should not' be allowed. But it is equally valid as a reason for why passing 'should' be allowed.

Implementations of passing

  • No online playing sites currently permit passing. However, this ought to be changed.
  • The current version of the SGF file format for Hex does not provide for a passing move. It does, however, permit consecutive moves by the same player. It would be desirable to add an explicit passing move to the file format, as this would allow passing moves to be recorded and documented. For example, a comment attached to such a move might explain why the player passed (e.g., to give a handicap). This is not quite the same as simply omitting the move; for example, for some handicapping methods, after the first move, the second player can choose to swap (and then the first player will get two consecutive moves) or not to swap (and then the first player gets to move again). If there is no explicit way of passing, the second player must verbally announce "I am not going to swap" before the first player can move again. This is not elegant. A passing move would permit this information to appear in the game tree.