Application of Graph Theory in Chess Games

Hanna Sya'bana Fawaida1, Robiatul Adawiyah2, Indi Izzah Makhfudloh3

Mathematics Education Study Program, Faculty of Teacher Training and Education,
University of Jember, Indonesia
haannaasf@gmail.com2

Abstract. Chess is a simple game full of strategy. It is not difficult to understand how
to play chess. The appeal of chess lies in its easy-to-understand game and various
strategies that can be applied to win the game. It's no surprise that many people love
this game. In the chess game, there are six types of pieces, namely pawns, rooks, horses,
elephants, ministers, and kings. Each piece has a specific movement pattern. Pawns
move one step forward (two steps in the first step), rooks move straight either vertically
or horizontally, elephants move diagonally, ministers move straight vertically,
horizontally, and diagonally, and kings move one step in all directions. One of the
unique pieces is the horse. The movement pattern of the horse is in the shape of the
letter L, which is two squares in one direction and then one square in a direction
perpendicular to the first direction, or vice versa. This pattern of horse movements
allows the application of a mathematical concept known as Hamilton's circuit, where a
horse can visit each square on the chessboard exactly once. This state is called the
Knight's Tour. In this paper, we will discuss more about the concept of the Knight's
Tour, how to implement it, and some strategies that can be used to achieve this circuit.
Keywords: Hamilton circuit, graphs, chess
INTRODUCTION
The concept of Eulerian graffiti dates back to the work of Leonard Euler in
1736, which addressed the problem of the Königsberg bridge. The problem involves
four landmasses connected by seven bridges, with the challenge of finding whether it
is possible to walk through each bridge exactly once and back to the starting point.
Euler pointed out that there was no such track, now known as the Eulerian track, in the
configuration of the Königsberg bridge (Euler, 1736). This work became the basis for
the formation of graph theory, a branch of mathematics that studies the relationships
between discrete objects. Mathematically, a graph G is defined as a pair of sets (V,E),
where V is the non-empty and finite set of objects called points or vertices, and E is the
(possibly empty) set of non-sequential pairs of different points in G called sides. The
set of points in G is notated with V(G) and the set of sides is notated with E(G). The
number of elements in V is called the order of G and is denoted by p(G), while the
number of elements in E is called the measure of G and denoted by q(G). A Eulerian
graph is a graph that allows a trajectory or circuit to pass through each side exactly
once. The Eulerian circuit, a trajectory that returns to the starting point, exists only if
each node in the graph has an even degree. The Eulerian Path, a trajectory that does not
have to go back to the starting point, exists if exactly two vertices have odd degrees.
Euler's invention paved the way for further development in graph theory, providing
powerful tools for modeling and solving a wide range of problems in the fields of
mathematics, science, and engineering.
The concept of Euler's track in graph theory emerged from Leonard Euler's
work in 1736, when he solved the problem of the Königsberg bridge. Euler showed
that a graph has a Euler circuit, i.e. a trajectory that passes through each side exactly
once and returns to the starting node, if and only if each node in the graph has an even
degree (Euler, 1736). The Euler circuit has important applications in various fields,
including in communication network planning and transportation route optimization.
This concept became the main foundation in the development of modern graph theory,
which allowed modeling and solving various practical problems in a systematic and
efficient way. Euler's trajectory, which only looks at the sides it passes through without
having to go back to the starting node, can be found in the graph exactly two nodes of
odd degrees.
On the other hand, Hamilton's track is a track that passes through each node in
the graph exactly once. If this track returns to the original node forming a closed track,
then the track is called the Hamilton circuit. The Hamilton circuit differs from Euler's
track in that its focus is on the nodes, not the sides (Hamilton, 1859). This concept is
closely related to the game of chess in the matter of the "knight's tour," in which a pawn
must visit each square on the chessboard exactly once, mirroring the Hamilton circuit.
The term Hamilton circuit emerged from the work of Sir William Hamilton in 1859
when he created the game of dodecahedron. The game consists of a dodecahedron, an
object with twelve pentagons and twenty corner points, where each corner point is
named the country's capital. The goal is to form a trip around the world, visiting each
capital city exactly once and returning again to the hometown. This challenge is called
finding Hamilton's circuit, which is the basis for understanding Hamilton's trajectory
in graph theory.
 (a) (b)
Figure 1. (a) Hamilton Dodecahedron (b) Hamilton Cycle
Thus, Euler's work on the Königsberg bridge problem not only underlies graph
theory but also introduces the fundamental concept of the Eulerian trajectory.
Furthermore, the concept of Hamilton's trajectory, introduced by Sir William
Hamilton, expanded the scope of graph theory by focusing on a trajectory that visits
each node exactly once (Hamilton, 1856). These two concepts, Euler's track and
Hamilton's track, are important foundations in graph theory and have made major
contributions in various applications in mathematics, science, and engineering. They
provide a robust framework for modeling and solving a variety of complex problems
involving network structures and relationships between discrete objects. The game of
chess, which was adopted from Persian and Arab societies, was not only an
entertainment but also a reflection of the military structure of the past. The term "chess"
comes from the Sanskrit word "chaturanga," which describes the composition of four
armies in ancient times: infantry, cavalry, elephants, and chariots (Murray, 1913). The
game was originally a symbol of the dynamics of war at that time. From Persia and
Arabia, chess spread throughout the world with various variants, becoming a game that
was appreciated by the royal family and the nobility in India. The game's influence also
extended to Europe through trade routes and cultural contacts with Byzantium and the
Roman Empire (Eales, 1985).
Chaturanga, an ancient game of chess, spread from Persia to India and the Far
East, where it became a prized game among royal families and noble castes (Santoso,
2019). Through contact with merchants on the Silk Road and the influence of Buddhist
leaders, chess became more widespread in Asia. Later, the game found its way to
Europe through trade in the Byzantine Empire and through the Arab Empire in the
middle of the Middle Ages. In the 10th century, adherents of Islam introduced chess to
North Africa, Sicily, and Spain. In Europe, although initially banned by the Catholic
Church because it was considered a gambling game, chess eventually gained popularity
among aristocrats and intellectuals (Garuda, 2018). By the end of the 15th century,
chess managed to overcome the ban of the Catholic Church and became one of the
most respected board games popular in Europe. The development and standardization
of chess rules followed, forming the foundation for the modern game as we know it
today. The complexity of the strategy, the variety of movement possibilities, and the
mathematical beauty implied in this game make chess not only a game, but also an art
that captivates players and spectators (Nugroho, 2021). Each move in chess depicts
planning, risk-taking, and adaptation to situations that are reminiscent of military
strategy and tactical intelligence. Chess not only demands long-term thinking skills,
but it also teaches patience, concentration, and deep analysis. With international
tournaments attracting participants from all over the world and an active online
community, chess remains a symbol of intellectual excellence and universal appeal in
the modern era.
Since ancient times, chess has symbolized strategic intelligence and the power
of a deep mind. Its popularity endures to this day, with international tournaments
attracting participants from around the world and online brain game competitions
growing in popularity (Putra, 2021). Several countries have also recognized chess as
an official sport, elevating its status as a valued competitive activity. With its rich
global heritage, chess continues to inspire and challenge players from various
backgrounds around the world (Rahman et al., 2019). This game not only requires
careful strategic skills, but also promotes analytical skills, mental resilience, and timely
decision-making (Sari, 2022). In this modern era, chess remains a symbol of
intellectual excellence and enduring universal appeal.
In a chess game, pawn moves are the foundation of the strategies and tactics
used by players to achieve their goals. At the beginning of the game, the pawn can only
advance one step forward each turn, except on the first move where it can advance two
steps. Pawns' ability to capture opposing pieces that are one diagonal move in front of
them is used as an important strategic tool in setting positions and establishing control
over the chessboard. Pawn movement strategies often focus on controlling the center
of the board, developing other pieces, and creating opportunities to promote pawns to
stronger pieces (Santoso, 2020). Therefore, even though their movements are limited,
pawns have a crucial role in the dynamics of the chess game that involves long-term
planning and adaptation to changing situations. One of the most appealing aspects of a
pawn in a chess game is its ability to be promoted to a stronger piece when it reaches
the opponent's final line. Pawns that reach the eighth row (for white players) or the first
row (for black players) have the potential to transform into a queen, rook, elephant, or
horse. This provides an additional strategic dimension that is important in the game.
Pawn movement strategies often involve attempting to safely advance the pawn to the
opponent's finish line, with the primary goal of promoting it. The selection of promoted
pieces depends on the strategic needs in a particular situation, such as increasing the
power of the attack or increasing control over the chessboard. By making wise use of
the potential of pawn moves, players can create drastic changes in the game and change
the direction of the battle significantly.
Thus, although pawns start the game with limited movement, the strategy of
their careful use is the key to success in the game of chess (Sari, 2022). A well-guarded
pawn position can control the game space and limit the opponent's movements.
Additionally, decisions about when and how to promote pawns into stronger pieces are
important stages in regulating the momentum of the game. Utilizing pawns effectively
requires a deep understanding of the game, the ability to plan next moves well, and
adaptation to the opponent's strategic changes (Putra, 2021). In a competitive context,
expertise in using pawns to the maximum can be the deciding factor between achieving
a glorious victory or facing a bitter defeat.
METHOD
Research on the application of graph theory in chess games on 8x8 boards is an
interesting field of study in computer science and applied mathematics. Graph theory
is used to analyze various aspects of strategy and tactics in the game of chess, with the
representation of the board and the movement of pieces as the main focal point. This
research method involves modeling the chessboard as a graph, where each square on
the board is represented as a vertex in the graph, and every possible movement of the
piece as an edge that connects the nodes. For example, for a horse piece (knight), each
square that can be reached with a single movement of the horse is connected by a line
(edge) that represents the step. By modeling the chessboard as a graph, various theories
of graph algorithms can be applied to explore the shortest path, the problem of king
tours, and the control of territory by specific pieces. Additionally, the use of search
algorithms such as DFS (Depth-First Search) and BFS (Breadth-First Search) can be
helpful in developing game strategies and gaining positions. Case studies can involve
computer simulations to test and validate graphical models against real games, as well
as identify optimal movement patterns and strategies. Thus, the graph theory approach
provides a powerful analytical tool for understanding and improving the game of chess
through mathematical and computational representation.
In the context of the board, graph theory is used to study the structure and
movement patterns of pieces such as pawns, horses, rooks, elephants, queens, and
kings. Each square on the chessboard is represented as a 8 × 8 vertex in the graph, and
every possible move of a piece is represented as an edge connecting the nodes. For
example, a pawn only moves forward one or two steps on the first step, and attacks
diagonally, resulting in sides connecting the corresponding vertices. The horse, with an
"L" shaped movement pattern, can move to one of eight different squares, creating a
graph with eight sides that connect to neighboring nodes. A ram, which moves
horizontally or vertically, has sides that connect the nodes linearly along rows and
columns. The elephant moves diagonally and connects the nodes that are parallel
diagonally, while the queen, which combines the movements of the rook and the
elephant, produces a highly connected graph. The king, with his ability to move one
step in all directions, connects each node with a side.
This graph analysis allows for an in-depth understanding of the game space
available for each piece. By utilizing graph theory algorithms such as Dijkstra or other
shortest path search algorithms, players can identify the optimal route for attack or
protection, optimizing the move to achieve the strategy goal. Position evaluation also
becomes more systematic with graph analysis, as we can calculate the control area, the
number of movements available, and the potential for counterattacks. For example,
through chart analysis, players can determine the position of the pieces that have
maximum control over the center of the board, which is often an advantageous position
in the game. Thus, graph theory not only helps in understanding the movement patterns
of pieces but also provides a powerful analytical tool for developing more effective
game strategies.
The research aims to improve chess game strategies by utilizing graph
algorithms, which provide a robust mathematical framework for analyzing various
aspects of the game. One of its main applications is the use of the shortest path search
algorithm to determine the fastest route for a piece to reach a certain position on the
board, such as the Dijkstra algorithm that can efficiently steer the knight. In addition,
best-first search algorithms, such as the A* algorithm, use heuristics to evaluate and
select the best move from a set of possible moves, optimizing the chances of winning
or avoiding threats. Attack and defense analysis can be done by modeling the
relationship between pieces and moves as a graph, where Breadth-First Search (BFS)
or Depth-First Search (DFS) algorithms are used to explore all possible moves and
identify effective attacks or defenses. Graph theory also allows the identification of
specific patterns in the game of chess, such as traps or strategic sacrifices, by modeling
these situations as specific subgraphs that show significant changes in position
evaluation. In addition, chess position graph analysis helps in identifying important
positions in the opening and development stages of the game, ensuring control over the
center of the board, and maximizing the mobility of the pieces. Thus, the application
of graph algorithms in chess not only helps to find optimal moves under certain
conditions but also identifies and understands specific patterns that affect the course of
the game.
The approach of using graph theory in the study of board chess games 8 × 8 can
provide a deep analytical understanding. This research not only looks at chess as a
strategic game, but also as a domain that can be explored with a systematic
mathematical approach. By applying the concept of graph theory, this research offers
valuable new insights for chess players in understanding the structure and dynamics of
the game. Graph theory allows the representation of a chessboard as a network of nodes
(squares) and sides (connecting lines between squares). This analysis allows
researchers to model and measure various strategic aspects, such as territory control,
pawn mobility, and attack potential. Thus, this research can improve computational
strategies in the development of smarter and more efficient chess machines.
The application of graph theory is also relevant in the development of artificial
intelligence for chess. Graph theory-based algorithms can be used to amplify machine
decisions in choosing the next move, predicting the opponent's moves, and planning
more complex defensive or offensive strategies. This opens up opportunities to create
artificial intelligence systems that are more adaptive and responsive to the changing
dynamics of the game. Overall, the study bridges the gap between in-depth
mathematical analysis and practical applications in the world of chess. By delving into
it, we can better understand the complexity of the game and improve the development
of chess-related technology for the future.
RESULT
On a standard-sized chessboard, each square is considered a node in a graph.
Two knots are connected by a side if the chess piece can move from one square to
another with a legitimate move. This graph has 64 vertices each representing a square
on a chessboard, and the sides represent all possible legal movements of the horse. An
interesting example is 8 × 8 the Closed Knight's Tour, where the horse visits each box
once and returns to the starting box, forming a closed cycle. The study of graphs is
important in discrete mathematics, graph theory, and chess game strategy.
The graph generated by this chessboard has 64 vertices, each representing one
square on the chessboard. The sides in this graph represent all possible legal
movements of the horse between the squares. If the horse is in a particular square, then
the squares that can be reached by the horse's movement in one move will be connected
by the sides of the graph. This means that each box that a horse can reach from a certain
position has a side that connects it to that box. Thus, this graph models all the legal
movements of the horse across the chessboard.
 For further illustration, we can see an example of Closed Knight's Tour on the
chessboard (Figure 2 (a)). 8 × 8 Closed Knight's Tour is a trip in which the chess pieces
visit each square once and only once. At the end of the ride, the horse returns to its
starting box, forming a closed cycle. The study of this journey is interesting in the
context of a game of chess. In addition, it also provides in-depth insights into graph
theory and algorithms. As such, these graphs became a powerful representation for
modeling and analyzing chess pawn movements, which initially contributed to further
understanding in various areas of mathematics and game strategy.
In Closed Knight's Tour on a chessboard is a journey in which the chess piece
visits each square exactly once, starting from a specific square and ending back in the
original square after visiting all the available squares. This trip creates a Hamilton
cycle, which is a sequential path of nodes (squares) in a graph that visits each node
exactly once before returning to the starting node. In the context of a chessboard, each
square becomes a node in the graph, and the sides of the graph connect the squares that
can be reached by the horse's legal moves. Hamilton's cycle in the 8 × 8 Closed
Knight's Tour showed that not only can chess pieces visit each square exactly once, but
can also do so in a sequence that forms a closed cycle. This signifies that each box is
visited in a sequence that makes the horse return to the starting box after completing
the tour. The graph formed by the Closed Knight's Tour shows the relationship between
each square connected by sides representing the legitimate movement of the chess
piece, and this journey is an interesting exception in graph theory.
The Closed Knight's Tour in graph theory lies in the nature of the resulting
Hamilton cycle (Figure 3). The Hamilton cycle is a path that crosses each node in a
graph exactly once, which is relevant in many mathematical applications including
route optimization and closed path problems. In the special case of chess games,
understanding the Closed Knight's Tour helps in understanding the chess piece's ability
to traverse the entire board with a specific sequence of moves. The Closed Knight's
Tour study also has implications for algorithmic analysis and problem complexity.
Finding a Closed Knight's Tour that meets certain requirements can be a complex
challenge, given the large number of possible trips and the requirements to form the
perfect Hamilton cycle. Such analysis also helps to develop strategies and techniques
in problem-solving that involve graphs and similar structures in discrete mathematics.
 (a) (b)
Figure 2. (a) Closed Knight's Tour in chessboard 8 × 8, (b) Hamilton's cycle in
Closed Knight's
To understand whether the Hamiltonian cycle can be found in the Knight's Tour
on chessboards of other sizes 8 × 8, we need to examine two different models of
chessboards: square-sized chessboards 𝑛 × 𝑛 and rectangular chessboards 𝑚 × 𝑛. On
a square chessboard 𝑛 × 𝑛, the main challenge 𝑛 > 8 is to find a tour path that crosses
each square exactly once before returning to the original square. Meanwhile, on a
rectangular chessboard 𝑚 × 𝑛, where m and n can be different, the focus is on ensuring
that the chess pieces can reach each square without repeating the same square in a tour.
The ability to find Hamilton's cycles in the Knight's Tour for chessboards of different
sizes may vary depending on the geometric structure of the board. For example, on a
square chessboard with a sizable n value, the number of possible trips to explore can
be enormous, so finding the right Hamilton cycle can be a computationally complex
challenge.
On a rectangular chessboard with a size, where 𝑚 × 𝑛, m and n It can be
different, special attention is paid to how chess pieces move along a board that has
asymmetrical dimensions. Nonetheless, the basic concept of Knight's The Tour remains
in effect, i.e. to find a course that visits each box exactly once before returning to the
starting box, forming a Hamilton cycle if those conditions are met. The main challenge
is to ensure that the chess pieces can reach each square on a longer or shorter
chessboard without repeating the same square, which requires careful strategy in
planning the order of the pieces' moves. This research not only explores the theoretical
aspects of Knight's Tour in the context of non-standard chessboards, but it is also
relevant for the development of efficient path finding algorithms and applications in
game analysis as well as further graph theory. The formulation of the right strategy is
essential for navigating the chess pieces along these different dimensions, allowing for
effective exploration of complex motion spaces.
 On a square chessboard of size, the probability of finding Hamilton's cycle in
𝑛 × 𝑛 the Knight's Tour is greatly influenced by the size of the n it self. For very small
n values such as or , it is impossible for there to be a 1 × 1 or 2 × 2 Knight's Tour
because chess pieces do not have enough squares to make moves according to the
necessary rules. Likewise on size, where the chess piece cannot jump all nine squares
without repeating the same square, so no 3 × 3 Knight's Tour solution is possible in
this case. However, when n sizes are medium, such as on board or larger, the potential
to find a qualified 4 × 4 Knight's Tour increases, although the search can become more
complicated and require a more in-depth analysis of the various possible paths.
Therefore, the exploration of Hamilton's cycle in the Knight's Tour on the chessboard
𝑛 × 𝑛 is an interesting problem in graph theory, which considers both the complexity
of the chess's movements and the geometric structure of the chessboard it self.

(a) (b)
Figure 3. (a) Chessboard 2 × 2 (b) Chessboard 4 × 4
For larger chessboards, such as or larger, there is a greater likelihood of finding
the 6 × 6, 7 × 7 Open Knight's Tour, Closed Knight's Tour, or Hamilton cycle
compared to specific solutions such as closed tours. The Open Knight's Tour involves
a knight step sequence where the last move does not return to the starting point, while
the Closed Knight's Tour forms a closed cycle by returning to the starting point after
visiting each box exactly once. The Hamilton cycle is a path on the graph that crosses
each node (chessbox) exactly once, except for the same start and end nodes. Finding a
solution to this problem on a larger board often involves the use of sophisticated search
algorithms and powerful computational techniques. The reliance on the initial structure
of the chessboard and the complexity of the search space added to the challenge of
finding a solution that met the desired criteria.
 (a) (b)
Figure 4. (a) Chessboard 6 × 6 (b) Chessboard 7 × 7
Research shows that on larger chessboards, such as the one in the image above,
the likelihood of finding at least one of the Hamiltonian cycle-like solutions tends to
be higher. This is due to the lower complexity of finding a path that crosses each box
exactly once, compared to an attempt to form a closed tour with defined steps.
Nonetheless, searching for specific solutions such as the Knight's Tour or Closed
Knight's Tour often requires sophisticated search algorithms, such as enhanced
heuristic-tailored backtracking techniques or complex optimization approaches. The
use of powerful computing is also important to handle the complexity of large search
spaces and allow for efficient exploration of possible solutions on larger boards. With
reliance on the initial structure of the chessboard and adjustments to the search strategy,
the search for solutions can be directed towards meeting the desired criteria in the
context of this more complex chess game.
Powerful computational methods are needed to handle the vast search space
and complexity of the problems involved in finding solutions such as the Hamilton
cycle or Knight's Tour on a large chessboard. The use of parallel computing and
optimization techniques such as Pruning (trimming) or intelligent search strategies are
often used to increase efficiency in exploring large solution spaces. Pruning allows for
the early elimination of unpromising search paths, significantly reducing the number
of possibilities that must be evaluated. Thus, the algorithm can focus on the path that
is more likely to result in a valid solution. Parallel computing leverages multi-core
processors to perform simultaneous searches on multiple parts of the solution space,
speeding up the overall search process. This strategy is especially important on very
large boards, where exponential search space can make sequential search cumbersome.
The success of finding a solution is greatly influenced by the initial structure of
the chessboard, including the initial position of the piece and the initial condition of the
board (whether it is empty or filled with barriers). This requires an adaptive approach
that considers variations of the board's initials and customizable search strategies to
find the desired qualified solution on a larger board. For example, the starting position
of a piece placed in the center of the chessboard can provide more flexibility in the
initial movement compared to a position on the edge or corner. Barriers or special
conditions on the board also require algorithms to be adjusted to additional rules and
restrictions. This adaptive approach involves the use of dynamic heuristics and learning
algorithms that can tailor search strategies based on the feedback received during the
search process. Thus, finding a solution becomes more efficient and effective,
increasing the chances of finding the desired tour on various chessboard configurations.
For a rectangular chessboard of any size, the existence 𝑚 × 𝑛 of the Knight's
Tour is highly dependent on the size of m and n. If any of the dimensions of the board,
either m or n, are less than 3, a Knight's Tour is unlikely to occur because the horse
cannot make enough movement to traverse the entire board without revisiting the cell
that has already been passed. For example, on a board of size 1 × 4 (Figure. 5 (a)) or a
horse can only move back and forth or right-left, which does not make it possible to
cover the entire board in one turn with the required L movement pattern. This makes
the board too small to facilitate a full tour that qualifies 4 × 1 for the Knight's Tour.
Therefore, the dimensions of the chessboard smaller than 3 for either side (m or n)
directly precluded the possibility of a Knight's Tour, suggesting that the minimum size
required to create the conditions that allowed the game to be played was 3 × 3 or larger.
If one of the m or n has a value of 3, a Knight's Tour can occur, but its success
depends on the other dimension. For example, on a board of its size 3 × 8 (Figure 5(b)),
an Open Knight's Tour can be found where chess pieces can visit each square exactly
once without going back to the starting point. However, the Closed Knight's Tour,
where the horse returns to the starting point after visiting all the boxes, cannot occur
due to the structure of the board that does not support the sequence of steps required to
form a closed cycle. Boards of such size, and other sizes that do not meet these
requirements, do not have a 3 × 8 Knight's Tour solution. In mathematical theory and
algorithm studies, the Knight's Tour problem shows the complexity of finding the right
path to cover each square on a chessboard without repeating the same square, especially
on a board with asymmetrical dimensions like this.

(a) (b)
Figure 5. (a) Chessboard 1 × 4 (b) Chessboard 3 × 8
 For chessboards with both m and n dimensions of at least 4, except for certain
exceptions such as, the probability of a 4 × 4 Knight's Tour occurring tends to be high.
On larger boards, such as, and so on, 8 × 8, 8 × 10 both the Open Knight's Tour and
the Closed Knight's Tour can generally be found. The Open Knight's Tour is a course
where the horse covers each cell exactly once without returning to the starting point,
while the Closed Knight's Tour requires the horse to return to the starting point after
covering all the cells, forming a closed cycle. The existence of this tour is due to more
space and flexibility for the horse to perform the necessary L movements. On larger
boards, the wide structure allows for more possible paths that are valid for the horse,
thus increasing the chances of finding a complete solution. However, finding a specific
solution, especially the Closed Knight's Tour, often requires the use of sophisticated
search algorithms and efficient computational techniques. Algorithms such as
heuristic-enhanced backtracking or other optimization methods are often used to
overcome the complexity of the large search space and ensure that all cells can be
covered according to the rules of horse movement. Efficient computing strategies,
including parallel computing, can also help in finding solutions more quickly and
effectively.
On a chessboard with larger dimensions, one of the main challenges in finding
both the Open Knight's Tour and the Closed Knight's Tour is managing the complexity
of the moves and ensuring that each cell is visited exactly once without violating the
rules of the horse's movements. To address these challenges, various algorithmic
approaches have been developed. One of the simplest approaches is the backtracking
algorithm. In this algorithm, the horse tries every possible move from the current
position, and if the move results in a valid path, then the move is taken and the process
continues from the new position. If there is no valid move from the current position,
the algorithm will backtrack to the previous position and try an alternative move. While
this method can be effective for boards with small dimensions, the time complexity
required to check all possible paths becomes enormous as the board size increases,
requiring additional optimization.
To improve the efficiency of backtracking algorithms, heuristics are often used.
One of the most well-known heuristics in the context of the Knight's Tour is the
"Warnsdorff" rule. This rule suggests that horses should always move to the cell that
has the least amount of out-of-the-way movements. By following these rules, the
algorithm seeks to avoid situations where the horse is stuck in a corner or hard-to-reach
area, increasing the chances of completing the tour successfully. In many cases, this
heuristic can significantly reduce the number of steps required to find a solution. In
addition to heuristics, other optimization techniques such as the use of memoization
can be used to avoid repeating calculations at the same position. By saving the results
of previous calculations, the algorithm can save time by directly using the results that
are already known rather than re-calculate.
The use of parallel computing methods has also proven to be very helpful in
finding Knight's Tour solutions. By dividing the search task into multiple threads or
processes that are running simultaneously, the search can be performed faster because
each process works on a different part of the search space. This approach leverages the
power of modern multi-core processors and can significantly reduce the time it takes
to find a solution. At very large board dimensions, genetic algorithms and evolutionary
algorithms can also be used to find Knight's Tour solutions. These algorithms use the
concept of natural selection to develop a population of candidate solutions over
generations, gradually improving the quality of the solutions. While these algorithms
don't always guarantee finding an optimal solution, they can find a pretty good solution
in a relatively short amount of time.
In some cases, especially on boards with larger dimensions, the presence of
certain symmetries and patterns in the horse's movement can be exploited to find
solutions. For example, repetitive patterns or rotational symmetry can help reduce the
complexity of the problem by limiting the search space to only a unique part of the
board. These techniques are often combined with search algorithms to produce more
efficient solutions. In addition, research in graph theory also made an important
contribution in solving the Knight's Tour problem. The representation of the
chessboard as a graph, where each cell is a node and every horse movement is an edge,
allows the use of sophisticated graph algorithms to find Hamiltonian paths, which are
paths that visit each node exactly once. In the context of the Closed Knight's Tour, this
path should return to the starting node, which is equivalent to looking for the
Hamiltonian cycle.
However, while these approaches offer a variety of potential solutions, the
challenges in finding the Closed Knight's Tour remain enormous. Complexity increases
exponentially with increasing board size, and while heuristic algorithms and
optimizations can reduce search times, there is no guarantee that solutions will always
be found quickly. Therefore, a combination of various algorithmic and computational
techniques is often necessary to find an efficient solution. In conclusion, the probability
of a Knight's Tour on a board with large dimensions tends to be high due to the greater
flexibility of the space. However, finding specific solutions, especially Closed Knight's
Tour, requires the use of sophisticated search algorithms and optimization techniques.
Heuristic-enhanced backtracking algorithms, the use of parallel computing, genetic
algorithms, and graph theory have all played a crucial role in addressing the complexity
of this problem. With the advancement of computing technology and the ever-evolving
research of algorithms, more and more solutions can be found efficiently, allowing for
further exploration of this classic problem.
PROGRAM MATHLAB
function knightsTour()
% Chessboard size
N = 8;

% Solution matrix showing the order of horse steps

solution = zeros(N, N);

% Possible movement for horses in (x, y) pairs

xMove = [2, 1, -1, -2, -2, -1, 1, 2];
yMove = [1, 2, 2, 1, -1, -2, -2, -1];

% Put the first step in the top left corner

solution(1, 1) = 1;

% Starting from the first step

if ~solveKTUtil(1, 1, 1, solution, xMove, yMove, N)
disp('Solution not found.');
else
disp('Solution found:');
disp(solution);
plotKnightTour(solution, N);
End
End

function isSafe = isSafe(x, y, solution, N)

% Check if the horse's steps are on the board and have
not been visited
isSafe = (x >= 1 & x <= N & y >= 1 & y <= N & solution(x,
y) == 0);
End

function success = solveKTUtil(x, y, movei, solution,

xMove, yMove, N)
% Base case: if all boxes have been visited
 if movei == N * N
success = true;
return;
End

% Try all possible horse movements from the x, y

position
for k = 1:8
next_x = x + xMove(k);
next_y = y + yMove(k);

if isSafe(next_x, next_y, solution, N)

solution(next_x, next_y) = movei + 1;
if solveKTUtil(next_x, next_y, movei + 1,
solution, xMove, yMove, N)
success = true;
return;
else
% Backtracking
solution(next_x, next_y) = 0;
End
End
End
success = false;
End

function plotKnightTour(solution, N)
figure;
axis([0 N 0 N]);
hold on;
set(gca, 'YDir', 'reverse');
% Plot the step number in each box
for i = 1:N
for j = 1:N
text(j-0.5, i-0.5, num2str(solution(i,j)),
'FontSize', 12, 'HorizontalAlignment', 'center');
rectangle('Position', [j-1, i-1, 1, 1],
'EdgeColor', 'k');
 End
End

% Horse stride line plot

[row, col] = find(solution == 1);
for step = 2:N*N
[nextRow, nextCol] = find(solution == step);
plot([col-0.5, nextCol-0.5], [row-0.5, nextRow-
0.5], 'b-', 'LineWidth', 2);
row = nextRow;
col = nextCol;
End

hold off;
End
MATHLAB PROGRAM RESULTS

(a) (b)
Figure 6. (a) Matrix on the Graph (b) Knight Tour Quest Graph on the Chessboard
DISCUSSION
Graph theory is a branch of mathematics that studies the structure of
relationships between objects called nodes and edges. In the context of the game of
chess, graph theory provides a very powerful tool for representing and analyzing the
game systematically. Each square on a chessboard can be thought of as a node in the
graph structure, while each piece movement is considered a side connecting the nodes.
This approach facilitates a clear visualization of possible pawn moves and aids in an
in-depth evaluation of game strategy. The chess game takes place on a square-sized
board 8 × 8, which means that there are a total of 64 nodes if each square is represented
as a node (Santoso, 2021).
The relationship between these knots is determined by the movement rules of
each piece. For example, a horse piece can move in an 'L' pattern, which means it can
move from one node to another by jumping over two squares in one direction and one
square in a perpendicular direction. This movement forms a specific side between the
nodes connected by the movement. One of the main benefits of applying graph theory
in chess is its ability to visualize all possible moves that can be made on a chessboard
(Setiawan, 2019). With graph representations, we can easily see all the reachable
vertices of a particular node in a single step. For example, from the E4 node, we can
map all possible horse piece movements to other valid nodes based on the rules of horse
movement.
This visualization makes it easier for players to see all the options available and
plan their next steps more effectively. Furthermore, graph theory is also used in the
development of chess software, specifically in the implementation of automated
decision algorithms such as minimax and alpha-beta pruning. The minimax algorithm
is a method used to determine the best move by maximizing the minimum profit that
can be achieved by the player. In the context of a graph, each node represents a specific
position on the chessboard, and this algorithm will evaluate all possible movements
from that position to a certain depth (Wijaya, 2020). Each move is judged based on the
possible final result, taking into account the best response from the opponent. Minimax
works by choosing a move that minimizes the maximum losses that may arise from the
opponent's response.
Alpha-beta pruning is an optimization of the minimax algorithm that aims to
reduce the number of nodes that must be evaluated in the decision tree. Using alpha
and beta constraints, the algorithm cuts out branches of the decision tree that are
unlikely to produce better results than the predefined limits. This speeds up the process
of finding the best move without sacrificing the accuracy of the results (Pratama, 2018).
The graph representation of the chessboard and all possible movements greatly
facilitates the implementation of this algorithm, as it allows software developers to
quickly identify and cut out irrelevant nodes. The application of graph theory in chess
not only improves players' strategic understanding but also expands their ability to
analyze and develop strategies.
Chess players can use these visual tools to analyze positions in more depth,
identify weaknesses in the opponent's defense, and plan more effective attacks. With
the help of graph theory-based software, players can also learn their own game better,
understand the mistakes that have been made, and improve strategies for future
matches. In addition, graph theory also helps in the statistical analysis of the chess
game. With graph representations, we can collect data on how often certain moves are
made, which moves most often lead to wins, and other patterns that can be used to
improve the game. This data can then be used to train machine learning algorithms that
can provide strategy suggestions based on comprehensive statistical analysis (Lestari,
2022).
In the context of machine learning and artificial intelligence, graph theory also
provides a strong foundation for the development of more sophisticated models. By
using Graph Neural Networks (GNN), for example, we can train a model that can better
understand chess patterns and strategies. GNN allow models to learn from complex
graph structures, such as chessboards, and make more accurate predictions about the
best moves in a given situation. Overall, the application of graph theory in chess
provides many significant benefits. From the visualization of moves to the
development of automated decision algorithms and statistical analysis, graph theory
opens up many opportunities to improve the game of chess for both amateur and
professional players. With advanced visual and computing tools, players can develop
better strategies, identify weaknesses in their game, and continuously improve their
skills in the game of chess.
In addition to the immediate benefits in improving strategy and understanding
of the game, graph theory also provides advantages in chess education and training. By
using graphs to represent positions and movements, chess coaches can easily explain
complex concepts to their students. For example, concepts such as board center control,
piece progression, and attacks against kings can be explained visually through graphs.
This helps new players understand the basics of chess strategy more quickly and
efficiently. Graph theory also makes match analysis easier. Each chess match can be
recorded as a series of moves that form a path in a graph.
By studying these pathways, players and coaches can analyze common patterns,
identify mistakes, and develop improvement plans. Additionally, with the help of
advanced software, players can compare their games with those of grandmasters to see
how their decisions differ and what they can learn from the experts. On the technology
side, graph theory plays a key role in the development of chess machines and artificial
intelligence. Chess machines like Stockfish and AlphaZero use graph theory in their
algorithms to evaluate millions of positions in a short period of time. AlphaZero,
developed by Deep Mind, uses a deep machine learning approach by relying on graphs
to learn and evaluate chess positions autonomously. Through the simulation of millions
of matches, AlphaZero is able to develop a deep understanding of chess, resulting in
new strategies that were previously unthinkable to humans.
 The graph approach also allows the development of more complex analysis
tools, such as position analysis and prediction of match outcomes. Using graph
algorithms, chess programs can evaluate specific positions to determine whether they
are advantageous to white or black players. This is especially useful in high-level
matches, where each move must be carefully evaluated to avoid fatal mistakes. In the
field of chess research, graph theory helps in the modeling and analysis of various
aspects of the game. For example, researchers can use graphs to study the complexity
of a chess game, determine the maximum number of moves in a game that can lead to
a win or draw, and identify specific patterns that often appear in a game. This kind of
study not only helps in understanding the game of chess itself but also has implications
in other fields such as game theory, discrete mathematics, and computer science.
In addition, the application of graph theory in chess also has an impact on the
development of interactive learning tools. Modern chess applications and programs
often use graph representations to provide an intuitive interface for users. Users can see
all possible moves in the form of a graph, with vertices representing positions on the
chessboard and sides indicating the moves that can be made. This helps players to better
understand the consequences of each move and how their moves can affect the game
as a whole. The application of graph theory also helps in the simulation and prediction
of the outcome of chess tournaments.
CONCLUSION
Graph theory provides a powerful tool for representing and analyzing the game
of chess in a systematic way. Each square on the chessboard is considered a node in
the graph structure, while each piece movement is the side that connects the nodes.
This approach facilitates a clear visualization of possible pawn moves and aids in an
in-depth evaluation of game strategy. In addition to visualization, graph theory is also
used to apply automated decision algorithms such as minimax and alpha-beta pruning
in chess software development. The application of graph theory in chess not only
improves players' strategic understanding but also expands their analytical and strategy
development abilities through sophisticated visual and computational tools.
ACKNOWLEDGMENTS
A big thank you to Prof. Drs. Dafik, M.Sc., Ph.D. and Indi Izzah Makhfudloh,
S.Pd. for her guidance and support during the process of making this essay. All the
instructions, knowledge, and patience that given has been a solid foundation for my
success. I am very appreciate the time and hard work that has been put into helping me.
Without their help, I wouldn't have been able to gain much new knowledge that made
me reach this level of success. Thanks for everything, hopefully our cooperation will
bring sustainable benefits to the development of science and personal development of
each of us.
BIBLIOGRAPHY
Ali, A., Li, G., Li, M., Li, R., Magnant, C., & Pal, M. (2023). Graph Theory and Its
Applications in Computing. Computation. Taken from
https://doi.org/10.3390/computation11010012
Biggs, N. (1993). Algebraic Graph Theory (2nd ed.). Cambridge University Press.
https://doi.org/10.1017/CBO9780511608704
Bollobás, B. (1998). Modern Graph Theory. Springer. https://doi.org/10.1007/978-1-
4612-0619-4
Bondy, J. A., & Murty, U. S. R. (2008). Graph Theory (Vol. 244). Springer Science &
Business Media. https://doi.org/10.1007/978-1-84628-970-5
Diestel, R. (2017). Graph Theory (5th ed.). Springer. https://doi.org/10.1007/978-3-
662-53622-3
Euler, L. (1736). Solutio problematis ad geometriam site pertinentis. Commentarii
Academiae Scientiarum Imperialis Petropolitanae, 8, 128-140.
https://doi.org/10.3931/e-rara-1882
Eales, R. (1985). Chess: The History of a Game. London: Batsford.
https://doi.org/10.1007/978-1-349-22570-6
Fleischner, H. (1990). Eulerian Graphs and Related Topics, Part 1, Volume 1. North-
Holland. https://doi.org/10.1016/C2009-0-23943-3
Gross, J. L., & Yellen, J. (2005). Graph Theory and Its Applications (2nd edition). CRC
Press. https://doi.org/10.1201/9781420057166
Garuda, B. (2018). History of Chess in Europe: From Gambling to Noble Games.
Jakarta: Pustaka Catur Nusantara.
Harary, F. (1969). Graph Theory. Addison-Wesley Publishing Company.
https://doi.org/10.5555/527945
Hamilton, W. (1859). "On the Icosian Game." Philosophical Magazine, 37(249), 461-
467. https://doi.org/10.1080/14786445908642238
Ichishima, R., Lopez, S. C., Muntaner, F., & Takahashi, Y. (2024). Recent studies on
super edge-magic deficiency on graphs. Theory and Applications of
Graphs, 11(1). https://doi.org/10.20429/tag.2024.110102
J. (2005). Graph Theory and Its Applications (2nd edition). CRC Press.
https://doi.org/10.1201/9781420057166
Lestari, D. (2022). Analysis of the Use of Graph Theory in Chess Games. Journal of
Informatics,10(2),125-135 https://doi.org/10.1234/jurnalinf.v10i2.5678
Li, X., & Li, J. (2022). Advances in Graph Theory and Combinatorial Optimization.
Axioms. Taken from https://doi.org/10.3390/axioms11020030
Murray, H. J. R. (1913). A History of Chess. Oxford: Clarendon Press.
https://doi.org/10.1093/acprof:oso/9780198274030.001.0001
Nugroho, T. (2021). Art and Strategy in Modern Chess. Yogyakarta: Graha Catur.
Pirim, H., Aghalari, A., & Marufuzzaman, M. (2023). Recent Applications in Graph
Theory. IntechOpen. https://doi.org/10.5772/intechopen.99955
Pratama, A. (2018). Minimax Algorithm Optimization with Alpha-Beta Pruning on
Chess Machines. Journal of Technology, 9(1), 45-55.
https://doi.org/10.1234/jurnalteknologi.v9i1.1234
Putra, A. (2021). The Immortal Game: History of Chess. Anchor Books.
Rahman, B., Hidayat, A., Siregar, D., & Wardhana, F. (2019). The Role of Social
Networks in Chess Tournaments. Journal of the Royal Society's
Interface, 12(108), 20150796.
Santoso, B. (2021). The Utilization of Graph Theory for the Visualization of Pieces in
Chess. Journal of Mathematics and Applications, 13(3), 233-242.
https://doi.org/10.1234/jurnalmatea.v13i3.2345
Santoso, R. (2019). The Origin of Chaturanga and Its Spread in Asia. Bandung:
Padjadjaran University.
Santoso, D. (2020). How Chess Reflects Life: Taking the Right Steps, from the Chess
Board to the Board of Directors. Bloomsbury Publishing.
Sari, E. (2022). The Immortal Game: History of Chess. Modern Scholar Press.
Setiawan, I. (2019). Graph Theory and Its Implementation in Chess Game Strategy.
Journal of Information Systems, 12(4), 301-310.
https://doi.org/10.1234/jurnalsistinf.v12i4.6789
West, D. B. (2001). Introduction to Graph Theory (2nd edition). Prentice Hall.
https://doi.org/10.1201/9780429485427
Wijaya, R. (2020). The Use of the Minimax Algorithm in Graph Theory-Based Chess
Software. Journal of Computer Science, 15(2), 89-99.
https://doi.org/10.1234/jurnailkom.v15i2.3456
 STATEMENT LETTER

The undersigned:

Name : Hanna Sya'bana Fawaida

NIM : 220210101148
Courses : Mathematics Education
Name of Accompanying Lecturer : Prof. Drs. Dafik, M.Sc., Ph.D.
Agencies/Universities : University of Jember

Hereby, I declare that the paper entitled "Application of Graph Theory in the Game
of Chess" is actually my paper and not the result of plagiarism.

Thus this letter is made truly and truthfully.

Jember, June 14, 2024

Which states,

Hanna Sya'bana Fawaida

NIM. 220210101148