Graph::Maker::NoughtsAndCrosses - create noughts and crosses graphs
use Graph::Maker::NoughtsAndCrosses; $graph = Graph::Maker->new ('noughts_and_crosses', N => 3);
Graph::Maker::NoughtsAndCrosses creates 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).
Graph::Maker::NoughtsAndCrosses
Graph.pm
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.
Option N => $integer is the board size NxN, for N>=1.
N => $integer
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.
Option players => $integer is the number of players in the game.
players => $integer
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.
Options 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.
rotate => $bool
reflect => $bool
$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 graph_maker or Graph->new().
graph_maker
Graph->new()
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 => 1 creates an undirected graph.
undirected => 1
House of Graphs entries for graphs here include
Entries in Sloane's Online Encyclopedia of Integer Sequences related to these graphs include
http://oeis.org/A008907 (etc)
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
Graph::Maker
Copyright 2017 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/.
To install Graph::Maker::Other, copy and paste the appropriate command in to your terminal.
cpanm
cpanm Graph::Maker::Other
CPAN shell
perl -MCPAN -e shell install Graph::Maker::Other
For more information on module installation, please visit the detailed CPAN module installation guide.