DOTS AND BOXES- Classic Strategy Board Game
Introduction
Among pencil-paper games, “dots and boxes” is a very famous game. It is popular among children and adults as it can be easily played and have very simple rules. In a game of Dots-And-Boxes, the players draw a rectangular grid of dots and take turns drawing lines between pairs of horizontally- or vertically-adjacent dots, forming boxes. The size of the game is defined by the number of boxes. To capture a box player has to complete the fourth line; when all the lines have filled, the player who captured the most boxes is the winner. If both players play optimally, there is no outcome of the game. For dots and boxes, the most used technique is Alpha – Beta “minimax”. The old techniques cannot be used due to copyright reasons and previous state of the art. There is a use of some generic search techniques in Dots-And-Boxes. These techniques are commonly used in the heuristic search, but there are non-obvious adaptations of them to the domain that greatly improve their effectiveness. Any person can play a classic line puzzle and dot game to recall their childhood. There are several other names for this game as Paddocks, Dots and Dashes, Smart Dots, Square, etc.
HOW TO PLAY Dots &Boxes:
The goal of the Dots and Boxes game is to join the dots and make squares. For every round, a player has to connect two dots to draw a line between two adjacent dots, which may be either horizontal or vertical. The player gains a point if he makes a square with all sides closed with lines. This is a two-player game. The player with more number of squares will be the winner.
Dots & Boxes game is available in the following modes:-
- Single player: where you can play with computer AI
- Multiplayer: where you can play with your friends
“Following the optimal strategy is key to win any strategy game.” There are some rules you can follow while playing the game
Minimax
The minimax algorithm is an algorithm that evaluates the value of a position in a combinatorial game by looking down the game tree based on the principle that the enemy aims to minimize the player’s score while the player aims to maximize it. In theory, this algorithm should be able to play any game on m \times nm×n grid optimally. However, the algorithm is only implemented when the number of moves is less. This is because as the number of boxes on the grid increase, the possibilities increase exponentially.
Single double-box move
Another way of putting this is to say that if (and only if) (m+1)(n+1)(m+1)(n+1) is odd, the first player wants to arrange things so that there is an even number of double-box moves in the game. For a chain of length 1 or 2, neither player needs to allow a double-box move to be made. However, in each chain of length three or more, either player may take all boxes but two, providing the opponent with a single double-box move. For a loop of four or more boxes, either player may take all but four boxes, providing the opponent with two double-box moves. Thus, in a well-played game, the number of double-box moves is equal to the number of long chains, plus twice the number of loops, minus one because the player to move in the last long chain will take all of the boxes. So if (m+1)(n+1)(m+1)(n+1) is odd, the first player wants an odd number of long chains in the game. Moreover, (m+1)(n+1)(m+1)(n+1) is odd if and only if both m and n are even.
USED TECHNIQUES
Chains
In most games, states exist whose optimal moves are easy to determine. For trivial examples, consider games like TicTac-Toe or Connect Four, where one wins by having a certain number of pieces in a line. If the current player can make a move that completes a winning line, or prevents the opponent from completing a winning line on their next move,
then the optimal move must be to fill in that position.
Transposition Tables
Transposition tables are a well-known technique for reducing duplicate work in depth-first searches. A transposition table is a cache of explored states that associates with each stored entry its backed-up minimax value. If a newly generated state has been previously explored, its stored value can be retrieved, avoiding the duplicate work of determining its value a subsequent time.
Symmetries
There are several trivial symmetries in Dots-And-Boxesthat reduce the problem space. The mirror image of a state is also a legal game whose optimal strategy mirrors that of the current state. All Dots-And-Boxes instances have horizontal and vertical symmetry, and square boards have diagonal symmetry. We store canonical representations of states in the
transposition table so that all states that are identical under symmetries map to the same entry. These symmetries reduce the size of the search space by a factor of 4 on most boards and a factor of 8 on square boards.
Move Ordering
The order that Alpha-Beta explores children of a node strongly influences the amount of work required to determine its value. An effective move-ordering heuristic sorts move in decreasing order of value for the current player, under the intuition that making stronger moves first will tighten search bounds for later moves, creating more search cutoffs.
Mirroring
Since the mirror trick makes things even, it favors Player 1. Since player 2 is second to play, Player 1 must find a way to become ‘Player 2’ in terms of being able to copy moves. Although many people try to create a mirror top-bottom and left-right, most do it wrong by only mirroring either the top-bottom or the left-right. A true mirror reflects top-bottom and left-right at the same time.
3×3 Boards
3×3’s are so small that they tend to change some rules. While mirrors will tend to favor Player 1, if Player 1 only plays either vertical or horizontal lines, Player 2 can win a mirror game with Player 1 by creating three chains that are all vertical or horizontal. If Player 1 notices that he is being copied, he can create a loop around the center box, which will favor Player 1 instead of Player 2.
All boards
As many may have found out before, the way to change the turn in favor of Player 1 for mirror tricks is to give away the center box so that Player 2 is effectively playing ahead of Player 1, allowing him to copy. While most might think this automatically spells doom for Player 2 if they let it happen, it does not.
Don’t let Player 1 give you center box. If they seem to be forcing you to take it, make sure there are un-copied lines somewhere else one the board. Also, try to circle the center block, incorporating it into a waving chain that counts as “1” so that if they mirror you the rest of the way, the count will remain odd.
Verifying Correctness
The margin of victory is given optimal play and the optimal opening move. For each problem considered in Experiments, we generated these values using Wilson’s solver, as well as solver with each search feature described. The result was the same in all cases, giving us a high degree of confidence that the proofs generated by our solver are correct.
Mistakes
Everyone makes mistakes; sometimes, you can use this to your advantage. If you are a follower, you can sometimes take the opportunity to give a chain away early.
If your opponent forgets to sacrifice the two boxes in the end, the count will drop by one, which can sometimes result in victory if your sacrifice did not give away too many boxes. To avoid excessive sacrifices, pick the smallest chains to sacrifice
FEATURES OF Dots and Boxes Game
ü Dots and Boxes is a simple classic game
ü Suitable for all ages
ü Different board sizes
ü Two player board also available
ü Popular as paddock
ü 100% free
ü Can be played offline
ü A casual game
Discussion
There are several reasons why Dots-And-Boxes is a game worth studying. First and foremost, it is an extremely popular and widely known game and is familiar to a wide variety of people from around the world. Also, it is an exceedingly simple game; the difficulty in solving the game comes primarily from the size of the problem space and not from any inherent complexity in the rules themselves. Finally, the game is an unusual example of an impartial game that cannot be addressed by the Sprague-Grundy theorem; most of the games addressed in the literature are partial. Despite this, there has been remarkably little coverage of Dots-And-Boxes in the literature; what material exists does not discuss applying computational search. As a consequence, the value of each of the existing techniques is unknown. Our paper is the first to synthesize these techniques and present them in the context of heuristic search, providing a thorough discussion of their utility.
The combination of these techniques, along with some non-obvious modifications, generic techniques, have allowed us to solve the previously unsolved 4×5 game. More importantly, however, our solver establishes a formal benchmark against which future research on this problem can be judged.
Compatibility
For androids 9.0 iPad, iPod, iPhone, and smartphones
https://play.google.com/store/apps/details?id=com.aljaro.dotsandboxes
Developers
Mohammad Al-Jaro
Contact: [email protected]
