CITE THIS NOTEBOOK: The Winning Move for Cutting Corners by Jindřich Michalik. Wolfram Community OCT 27 2022.
ORIGINAL ARTICLE: Michalik, J. The Winning Move for Cutting Corners. Math Intelligencer (2022). https://doi.org/10.1007/s00283-022-10215-9
ORIGINAL ARTICLE: Michalik, J. The Winning Move for Cutting Corners. Math Intelligencer (2022). https://doi.org/10.1007/s00283-022-10215-9
Abstract: This is an electronic supplement to the article The Winning Move For Cutting Corners. Cutting Corners is a game that ends after six moves (three moves by each player), but the number of possible moves rises rapidly with each state of the game. This program is constructed to find a winning strategy for this game using a depth-first search with alpha-beta pruning. Besides the original six-move game by Sid Sackson, other variants in which the game ends after up to ten moves were analyzed and solved, as well as some variants where other rules are slightly modified. All relevant outputs are preserved in the notebook. A significant effort has been made to visualize the game states and the results in a convenient way. The same program can be used to explore variants with more than ten moves, but to do so would be time-consuming.
Introduction
Introduction
The game Cutting Corners first appeared in Sid Sackson’s book A Gamut Of Games in 1969, and was later popularized in Jim Henle’s paper [2]. These are the rules of the original game:
On a piece of paper draw a good-sized square with one player’s color (blue) on two adjacent sides and the second player’s color (red) on the other two. The first player, starting at one edge, draws a blue line, makes one right-angle turn, and ends at another edge. At least one of the edges connected must be red. The second player now draws a red L-shaped line connecting two edges of the square. This line, as well as all subsequent lines, must follow these rules:
1. A new line must touch a side of the opposite color or intersect a line of the opposite color.
2. The number of intersection points of a new line must be equal to the number of lines previously drawn, i.e., the nth line must cross the previous lines n − 1 times (it is not necessary to cross each line exactly once).
After six moves, each region with more blue sides than red sides is colored blue, and each region with more red sides than blue is colored red. The player with more areas of their color wins.
We have found a winning strategy for Cutting Corners and some of its variants using a depth-first search implemented in the Wolfram Language. All functions required for the computation can be found in the part entitled ‘Important data structures and functions’. The following part, ‘Testing, outputs’, uses the previous code to find the winner for Cutting Corners with different numbers of moves.
Section 2, where variants of the games ending after 1,...,10 moves are analyzed, uses the version of the algorithm with alpha-beta pruning for better efficiency (details can be found in the original article). The function explorep[n] runs the computation from the current state, n being the number of lines after which the game ends. The last row of each output contains a blue/red/gray square signalizing whether the current state is winning for Blue/winning for Red/draw. The row above it displays various possible initial moves by the player on the move together with their classification (blue/red/gray square). Some of these states may be substituted by the pair {0,0} meaning that the respective state does not have to be evaluated due to alpha-beta pruning. The previous rows (if any) display the classification of the moves in deeper levels.
Solution to the original six-move game can be found in subsection 2.6 - we consider both opening moves for the first player and run both searches separately. The red square at the end of the output in both cases means that the second player has a winning response for both openings, and therefore a winning strategy for the game. The variable maxlinesp was set to 4 (default value), which reduces the output and shows only the states in which at most four lines are drawn. In subsection 2.5, which deals with the five-move variant of the game, we can see a blue square in the output, which is a sign that the first player has a winning strategy for this variant.
Section 1 is dedicated to variants of the game where the rule 1 described above is omitted. Such a modification allows a new opening move for Blue, which appears to be rather strong. An interesting find is that Blue still cannot force their victory in the 6-move game; however, both players can force a draw in this case. Details about the motive for these computations and further discussion of the results obtained can be found in the original article.
Section 3 contains some additional tests related to the content of the article. For example, subsection 3.1 shows that in the 4-move variant of the game, Red has at least two winning responses to Blue’s opening move. The outputs in the subsection 3.4 prove we cannot say the same about the original 6-move variant; only one winning response to Blue’s ‘better’ opening exists for Red.
On a piece of paper draw a good-sized square with one player’s color (blue) on two adjacent sides and the second player’s color (red) on the other two. The first player, starting at one edge, draws a blue line, makes one right-angle turn, and ends at another edge. At least one of the edges connected must be red. The second player now draws a red L-shaped line connecting two edges of the square. This line, as well as all subsequent lines, must follow these rules:
1. A new line must touch a side of the opposite color or intersect a line of the opposite color.
2. The number of intersection points of a new line must be equal to the number of lines previously drawn, i.e., the nth line must cross the previous lines n − 1 times (it is not necessary to cross each line exactly once).
After six moves, each region with more blue sides than red sides is colored blue, and each region with more red sides than blue is colored red. The player with more areas of their color wins.
We have found a winning strategy for Cutting Corners and some of its variants using a depth-first search implemented in the Wolfram Language. All functions required for the computation can be found in the part entitled ‘Important data structures and functions’. The following part, ‘Testing, outputs’, uses the previous code to find the winner for Cutting Corners with different numbers of moves.
Section 2, where variants of the games ending after 1,...,10 moves are analyzed, uses the version of the algorithm with alpha-beta pruning for better efficiency (details can be found in the original article). The function explorep[n] runs the computation from the current state, n being the number of lines after which the game ends. The last row of each output contains a blue/red/gray square signalizing whether the current state is winning for Blue/winning for Red/draw. The row above it displays various possible initial moves by the player on the move together with their classification (blue/red/gray square). Some of these states may be substituted by the pair {0,0} meaning that the respective state does not have to be evaluated due to alpha-beta pruning. The previous rows (if any) display the classification of the moves in deeper levels.
Solution to the original six-move game can be found in subsection 2.6 - we consider both opening moves for the first player and run both searches separately. The red square at the end of the output in both cases means that the second player has a winning response for both openings, and therefore a winning strategy for the game. The variable maxlinesp was set to 4 (default value), which reduces the output and shows only the states in which at most four lines are drawn. In subsection 2.5, which deals with the five-move variant of the game, we can see a blue square in the output, which is a sign that the first player has a winning strategy for this variant.
Section 1 is dedicated to variants of the game where the rule 1 described above is omitted. Such a modification allows a new opening move for Blue, which appears to be rather strong. An interesting find is that Blue still cannot force their victory in the 6-move game; however, both players can force a draw in this case. Details about the motive for these computations and further discussion of the results obtained can be found in the original article.
Section 3 contains some additional tests related to the content of the article. For example, subsection 3.1 shows that in the 4-move variant of the game, Red has at least two winning responses to Blue’s opening move. The outputs in the subsection 3.4 prove we cannot say the same about the original 6-move variant; only one winning response to Blue’s ‘better’ opening exists for Red.
Important data structures and functions
Testing, outputs
Section 1. Testing an opening move forbidden by rule 1. Testing n-move games for n=1,...,6.
Section 1. Testing an opening move forbidden by rule 1. Testing n-move games for n=1,...,6.
The opening move connecting two blue sides of the square (forbidden by rule 1) - would it be a good move for blue? Only game states up to 4 lines are drawn.
(Debug) In[]:=
(*initialization-thiscellneedstobeevaluatedfirsttobeablerunthecomputationsinthissection*)basicinitialization[6];(*firstmove*)newmove[{1,1},{1,0}];
1.1. 1-move game (obviously, Blue wins)
1.1. 1-move game (obviously, Blue wins)
(Debug) In[]:=
Timing[explorep[1]]
(Debug) Out[]=
{0.,}
1.2. 2-move game (Blue wins)
1.2. 2-move game (Blue wins)
(Debug) In[]:=
Timing[explorep[2]]
,,,,,
,
,
,
,
,
,
(Debug) Out[]=
{0.03125,}
1.3. 3-move game (Blue wins)
1.3. 3-move game (Blue wins)
Timing[explorep[3]]
,,,,,
,
,
,
,
,
,
(Debug) Out[]=
{0.0625,}
1.4. 4-move game (draw)
1.4. 4-move game (draw)
1.5. 5-move game (Blue wins)
1.5. 5-move game (Blue wins)
1.6. 6-move game (draw)
1.6. 6-move game (draw)
Section 2. Using depth-first search with alpha-beta pruning to find winning strategies in n-move games for n=1,...,10.
Section 2. Using depth-first search with alpha-beta pruning to find winning strategies in n-move games for n=1,...,10.
If not stated otherwise, only game states up to 4 lines are drawn.
2.1. 1-move game (obviously, Blue wins)
2.1. 1-move game (obviously, Blue wins)
(Debug) In[]:=
(*initialization*)basicinitialization[2];{drawcurrent[]}Timing[explorep[1]]
(Debug) Out[]=
,{0,0},{0,0},{0,0}
,
(Debug) Out[]=
{0.,}
2.2. 2-move game (Red wins)
2.2. 2-move game (Red wins)
(Debug) In[]:=
(*initialization*)basicinitialization[2];{drawcurrent[]}Timing[explorep[2]]
(Debug) Out[]=
,,
,
,
,
(Debug) Out[]=
{0.046875,}
2.3. 3-move game (Blue wins)
2.3. 3-move game (Blue wins)
2.4. 4-move game (Red wins)
2.4. 4-move game (Red wins)
2.5. 5-move game (Blue wins)
2.5. 5-move game (Blue wins)
2.6. 6-move game (Red wins)
2.6. 6-move game (Red wins)
2.7. 7-move game (Blue wins)
2.7. 7-move game (Blue wins)
2.8. 8-move game (Red wins)
2.8. 8-move game (Red wins)
There are two separate subsubsections: in the first we explore the game where Blue starts with their better move. The other one is dedicated to Blue’s worse opening.
Branch where Blue starts with their better move (connects a red side with a blue side)
Branch where Blue starts with their better move (connects a red side with a blue side)
We guess the winning response for Red.
(*initialization*)basicinitialization[8];(*firstmoves*)newmove[{1,1},{1,1}];newmove[{2,2},{0,1}];Timing[explorep[8]]
,,,,,,,
,
,
,
,
,
,
,
,
(Debug) Out[]=
{529.141,}
Branch where Blue starts with their worse move (connects two red sides)
Branch where Blue starts with their worse move (connects two red sides)
2.9. 9-move game (Blue wins)
2.9. 9-move game (Blue wins)
2.10. 10-move game (Red wins)
2.10. 10-move game (Red wins)
Section 3. Additional tests
Section 3. Additional tests
3.1. 4-move game (Red wins) - using explore to classify all nodes. Only the nodes with at most 2 lines are drawn.
3.1. 4-move game (Red wins) - using explore to classify all nodes. Only the nodes with at most 2 lines are drawn.
3.2. 6-move game, investigation of Jim Henle’s move (draw)
3.2. 6-move game, investigation of Jim Henle’s move (draw)
Here we investigate Jim Henle’s response to Blue’s better opening. It shows that although the move is winning for Red in the 4-move game, in the original 6-move game Blue has two options to force a draw.
3.3. 6-move game, investigation of a good response to Jim Henle’s move (draw)
3.3. 6-move game, investigation of a good response to Jim Henle’s move (draw)
Here we investigate a draw-forcing response by Blue to Jim Henle’s move. We learn that in the subsequent move only two Red’s options are draw-forcing out of the nine.
3.4. 6-move game, classification of all possible responses to Blue’s `better’ opening
3.4. 6-move game, classification of all possible responses to Blue’s `better’ opening
First we get all the possible responses to Blue’s `better’ first move. Then we classify each of them separately using the function explorep (function explore is already too ineffective for the 6-move game).
We learn that there is exactly one winning response from Red.
We learn that there is exactly one winning response from Red.
References
References
[1] ORIGINAL ARTICLE: Michalik, J. The Winning Move for Cutting Corners. Math Intelligencer (2022). https://doi.org/10.1007/s00283-022-10215-9
[2] Henle, J. Mathematical Treasures from Sid Sackson. Math Intelligencer 41, 71–77 (2019). https://doi.org/10.1007/s00283-018-9855-x
[2] Henle, J. Mathematical Treasures from Sid Sackson. Math Intelligencer 41, 71–77 (2019). https://doi.org/10.1007/s00283-018-9855-x