CTakefujiLee Class Reference

Neural network tourney generator. More...

#include <TakefujiLee.h>

Inheritance diagram for CTakefujiLee:

Public Member Functions
	CTakefujiLee (int w, int h, int seed)
	Constructor. More...
void	Generate (CBoard &b)
	Generate a tourney. More...
Public Member Functions inherited from CNeuralNet
	CNeuralNet (UINT n, int seed)
	Constructor. More...
void	InsertNeuron (UINT i, UINT j)
	Insert a neuron. More...
Public Member Functions inherited from CGraph
	CGraph (const UINT n)
	Constructor. More...
	~CGraph ()
	Destructor. More...
void	InsertEdge (const UINT i, const UINT j)
	Insert an edge. More...
UINT	BFSF (std::vector< UINT > &result)
	Breadth-first spanning forest. More...
void	PrintGraph ()
	Print the graph to a text file. More...

Private Member Functions
bool	Update ()
	Update all neurons. More...
void	GetAdjacentVertices (std::vector< CVertex * > &v, CVertex *p)
	Get adjacent vertices. More...
bool	IsStable ()
	Stability test. More...
bool	HasDegree2 ()
	Degree test. More...
void	Reset ()
	Reset. More...
void	RandomizeEdgeList ()
	Randomize the edge list. More...
void	GraphToBoard (CBoard &b)
	Convert graph to board. More...

Private Attributes
int	m_nWidth = 0
	Board width.
int	m_nHeight = 0
	Board height.
int	m_nSize = 0
	Board size.

Additional Inherited Members
Protected Attributes inherited from CGraph
std::vector< CEdge * >	m_vEdgeList
	Edge list.
UINT	m_nNumEdges = 0
	Number of edges.
CVertex *	m_pVertexList = nullptr
	Vertex list.
UINT	m_nNumVerts = 0
	Number of vertices.
std::queue< CVertex * >	m_qBFSQueue
	Queue for breadth-first search.
CRandom	m_cRandom
	Random number generator.

Detailed Description

Neural network tourney generator by Takefuji and Lee, see Takefuji and Lee, "Neural network computing for knight's tour problems", Neurocomputing, 4(5):249–254, 1992. Unfortunately the paper doesn't completely specify the method used, so I've taken best guesses in a couple of places. This method is slow at generating closed knight's tours (for more details, see Parberry, "Scalability of a neural network for the knight's tour problem", Neurocomputing, 12:19-34, 1996), but it's much faster at generating tourneys. It's essentially just a Hopfield network with a custom update function, so convergence is guaranteed.

Definition at line 47 of file TakefujiLee.h.

Constructor & Destructor Documentation

CTakefujiLee()

CTakefujiLee::CTakefujiLee	(	int	w,
		int	h,
		int	seed
	)

Initialize the neural network.

Parameters

w	Board width.
h	Board height.
seed	PRNG seed.

Definition at line 41 of file TakefujiLee.cpp.

Member Function Documentation

Generate()

void CTakefujiLee::Generate

(

CBoard &

b

)

Generate a tourney.

Parameters

b	[out] Chessboard.

Definition at line 153 of file TakefujiLee.cpp.

GetAdjacentVertices()

void CTakefujiLee::GetAdjacentVertices ( std::vector< CVertex * > &  v, CVertex *  p  )

private

Get vector of vertices adjacent to a given vertex.

Parameters

p	Pointer to a vertex.
v	[out] Vector of vertices adjacent to the vertex pointed to by p.

Definition at line 237 of file TakefujiLee.cpp.

GraphToBoard()

void CTakefujiLee::GraphToBoard ( CBoard &  b )

private

Assuming the neural network has converged, convert the outputs of its neurons to a move table.

Parameters

b	[out] Chessboard for the results.

Definition at line 175 of file TakefujiLee.cpp.

HasDegree2()

bool CTakefujiLee::HasDegree2 ( )

private

The neural network may converge to a state in which not all vertices have degree 2, which is a requirement for knight's tours and tourneys.

Returns

true If all vertices have degree 2.

Definition at line 123 of file TakefujiLee.cpp.

IsStable()

bool CTakefujiLee::IsStable ( )

private

The network is stable if all neurons are stable.

Returns

true If all neurons are stable.

Definition at line 111 of file TakefujiLee.cpp.

RandomizeEdgeList()

void CTakefujiLee::RandomizeEdgeList ( )

private

Permute the edge list into pseudorandom order for update.

Definition at line 252 of file TakefujiLee.cpp.

Reset()

void CTakefujiLee::Reset ( )

private

Reset all neuron outputs to zero and all neuron states to a random value.

Definition at line 70 of file TakefujiLee.cpp.

Update()

bool CTakefujiLee::Update ( )

private

Update all neurons.

Returns

true If the network has stabilized.

Definition at line 83 of file TakefujiLee.cpp.