/ 
Graph-Maker-Other-19
River stage zero No dependents
/ Graph::Maker::NoughtsAndCrosses

NAME

Graph::Maker::NoughtsAndCrosses - create noughts and crosses graphs

SYNOPSIS

use Graph::Maker::NoughtsAndCrosses;
$graph = Graph::Maker->new ('noughts_and_crosses', N => 3);

DESCRIPTION

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).

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.

Board Size

Option 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

Option 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.

Rotation and Reflection

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.

FUNCTIONS

$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().

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.

HOUSE OF GRAPHS

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

OEIS

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

SEE ALSO

Graph::Maker

HOME PAGE

http://user42.tuxfamily.org/graph-maker-other/index.html

LICENSE

Copyright 2017, 2018, 2019, 2020, 2021 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/.