My history of developing artificially intelligent checkers applications began in the Winter Quarter of 1999 at Auburn University. I was taking a Machine Learning course taught by Professor Gerry V. Dozier. We used the textbook “Machine Learning” by Tom M. Mitchell. The first chapter of the now classic textbook is devoted to developing a framework for a checkers (draughts) game. Mitchell used an evaluation function with seven weights and a least mean squares training rule. Over the years I have expanded the number of weights to fourteen rules. I seem to recall my early efforts were in C and later Java. I began programming checkers and chess applications on a Palm Pilot in the Summer Semester of 2002 in the course Handheld Software Development taught by my PhD research advisor Professor Richard O. Chapman. This work was performed in Palm Pilot Operating System C programming language. I created a client server set of programs to operate over TCP/IP networks. I had a modem for my Palm Pilot and learned TCP/IP sockets programming on the Palm Pilot. I still have two volumes addressing Palm Pilot C programming. I created a C# checkers program beginning on October 19, 2017. I started creating a Win32 version of my C# application on October 27, 2022. Unfortunately, I cannot video capture a Win32 game using the Windows button followed by the letter G for Game Boy. The program has five dialogs and apparently Windows-G buttons do not record dialogs. You can find a video of the computer playing against the computer on my Facebook page. I show the main dialog of the Win32 application in this blog.
namespace HamiltonianCircuit
{
class Algorithm
{
// code from C/C++
// http://www.geeksforgeeks.org/backtracking-set-7-hamiltonian-cycle/
// A utility function to check if the vertex v can be added at
// index 'pos' in the Hamiltonian Cycle constructed so far (stored
// in 'path[]')
private bool IsSafe(int v, bool[,] graph, int[] path, int pos)
{
/* Check if this vertex is an adjacent vertex of the previously
added vertex. */
if (!graph[path[pos - 1], v])
return false;
/* Check if the vertex has already been included.
This step can be optimized by creating an array of size V */
for (int i = 0; i < pos; i++)
if (path[i] == v)
return false;
return true;
}
/* A recursive utility function to solve hamiltonian cycle problem */
private bool HamCycleUtil(bool[,] graph, int V, int[] path, int pos)
{
/* base case: If all vertices are included in Hamiltonian Cycle */
if (pos == V)
{
// And if there is an edge from the last included vertex to the
// first vertex
if (graph[path[pos - 1], path[0]])
return true;
else
return false;
}
// Try different vertices as a next candidate in Hamiltonian Cycle.
// We don't try for 0 as we included 0 as starting point in in hamCycle()
for (int v = 1; v < V; v++)
{
// Check if this vertex can be added to Hamiltonian Cycle
if (IsSafe(v, graph, path, pos))
{
path[pos] = v;
// recur to construct rest of the path
if (HamCycleUtil(graph, V, path, pos + 1))
return true;
// If adding vertex v doesn't lead to a solution,
// then remove it
path[pos] = -1;
}
}
// If no vertex can be added to Hamiltonian Cycle constructed so far,
// then return false
return false;
}
// This function solves the Hamiltonian Cycle problem using Backtracking.
// It mainly uses HamCycleUtil() to solve the problem. It returns false
// if there is no Hamiltonian Cycle possible, otherwise return true and
// prints the path. Please note that there may be more than one solutions,
// this function prints one of the feasible solutions.
public bool HamCycle(bool[,] graph, int V, out int[] path)
{
path = new int[V];
for (int i = 0; i < V; i++)
path[i] = -1;
// Let us put vertex 0 as the first vertex in the path. If there is
// a Hamiltonian Cycle, then the path can be started from any point
// of the cycle as the graph is undirected
path[0] = 0;
if (HamCycleUtil(graph, V, path, 1) == false)
return false;
return true;
}
}
}
using System;
using System.Collections.Generic;
namespace HamiltonianCircuit
{
class Edge : IComparable
{
public Vertex Lt { get; set; }
public Vertex Rt { get; set; }
public int Wt { get; set; }
public Edge(Vertex lt, Vertex rt, int wt)
{
Lt = lt;
Rt = rt;
Wt = wt;
}
public int CompareTo(object obj)
{
Edge other = (Edge)obj;
int c1 = Lt.CompareTo(other.Lt);
int c2 = Rt.CompareTo(other.Rt);
if (c1 != 0)
return c1;
if (c2 != 0)
return c2;
return Wt - other.Wt;
}
public bool InList(List<Edge> elist)
{
for (int i = 0; i < elist.Count; i++)
{
Edge e = elist[i];
if (Lt == e.Lt && Rt == e.Rt)
return true;
}
return false;
}
}
}
using System;
using System.Collections.Generic;
namespace HamiltonianCircuit
{
class Vertex : IComparable
{
public int Id { get; set; }
public List<Edge> Edges { get; set; }
public Vertex(int id)
{
Id = id;
}
public Vertex(int id, List<Edge> edges)
{
Id = id;
Edges = edges;
}
public int CompareTo(object obj)
{
Vertex other = (Vertex)obj;
return Id - other.Id;
}
}
}
using System;
using System.Collections.Generic;
using System.Drawing;
using System.Windows.Forms;
namespace HamiltonianCircuit
{
public partial class MainForm : Form
{
private bool generate = true;
private int n, x, y, x1, y1, x2, y2;
private Algorithm algo = new Algorithm();
private Color[] colors =
{
Color.Red,
Color.Blue,
Color.Green,
Color.Orange,
Color.Purple,
Color.Brown,
Color.Turquoise,
Color.Violet,
Color.Tan,
Color.Plum,
Color.Teal,
Color.Yellow
};
private List<Edge> E, F;
private List<Vertex> V;
private Random random = new Random();
private SolidBrush drawBrush;
private Font drawFont;
public MainForm()
{
InitializeComponent();
panel1.Paint += new PaintEventHandler(panel1_Paint);
drawBrush = new SolidBrush(Color.White);
}
void panel1_Paint(object sender, PaintEventArgs e)
{
if (generate)
GenerateDraw(e.Graphics);
else
PathDraw(e.Graphics);
}
private void calculateXY(int id)
{
int Width = panel1.Width;
int Height = panel1.Height;
x = Width / 2 + (int)(Width * Math.Cos(2 * id * Math.PI / n) / 4.0);
y = Height / 2 + (int)(Width * Math.Sin(2 * id * Math.PI / n) / 4.0);
}
private void PathDraw(Graphics g)
{
if (V != null)
{
GenerateDraw(g);
int divisor = 1;
int Width = panel1.Width;
int Height = panel1.Height;
Pen pen = new Pen(Color.Red);
n = V.Count;
for (int i = 0; i < F.Count; i++)
{
Vertex u = F[i].Lt, v = F[i].Rt;
calculateXY(u.Id);
x1 = x + (Width / 2) / n / 2;
y1 = y + (Width / 2) / n / 2;
calculateXY(v.Id);
x2 = x + (Width / 2) / n / 2;
y2 = y + (Width / 2) / n / 2;
g.DrawLine(pen, x1, y1, x2, y2);
}
if (n >= 4 && n <= 5)
divisor = 16;
else if (n >= 6 && n <= 8)
divisor = 24;
else if (n >= 9 && n <= 10)
divisor = 32;
drawFont = new Font("Arial", Width / divisor);
for (int i = 0; i < n; i++)
{
Vertex u = V[i];
SolidBrush brush = new SolidBrush(colors[u.Id]);
calculateXY(u.Id);
g.FillEllipse(brush, x, y, (Width / 2) / n, (Width / 2) / n);
if (n >= 4 && n <= 10)
g.DrawString(i.ToString(), drawFont, drawBrush, x + 4, y + 4);
}
}
}
private void GenerateDraw(Graphics g)
{
if (V != null)
{
int divisor = 1;
int Width = panel1.Width;
int Height = panel1.Height;
Pen pen = new Pen(Color.Black);
n = V.Count;
for (int i = 0; i < n; i++)
{
Vertex u = V[i];
calculateXY(u.Id);
x1 = x + (Width / 2) / n / 2;
y1 = y + (Width / 2) / n / 2;
if (u.Edges != null)
{
for (int j = 0; j < u.Edges.Count; j++)
{
Vertex v = u.Edges[j].Rt;
calculateXY(v.Id);
x2 = x + (Width / 2) / n / 2;
y2 = y + (Width / 2) / n / 2;
g.DrawLine(pen, x1, y1, x2, y2);
}
}
}
if (n >= 4 && n <= 5)
divisor = 16;
else if (n >= 6 && n <= 8)
divisor = 24;
else if (n >= 9 && n <= 10)
divisor = 32;
drawFont = new Font("Arial", Width / divisor);
for (int i = 0; i < n; i++)
{
Vertex u = V[i];
SolidBrush brush = new SolidBrush(colors[u.Id]);
calculateXY(u.Id);
g.FillEllipse(brush, x, y, (Width / 2) / n, (Width / 2) / n);
if (n >= 4 && n <= 10)
g.DrawString(i.ToString(), drawFont, drawBrush, x + 4, y + 4);
}
}
}
private void button1_Click(object sender, EventArgs e)
{
generate = true;
button2.Enabled = true;
int numVers = (int)numericUpDown1.Value;
E = new List<Edge>();
V = new List<Vertex>();
for (int i = 0; i < numVers; i++)
{
Vertex v = new Vertex(i);
v.Edges = new List<Edge>();
V.Add(v);
}
for (int i = 0; i < numVers; i++)
{
int numEdges = random.Next(numVers - 1);
while (numEdges < 2)
numEdges = random.Next(numVers - 1);
Vertex v = V[i];
for (int j = 0; j < numEdges; j++)
{
int id = random.Next(numVers);
int wt = random.Next(100);
Edge edge;
while (wt < 10)
wt = random.Next(100);
while (id == v.Id)
id = random.Next(numVers);
edge = new Edge(v, V[id], wt);
if (!edge.InList(E))
E.Add(edge);
edge = new Edge(V[id], v, wt);
if (!edge.InList(E))
E.Add(edge);
}
}
for (int i = 0; i < E.Count; i++)
{
Vertex u = E[i].Lt, v = E[i].Rt;
u.Edges.Add(new Edge(u, v, E[i].Wt));
v.Edges.Add(new Edge(v, u, E[i].Wt));
}
for (int i = 0; i < V.Count; i++)
{
if (V[i].Edges.Count == 0)
{
MessageBox.Show("Generate a new graph", "Warning Message",
MessageBoxButtons.OK, MessageBoxIcon.Warning);
return;
}
}
textBox1.Text = string.Empty;
textBox1.Text = "Edges(u, v)\r\n";
textBox1.Text += " u v wt\r\n";
for (int i = 0; i < E.Count; i++)
{
textBox1.Text += E[i].Lt.Id.ToString().PadLeft(2) + " ";
textBox1.Text += E[i].Rt.Id.ToString().PadLeft(2) + " ";
textBox1.Text += E[i].Wt.ToString().PadLeft(2) + "\r\n";
}
panel1.Invalidate();
}
private void button2_Click(object sender, EventArgs e)
{
generate = false;
Algorithm algo = new Algorithm();
int n = V.Count;
bool[,] graph = new bool[n, n];
int[] ipath;
for (int i = 0; i < E.Count; i++)
{
Edge edge = E[i];
Vertex u = edge.Lt, v = edge.Rt;
graph[u.Id, v.Id] = true;
}
if (!algo.HamCycle(graph, n, out ipath))
{
MessageBox.Show("No Hamilton circuit exists", "Warning Message",
MessageBoxButtons.OK, MessageBoxIcon.Warning);
return;
}
textBox1.Text += "\r\n";
textBox1.Text += "Edges(u, v)\r\n";
textBox1.Text += " u v wt\r\n";
Vertex[] path = new Vertex[n];
int tcost = 0;
F = new List<Edge>();
for (int i = 0; i < n - 1; i++)
{
Vertex u = V[ipath[i]], v = V[ipath[i + 1]];
Edge edge = new Edge(u, v, 0);
for (int j = 0; j < E.Count; j++)
{
if (edge.Lt == E[j].Lt && edge.Rt == E[j].Rt)
{
edge.Wt = E[j].Wt;
tcost += edge.Wt;
break;
}
}
F.Add(edge);
textBox1.Text += u.Id.ToString().PadLeft(2) + " ";
textBox1.Text += v.Id.ToString().PadLeft(2) + " ";
textBox1.Text += edge.Wt.ToString().PadLeft(2) + "\r\n";
}
Vertex up = V[ipath[n - 1]], vp = V[0];
Edge edgep = new Edge(up, vp, 0);
for (int j = 0; j < E.Count; j++)
{
if (edgep.Lt == E[j].Lt && edgep.Rt == E[j].Rt)
{
edgep.Wt = E[j].Wt;
tcost += edgep.Wt;
break;
}
}
F.Add(edgep);
textBox1.Text += up.Id.ToString().PadLeft(2) + " ";
textBox1.Text += vp.Id.ToString().PadLeft(2) + " ";
textBox1.Text += edgep.Wt.ToString().PadLeft(2) + "\r\n";
textBox1.Text += "Cost = " + tcost + "\r\n";
panel1.Invalidate();
}
}
}
Hamiltonian for a Four Node GraphHamiltonian for a Five Node GraphHamiltonian for a Six Node Graph
There are three classic theoretical tests of Albert Einstein’s Theory of General Relativity: the perihelion precession of Mercury, the other Solar System planets, and the planetoid Pluto, the bending of light by massive bodies, and the gravitational red shift. I recently wrote a C# program for displaying the exaggerated Rosette motion of theoretical planets (Schwarzschild’s solution to Einstein’s general relativity field equation that admit the existence of black holes). I also wrote a C++ program to calculate planetary precession values that agree with experimental results.
Precession.cpp (c) James Pate Williams, Jr. August 2022
This program calculates the planetary precessions of the planets in our solar system. Some of the equations and data are from “General Relativity” by Hans Stephani 1982 page 103 and the following websites. Also, two calculations of the mass of the Sun are exhibited, along with my weight on different planets:
Back in 2015 I created a C# application to solve quadratic, cubic, and quartic equations which are of degrees 2, 3, and 4, respectively. Yesterday I successfully translated the C# to the Python console. I bench-marked my computer programs against the online calculators on the following website:
Numerical Explorations 