A Tic Tac Toe machine to defeat all humans (Team Project)

This week’s objectives

Machine

Application

Application a device designed to help the user to perform specific tasks

The application for our machine is to play tic-tac-toe against a human adversary, using an aggressive play-to-win AI.

Automation

Automation describes a wide range of technologies that reduce human intervention in processes.

Our machine provides full end-to-end automation for the entire game of tic-tac-toe.

See below for a detailed list of features.

Actuation

Actuation. An actuator is a component of a machine that is responsible for moving and controlling a mechanism or system, for example by opening a valve. In simple terms, it is a “mover”.

From the point of view of machine design, Actuators are the parts of the machine that operate in its environments ( to affect it/change it, in some way), while the sensors are the parts that receive information from its environment.

In terms of actuation, our machine has a moving pen, whose tip can be arbitrarily positioned in any position in the operating space/volume.

For all intents and purposes, however the pen will only occupy 2 planes in space:

private static final int SERVO_HOVER=550;
private static final int SERVO_PAPER=400;

public void hover(){
  arduinoClient.sendCommand("M3 S"+SERVO_HOVER);
}

public void paper(){
  arduinoClient.sendCommand("M3 S"+SERVO_PAPER);
}

Mechanism

Mechanism (engineering), rigid bodies connected by joints in order to accomplish a desired force and/or motion transmission

The machine that we have built has various mechanisms to operate and perform action in all 3 spacial dimensions:

The combination of these mechanisms allow the machine to have an operating space/volume of approx:

412 mm x 420 mm x 18 mm = 3,114,720 mm3 = 3114 cm3

Here’s a short excerpt of the code used to control the machine over the operating space.

private static final int FEED_RATE_FAST = 150;

/**     0   1   2
 * 0  ( 1 | 2 | 3 )
 * 1  ( 4 | 5 | 6 )
 * 2  ( 7 | 8 | 9 )
 */
public void goToPosition(int row, int col){
  switch(""+row+col){
    case"00"->fastTo(1.5,7.5); // (Position for Cell 1)
    case"01"->fastTo(4.5,7.5); // (Position for Cell 2)
    case"02"->fastTo(7.5,7.5); // (Position for Cell 3)
    case"10"->fastTo(1.5,4.5); // (Position for Cell 4)
    case"11"->fastTo(4.5,4.5); // (Position for Cell 5)
    case"12"->fastTo(7.5,4.5); // (Position for Cell 6)
    case"20"->fastTo(1.5,1.5); // (Position for Cell 7)
    case"21"->fastTo(4.5,1.5); // (Position for Cell 8)
    case"22"->fastTo(7.5,1.5); // (Position for Cell 9)
  }
}

private void fastTo(double x,double y){
  arduinoClient.sendCommand("G00 X" + x + "Y" + y + " F" + FEED_RATE_FAST);
}

My Individual Contribution

Research

  1. Learned about GCode syntax, commands, flavours and features
    1. How to use Relative and Absolute coordinates for our benefit
    2. How to avoid mistakes when doing circles
  2. Research on tic-tac-toe algorithms and 3rd party A.I. engines
  3. Learned about Svelte for creating frontends using typescript
  4. Investigating grblHAL-sim to see if it could be useful as a GRBL Simulator, so I would not be blocked/waiting while the team was designing/building the machine/calibrating the drivers/shield.

Implementation

  1. Implementing the GCODE needed to draw on the board via Arduino/GRBL through a serial interface (tested in NCViewer)
  2. Creating the control application and logic:
    1. Backend that receives user input and coordinates with 3rd party A.I. engine
      1. Java 17 OpenJDK
      2. Spring Framework 5.3.18
      3. Spring Boot 2.6.6
      4. jSerialComm Library, used to abstract raw serial communications
      5. JavaArduinoLibrary used to abstract basic arduino commands.
    2. Frontend used for the user to enter moves and view game state
      1. First iteration using Bootstrap 5.13 and JQuery 3.6.0
      2. Second iteration using Svelte, Typescript language, and RollupJs as a bundler
    3. Minimal changes in 3rd party AI algorithm to make it easy-to-interface-with, since it was not initially designed to be used as a standalone library.
  3. Collaboration with the rest of the team on making sure all the pieces work well together.
    1. For example, our machine does not require precise mm/inch calibration. It assumes that the board is 9x9 units in size, and it draws in that imaginary grid.
    2. It was critical to communicate these core assumptions with the rest of the team so that the driver/arduino/shield calibration was done as expected by the controlling logic.

Machine Features

The diagram above highlights in lime green the components that I have implemented and in green-gray the component that I have adapted from existing code.

Exploration and Useful Resources

These are some interesting resources that were helpful during my research

Controlling Arduino from a computer/website

  1. Ethernet Shield
    1. Discarded because there are no Ethernet shields available in the BCN lab
    2. More importantly, definitely discarded because if we wanted to have all the goodies (a fully featured machine, and aggressive AI algorithm, an easy to debug backend, an easy to compose frontend, etc…) having a laptop as a backend would make our work much easier. Most of the shield examples end up with pretty ugly/basic/1990s web interfaces (no shade!)
  2. GCode4J
    1. Very useful to get a general idea, but far from easy to be integrated.
  3. RSTEP Project
    1. I checked this out as an alternative to GCode4J. Discarded: Too low level. This project is a GCode interpreter. We already have this. We’re looking for a GCode Sender.
  4. UGS Universal Gcode Sender 1.A fully featured java application. Overkill and probably hard to integrate with custom control logic. We’re not interested in building a plugin for UGS.
  5. Chrome GCode Sender for ChromeOS
    1. Interesting project for ChromeOS. Discarded because we don’t have plans to run our machine from ChromeOS. Hard to integrate with custom control logic
  6. Java Arduino Library
    1. Tiny and to the point! a winner. We ended up using this in our project! ✨
  7. simpleJavaGrblStreamer
    1. I came across when I was having issues sending GCode via Serial interface.
    2. While we did not use any code from this resource, seeing such a simple that (presumably) works was the final straw that proved that the issues we were having were caused by something in our code, not in the intermediary libraries, etc…
    3. In hindsight, line 151 should have given me the CLICK! needed to fix, but in the end, it was Josep (one of our local instructions) who gave us the hint we needed!

TicTacToe Algorithms

These are some algorithms I checked out while looking for something we could readily use in our backend laptop.

  1. MixiMax Algorithm
    1. Very promising! We would have implemented this, if we hadn’t found an already implemented algorithm.
  2. Simple Tic Tac Toe
    1. Very simple algorithm that has no intelligence and plays an “O” on the first available spot on the board.
    2. Lacks intelligence and aggressiveness
  3. Detect a winner
    1. Does not place any tokens, just checks if the board is in a “win” position for either player. Not what we were looking for
  4. Another example using MinMax
    1. Another simple example on Minimax
  5. Another example using Alpha Beta Pruning
    1. Another nice example on Alpha-Beta Pruning.
  6. Unbeatable using Alpha Beta Pruning with performance Improvements, by LazoCoder
    1. The algorithm we ended up using. It uses Alpha-Beta Pruning, but it includes the “fold depth” as a factor to score movements, giving better scores that end up in a winning position in fewer movements.
    2. Without this optimization, the basic Alpha-Beta Pruning algorithm would still reach a victory, but it would win after needlessly torturing the human adversary. We have no time for nonsense.
    3. I selected this specific implementation because I liked the consistency that this algorithm displayed, and the total absence of confusing moves it makes. It searches for the fastest win and goes for it.

Problems encountered

GRBL and Relative coordinates

During our initial iterations, we were having issues when we tried to get the steppers to draw figures on our board, but not when we were trying to move around the board (hovering).

Our initial hypothesis was that maybe GRBL did not support relative coordinates.

  1. After a bit of research we came across specific documentation (Pg. 3) for GRBL 1.1.2 that clearly indicates that it supports G91 for relative positioning.
  2. Something else I learned is that “Relative positioning” is called “Incremental” in some environments. This proved useful when googling around, as we found many more hits and useful results.
  3. A third thing I learned is that there is specific syntax that allows relative coordinates to be used while GRBL is in absolute mode. This syntax uses UVW Commands instead of XYZ, although it seems to be unsupported by GRBL 1.1.

This avenue of research did not help us resolve the issue we were having, and at the end, the problem was fixed by re-tightening all the belts used by the steppers, and doing a soft reset of the shield.

We accidentally burned one arduino board

So, full disclosure… We don’t actually know what happened, but we believe it burned/died because it is no longer working in any capacity.

Context: While we were using an Arduino UNO Board, it suddenly stopped working. In front of all of us. And no one was moving around/touching it.

That’s not the worst part. The worst part is that we have not been able to find out the root cause of this unexpected event.

Everything worked as normal when we place a new arduino board and reloaded the GRBL config settings, so it’s clearly something wrong with the Arduino UNO board, and trying to flash it with the GRBL firmware/library was not possible once it died.

We need to do a bit more research to figure out what happened! A 20$ damage is a huge piece of the budget. We better find answers.

Desperation to fix a GRBL problem almost ended with my laptop infected with suspicious virus

Pro Tip: when developing for GRBL/Arduino, on a Linux machine, with custom software, always click on any “Download Windows Registry Fix.exe” links that may appear in front of you!

😒 Don’t trust all links!

Inconsistent command execution & GRBL randomly dropping instructions without errors

Alright! So this was one of the most confusing problems, and one of the most celebrated once it got fixed.

Imagine that Arduino is receiving commands correctly when you send them via the Arduino IDE / Serial Monitor:

But that the exact same commands Sometimes fail when you send them via your custom program:

This problem has all ingredients for the perfect frustration 🥴🤯 storm 🌩:

  1. The command (any command!) works perfectly on a known platform (Arduino IDE): so it’s not hardware issue
  2. We tested different cables: so it’s not a comms issue
  3. It sometimes works correctly from our program: so it’s not an obvious error in our code/library
  4. All the examples we are finding online have code that looks extremely similar to our custom code (open port, handshake, etc…): so we have not missed anything obvious
  5. What is it?!
    1. The answer came to us after a quick question to one of our local instructors (Thanks Josep! 💝):
      1. It turns out, we had forgotten to send out the “new line” character at the end of our command.
      2. The new line command is normally generated when we press Return or Enter key on our keyboards.
      3. The same key we press on the Arduino Serial Monitor to “send” the command.

The fix was easy and swift: We just had to add a \n new line character at the end of each command we wanted to send arduino.serialWrite(command); for a arduino.serialWrite(command + "\n");

It was so obvious, and yet so invisible, until it got fixed.

✨ What a difference 1 byte makes✨, when implementing low-level protocols!

Life lesson:

Video - Real Life demo of a full game

This is one of the sample games we played before we had a fully functioning pen holder.

Spoiler alert: 😎 I lose because I was more focused on recording the video than on playing! 🤦

Video - Sample demo with pen

One of the first iteration with a pen attached

This showed us that we had to find a most consistent way to hold the pen:

Video - Blooper: A Fail Game

And the mandatory “Fail” Video that shows our glorious successes during the build process.

That’s how you know this machine was built by us! We have the evidence to prove it 😉

Summary

Anyway, these are my lessons learned and my contributions to the team project. Jump on to the group documentation page for a more detailed explanation of all the work we did, as a team, to get this project off the ground and into glorious success.

Source code and Licensing

Assets