Autonomous Path Planning
Strydr Silverberg ·
Using artificial intelligence to compute good chess moves has been around [since the 1940s](https://en.wikipedia.org/wiki/History_of_chess_engines). However, nobody to my knowledge has attempted to tackle the problem of playing chess moves autonomously without a mechanical arm or cameras. Here is a bit about my approach and how works at a systems level.
The problem with playing chess moves autonomously
The root of the problem is this: not all chess pieces can move in the same way; and there are two particularly difficult cases we must account for in order to have a fully autonomous chess system.
- Knights can jump neighboring pieces to accomplish it's move. This is unlike other pieces, which must have a direct line-of-sight to the piece they are targeting.
- Castling requires two pieces to swap places.
Solution
Essentially, the solution is to generate a move plan for any move presented to the gantry by the engine. The move plan encompasses a series of moves that must be done to accomplish the engine move. We begin by generating all possible paths for a primary piece, select the best path, find blocking pieces on the path, build a set of excluded squares (primary piece path squares), plan relocation for each blocking piece (which recursively makes a move plan for blocking blockers), build restoration paths (reverse order of relocations), generate the G-code, and execute the plan.
`
A_STAR(start, goal):
Create an empty priority queue OPEN Create an empty set CLOSED
Add start node to OPEN
Set: g(start) = 0 h(start) = heuristic distance from start to goal f(start) = g(start) + h(start)
while OPEN is not empty:
current = node in OPEN with lowest f value
if current == goal: return reconstruct_path(current)
Remove current from OPEN Add current to CLOSED
for each neighbor of current:
if neighbor is in CLOSED: continue
tentative_g = g(current) + cost(current, neighbor)
if neighbor is not in OPEN: add neighbor to OPEN
else if tentative_g >= g(neighbor): continue
// This is a better path parent(neighbor) = current
g(neighbor) = tentative_g
h(neighbor) = heuristic(neighbor, goal)
f(neighbor) = g(neighbor) + h(neighbor)
return no path found
`
What the values mean A* uses three scores:
1. g(n) — Cost so far
The actual distance traveled from the start node to the current node.
g(Current) = total movement cost so far
2. h(n) — Estimated cost remaining
This is the heuristic function. It guesses how far the node is from the goal.
h(Current) = estimated remaining distance
3. f(n) — Total estimated cost
f(n) = g(n) + h(n)
A* always expands the node with the lowest f because it represents the best balance between how far we've already traveled and how close we appear to be to the goal.
About the Data Structure
The priority queue is what makes A* efficient. Normal queues are FIFO or first in, first out. A regular queue does not care which path looks promising. A priority queue, on the other hand, has a notion of how items should be placed in the queue based on priority. Lowest f-score comes out first which allows the algorithm to ask "which node currently has the best estimated path to the goal" and quickly retrieve that node.