Set Game Solver on Microcontroller
#augmented reality #combinatorics #discrete mathematics
There is one very witty board game. It is called Set. It is a game of attention. The advantage of this game is that it is for an unlimited number of players. This is what it looks like.
Set has another variation: the game cats.
There are signs not of figure, color, quantity and filling, but of headdress, glasses, camera.
What is the problem?
It happens that you are going to play Set and no one sees the set. But it actually exists.
The solution to the problem would be a hardware and software complex for automatic set detection!
I decided to take on its design.
What's the plan?
The idea is very simple. The idea is this…
1–Assign a natural number to each card from the Set game. Literally one byte per card.
2–Convert a natural number into DataMatrix code.
3–Print the code on a sticker.
4–Stickers with DataMatrix codes are glued to the back of each card in the game Set. This is 81 stickers.
5–Connect the QR code reader to the microcontroller via UART.
6–Write a microcontroller firmware that finds all Set(s) by enumeration and prints the solution to UART.
As you can see, the plan is simple, and therefore good. Because in complex captivity, something can go wrong.
Hardware
Hardware comes first, software comes second. So you need to prepare the hardware.
First, the Set game instance needs to be upgraded. 81 needs to be generated DataMatrix code to install it on each card in the deck. For this, I wrote this software pipeline.
Each card is uniquely encoded with 8 bits.
No. | bit numbers | number of bits | parameter | options |
1 | 1:0 | 2 | quantity | 1 2 3 |
2 | 3:2 | 2 | filling | empty, solid, striped |
3 | 5:4 | 2 | color | purple, red, green |
4 | 7:0 | 2 | figure | wave, rhombus, oval |
Here the 8-bit code of the card is converted into a binary representation of the DataMatrix code (100 bits). To generate the code, I downloaded the C sources from GitHub.
Then the Graphviz code generator code is launched and a black and white tile is composed in the Graphviz language. At the finish, the text *.gv file is converted to *.svg by the dot.exe utility. And so on for 81 cases. We get 81 *.svg files. Throw *.svg onto a USB flash drive and take them to the nearest printing house and ask to print them on adhesive paper. Each code is 4 cm on the side.
The most tedious part of this project was to stick the DataMatrix codes on each card. This had to be done very carefully without mistakes. Otherwise, everything would go to hell. I was sticking these stickers for about 3 hours.
In general, I personally do not understand why the manufacturers of the game set do not print a QR code on the back of the card, which would provide information about this card. This would be logical and would help with the automatic sorting of these cards in production. The same applies to all other board games, where there are any cards.
As a QR code reader, I purchased a separate GM67 module.
To switch the module to UART mode, you need to scan this code.
Now all that remains is to connect the units according to this diagram.
I wrote a program for calculating the location of the set for the AT-Start-F437 training electronic board with an ARM-Cortex-M4 AT32F437ZM microcontroller on board.
Software part
As a programming language in which to solve the problem, I chose the C programming language, the GCC compiler, and the Make build system. All of this can be downloaded from the Internet absolutely free of charge.
I first debugged the game's business logic on DeskTop PC as a Windows console application. Then I rebuilt the same code for the ARM Cortex-M4 microprocessor.
Here is the code for the main software component – the Set game solver
#include "set_game.h"
#include <string.h>
#include <stdlib.h>
#include "debug_info.h"
#include "log.h"
#include "code_generator.h"
#ifdef HAS_GM67
#include "gm67_drv.h"
#endif
COMPONENT_GET_NODE(SetGame, set_game)
COMPONENT_GET_CONFIG(SetGame, set_game)
#define SET_GAME_IS_XXXX_SET(CardA,CardB,CardC,ATTRIBUTE) \
bool set_game_is_##ATTRIBUTE##_set(SetCard_t* CardA, \
SetCard_t* CardB, \
SetCard_t* CardC) { \
bool res = false; \
if(CardA->Info.ATTRIBUTE == CardB->Info.ATTRIBUTE){ \
if(CardB->Info.ATTRIBUTE == CardC->Info.ATTRIBUTE){ \
if(CardA->Info.ATTRIBUTE == CardC->Info.ATTRIBUTE){ \
res = true; \
} \
} \
} \
if(CardA->Info.ATTRIBUTE != CardB->Info.ATTRIBUTE){ \
if(CardB->Info.ATTRIBUTE != CardC->Info.ATTRIBUTE){ \
if(CardA->Info.ATTRIBUTE != CardC->Info.ATTRIBUTE){ \
res = true; \
} \
} \
} \
return res; \
}
bool set_game_proc_one(uint8_t num) {
bool res = false;
LOG_PARN(SET_GAME, "Proc:%u", num);
SetGameHandle_t* Node = SetGameGetNode( num);
if (Node) {
#ifdef HAS_GM67
Gm67Handle_t* Gm67Node=Gm67GetNode(Node->scanner_num);
if(Gm67Node){
if(Gm67Node->unptoc_frame){
LOG_DEBUG(SET_GAME, "%s", SetNodeToStr(Node));
SetCardInfo_t Card;
Card.byte = Gm67Node->DataFixed[0];
res = set_game_add_card(num, Card);
Gm67Node->unptoc_frame = false ;
res = set_game_seek_set(num);
}
}
#endif
}
return res;
}
bool set_game_init_custom(void) {
bool res = true ;
srand(time(0));
log_level_get_set(SET_GAME, LOG_LEVEL_INFO );
return res;
}
bool set_game_is_uniq_ll( SetGameHandle_t* Node,SetCardInfo_t Card){
bool res = true;
uint8_t i = 0 ;
for(i=0;i<Node->card_cnt;i++){
if(Card.byte == Node->Cards[i].Info.byte){
res = false ;
}
}
return res;
}
bool set_game_is_set_index(const SetInstance_t* const SetNode, uint8_t index){
bool res = false ;
if(index==SetNode->CardA.index){
res = true;
}
if(index==SetNode->CardB.index){
res = true;
}
if(index==SetNode->CardC.index){
res = true;
}
return res;
}
bool set_game_add_card(uint8_t num, SetCardInfo_t Card){
bool res = false;
SetGameHandle_t* Node = SetGameGetNode( num);
if(Node) {
LOG_DEBUG(SET_GAME,"New:%s",SetCardInfoToStr( Card) );
if( Node->card_cnt < SET_GAME_TOTAL_ON_TABLE){
//is uniq?
res = set_game_is_uniq_ll(Node,Card);
if(res) {
LOG_INFO(SET_GAME,"+%s",SetCardInfoToStr( Card) );
Node->Cards[Node->card_cnt].Info=Card;
Node->Cards[Node->card_cnt].index = Node->card_cnt;
Node->card_cnt++;
res = true;
} else {
LOG_ERROR(SET_GAME,"Duplicate:%s",SetCardInfoToStr( Card) );
}
} else {
LOG_ERROR(SET_GAME,"TooManyCardsOnnTable:%s",SetCardInfoToStr( Card) );
}
SetGameDiag(Node);
}
return res;
}
SET_GAME_IS_XXXX_SET(CardA,CardB,CardC,color)
SET_GAME_IS_XXXX_SET(CardA,CardB,CardC,filling)
SET_GAME_IS_XXXX_SET(CardA,CardB,CardC,quantity)
SET_GAME_IS_XXXX_SET(CardA,CardB,CardC,shape)
bool set_game_is_set(SetCard_t* CardA, SetCard_t* CardB, SetCard_t* CardC) {
bool res = false;
res = set_game_is_color_set(CardA, CardB,CardC) ;
if(res) {
res = false;
res = set_game_is_filling_set(CardA, CardB, CardC) ;
if(res){
res = false;
res = set_game_is_quantity_set(CardA, CardB, CardC) ;
if(res){
res = false;
res = set_game_is_shape_set(CardA, CardB, CardC) ;
}
}
}
return res;
}
int uint32_compare(const void * x1, const void * x2) {
return ( *(uint32_t*)x1 - *(uint32_t*)x2 ); // если результат вычитания равен 0, то числа равны, < 0: x1 < x2; > 0: x1 > x2
}
bool set_game_is_set_uniq(SetGameHandle_t* Node , SetInstance_t* Instance){
bool res = true ;
uint32_t i =0;
for (i=0;i<Node->set_cnt;i++){
if(Instance->qword==Node->SetArray[i].qword){
res = false ;
break;
}
}
return res;
}
bool set_game_seek_set(uint8_t num){
bool res = false ;
SetGameHandle_t* Node = SetGameGetNode(num);
uint32_t cur_arr[3] ={0};
uint32_t i =0;
uint32_t j =0;
uint32_t k =0;
for(i=0;i<Node->card_cnt;i++){
for(j=0;j<Node->card_cnt;j++){
for(k=0;k<Node->card_cnt;k++){
if(i!=j){
if(i!=k){
if(j!=k){
res = set_game_is_set(
&Node->Cards[i],
&Node->Cards[j],
&Node->Cards[k]);
if(res){
cur_arr[0] =i;
cur_arr[1] =j;
cur_arr[2] =k;
size_t item_size = sizeof(uint32_t);
qsort((void *)cur_arr, (size_t)3, item_size, uint32_compare);
SetInstance_t Instance;
Instance.qword = 0;
Instance.CardA=Node->Cards[cur_arr[0]];//2
Instance.CardB=Node->Cards[cur_arr[1]];//2
Instance.CardC=Node->Cards[cur_arr[2]];//2
res = set_game_is_set_uniq(Node,&Instance);
if (res) {
Node->SetArray[Node->set_cnt]=Instance;
Node->set_cnt++;
res = true;
LOG_INFO(SET_GAME,"%u,SpotNewSet:%u,%u,%u!",Node->set_cnt,cur_arr[0],cur_arr[1],cur_arr[2]);
}
}
}
}
}
}
}
}
if(Node->set_cnt){
LOG_INFO(SET_GAME,"SetCnt:%u",Node->set_cnt);
}else {
LOG_ERROR(SET_GAME,"NoSets");
}
return res;
}
bool set_game_init_one(uint8_t num) {
LOG_WARNING(SET_GAME, "Init:%u", num);
bool res = false;
const SetGameConfig_t* Config = SetGameGetConfig(num);
if(Config) {
LOG_WARNING(SET_GAME, "%s", SetGameConfigToStr(Config));
SetGameHandle_t* Node = SetGameGetNode(num);
if(Node) {
LOG_INFO(SET_GAME, "%u", num);
Node->num = Config->num;
Node->scanner_num = Config->scanner_num;
Node->valid = true;
Node->set_cnt = 0;
Node->card_cnt = 0;
memset(Node->StepLog,0,sizeof(Node->StepLog));
SetGameDiag(Node) ;
res = true;
}
}
return res;
}
COMPONENT_INIT_PATTERT(SET_GAME, SET_GAME, set_game)
COMPONENT_PROC_PATTERT(SET_GAME, SET_GAME, set_game)
Debugging
When the cards are scanned, they end up in an array of structures. Fortunately, the firmware has UART-CLI for monitoring global variables. Here is the result of the cards read by the scanner.
After adding a new card to the array, the set search procedure is launched. The solution is issued as a list of arrays with indexes of cards that form the Set. Visual patterns of the places where each set is laid are also printed, so that it is easy to find and pick it up on the table. These 5 set(s) were found by the microcontroller itself!
Thus, the firmware, like a litmus test in real time, provides target indication of the physical location of the set(s).
What can be improved?
1–Write an Android application that finds a set from a tabletop photo. However, this is very labor-intensive, since it is necessary to do image recognition (probably in OpenCV).
2–Print set cards on RFID cards or make perforations so that a regular photo resistor can read the card code.
4–You can display solutions on OLED display with I2C interface.
Results
This hardware and software complex (HSC) can be used to conduct tournaments in the game Set (if such tournaments are held).
By the way, similar actions can be done for another card game – Spot.
QR codes are good because they are a standardized way to transfer binary data from the screen to the camera. You can even update the firmware with a sequence of QR codes.
How can all this be applied in real life?
It would be great to somehow put the same ID codes on the socks. Then with a simple reader it would always be easy to find pairs after washing.
Dictionary
Acronym | translation |
PACK | hardware and software system |
UART | Universal asynchronous receiver-transmitter |
