- HOUSE OF GRAPHS
- SEE ALSO
Graph::Maker::NoughtsAndCrosses - create noughts and crosses graphs
use Graph::Maker::NoughtsAndCrosses; $graph = Graph::Maker->new ('noughts_and_crosses', N => 3);
Graph.pm graphs of noughts and crosses games. Each vertex is the state of the board, starting from an empty board. Each edge is a move by a player, adding a nought or cross and going to a new board state. The game stops when one player has a winning line or the board is full (which might be win or draw).
The format of vertex names is unspecified. Currently they're a string of board contents, 0 for empty square, 1 or 2 for player's piece. But don't rely on that.
N => $integer is the board size NxN, for N>=1.
The number of vertices quickly becomes very large, so 3x3 is about the biggest which it's practical to calculate. Some of the options below reduce combinations enough to allow 4x4.
N=1 is a board of 1 cell which is trivially won by the first player, so a 2 vertex graph. N=2 is also always won by the first player, but with more structure.
players => $integer is the number of players in the game.
0 players means no moves so a single vertex for the empty board.
1 player means placing pieces until reaching a filled line. On a 2x2 board any 2 places make a line so the states are just 4 positions with up to 2 filled. This is an induced subgraph of the tesseract (Graph::Maker::Hypercube with N=4). A corner of the tesseract is the empty board then filling is vertices distance <= 2 from there. Other size boards are also induced sub-graphs of an N^2 dimensional hypercube, but the rule for which vertices to include is not as simple.
1 player in general has depth from the empty board of at most N^2-N pieces placed, since any more placed is less than N holes so not enough to prevent a line in all rows. On a 2x2 that's still not enough as 2 pieces can be a column or diagonal. On a 3x3 the only 6 piece board not yet winning is, up to rotation or reflection,
. X X X . X 1-player diagonal of unfilled squares X X .
From this there are 3 ways to reach a 7-piece win, or 2 ways up to rotation and reflection. These are the only 7-piece configurations which arise in play.
X X X . X X X . X X X X 1-player 7-piece wins X X . X X .
If players > N+1 then there are not enough cells for anyone to win. If players > N^2 then there are more players than cells and only the first N^2 have a turn. In that case the boards at depth d become all arrangements of d different pieces in N^2 cells.
rotate => $bool and
reflect => $bool treat board states as equivalent when they are the same when rotated 90, 180 or 270 degrees, or mirror image reflection, respectively. Rotate and reflect together are all combinations of 0, 90, 180, 270 rotation and reflect or not.
$graph = Graph::Maker->new('noughts_and_crosses', key => value, ...)
The key/value parameters are
N => integer, default 3, board size NxN players => integer >= 1 rotate => boolean, default false, rotated boards equivalent reflect => boolean, default false, mirror image equivalent graph_maker => subr(key=>value) constructor, default Graph->new
Other parameters are passed to the constructor, either
If the graph is directed (the default) then edges are directed from old board state to new board state. The one predecessorless vertex is the empty board. Option
undirected => 1creates an undirected graph.
House of Graphs entries for graphs here include
- N=2, https://hog.grinvin.org/ViewGraphInfo.action?id=27017
- N=2, rotate, https://hog.grinvin.org/ViewGraphInfo.action?id=27020
- N=2, rotate, reflect https://hog.grinvin.org/ViewGraphInfo.action?id=945
- N=2, 1 player, https://hog.grinvin.org/ViewGraphInfo.action?id=27032
- N=2, 1 player, reflect, https://hog.grinvin.org/ViewGraphInfo.action?id=856
- N=2, 1 player, rotate, https://hog.grinvin.org/ViewGraphInfo.action?id=500 (claw)>
- N=2, 3 players, rotate, https://hog.grinvin.org/ViewGraphInfo.action?id=27025
- N=2, 3 players, rotate, reflect, https://hog.grinvin.org/ViewGraphInfo.action?id=27048
- N=2, 4 players, rotate, https://hog.grinvin.org/ViewGraphInfo.action?id=27034
- N=2, 4 players, rotate, reflect, https://hog.grinvin.org/ViewGraphInfo.action?id=27050
- N=3, 1 player, rotate, reflect https://hog.grinvin.org/ViewGraphInfo.action?id=27015
Entries in Sloane's Online Encyclopedia of Integer Sequences related to these graphs include
3x3 with 2 players (the default) A061526 num NxN complete games being num paths from root to some successorless vertex A061527 num NxN games won by player 1 A061528 num NxN games won by player 2 A061529 num NxN games drawn A061221 num winning game states, after n moves being num paths from root to successorless vertex, excluding draws at depth 9 3x3 with 2 players, up to rotate and reflect A008907 num board states after n moves A048245 num winning board states after n moves A085698 num vertices for N^2 players A087074 num vertices at depths for N^2 players
Copyright 2017, 2018, 2019 Kevin Ryde
This file is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 3, or (at your option) any later version.
This file is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
You should have received a copy of the GNU General Public License along with This file. If not, see http://www.gnu.org/licenses/.