I have been doing some task allocation and scheduling work with multi-robot systems during my PhD. I mostly focus on the area of multi-robot 3D printing, but tic-tac-toe is pretty similar!
Here is a video of my robots playing two games. The first move is random, and then each robot plays to the best of its ability using the Minimax algorithm. The process is performed in ROS and the code can be found here: hydra_tic_tac_toe.
Very cool use of an excessive amount of capability for such a mundane task! (no sarcasm there, I actually really love it)
Curious how the first random move is generated. Since I know most languages only have the ability to generate psuedorandom numbers, did you implement something to ensure a true random first move?
Hi Ian, thank you! These libraries I put together for this demo were originally intended for multi-material multi-robot 3D printing. So you’re right – there were probably much easier way to achieve this haha.
As for the random first move, I encode each square of the game board as number 0-8 as follows
| 0 | 1 | 2 |
|---|---|---|
| 3 | 4 | 5 |
| 6 | 7 | 8 |
In Python, I used the random library to generate the first move.
import random
move = random.randint(0, 8)
You are correct in saying this is a psuedorandom number. However, Python uses the current system time to generate the seed of the random module, so it’s seemingly random. For example, I have included the output of five separate runs of the code below:
import random
nums = [random.randint(0, 8) for i in range(20)]
print(nums)
# it1: [2, 8, 1, 2, 8, 0, 6, 3, 4, 2, 8, 8, 3, 0, 3, 6, 4, 8, 2, 6]
# it2: [1, 1, 7, 4, 8, 0, 7, 3, 1, 4, 8, 0, 6, 7, 2, 4, 5, 1, 6, 8]
# it3: [4, 0, 1, 3, 2, 2, 0, 6, 5, 4, 3, 8, 5, 1, 1, 8, 6, 4, 8, 5]
# it4: [5, 4, 4, 8, 1, 8, 3, 5, 0, 6, 5, 5, 8, 3, 4, 2, 8, 2, 2, 1]
# it5: [5, 8, 3, 4, 2, 1, 7, 3, 8, 4, 3, 3, 1, 1, 7, 4, 1, 2, 0, 6]
Thanks for your interest! The tic-tac-toe specific portion of the code is relatively simple and can be found here.
@arbogastaw fantastic video! Really well done!