Grająca Szachownica

[okjak]

Witam 🙂

Elektroniką zajmuję się od dwóch miesięcy, kiedy to po raz pierwszy zaświeciłem diodą z kursu: FORBOT - podstawy elektroniki - zestaw elementów + kurs ON-LINE. Kurs tak mi się spodobał że ukończyłem go w dwa dni i kupiłem 4 kolejne: 

• FORBOT - podstawy elektroniki 2 - zestaw elementów + kurs ON-LINE, 
• FORBOT - technika cyfrowa - zestaw elementów + kurs ON-LINE, 
• FORBOT - zestaw do nauki lutowania elementów THT oraz
• FORBOT - zestaw do kursu podstaw Arduino + gadżety i Box (wersja PLUS).

Jak tylko je połknąłem pojawił mi się w głowie pomysł na pierwszy projekt którym chciałbym się  Wami podzielić. Projekt został oparty o Arduino Pro Mini i jest to Szachownica która gra za mną w szachy 🙂

Bardzo zależało mi żeby była to tradycyjna duża drewniana szachownica, którą będę się mógł cieszyć przez lata. Całość prezentuje się tak:

Najpierw należało zacząć od wykrywania pozycji bierek. Do tego zdecydowałem się (być może nieco pochopnie) na użycie małego ładnego zgrabnego komponentu o nazwie sg-2bc. SG-2BC to nic innego jak dioda IR i fototranzystor w jednej małej (4mm średnicy) ceramicznej obudowie. Ma jednak jedną wadę w zastosowaniu do którego go potrzebowałem - jego fototranzystor jest bardzo wrażliwy na światło słoneczne. Musiałem więc odróżnić jakoś światło słoneczne od światła odbitego diody IR. Zaprojektowałem w tym celu prosty obwód oparty o ne555, który generuje sygnał PWM o częstotliwości około 32kHz i wypełnieniu 33%. Układ ten daje sygnał na diodę IR oraz sprawdza za pomocą 3 komparatorów (dwa lm393 - 2 komparatory na układ) i filtra RC czy odebrał sygnał o odpowiedniej charakterystyce po stronie fototranzystora (czyli na polu stoi bierka). Na wyjściu wystawia stan wysoki jeśli to mu się udało. W ten sposób powstał mój pierwszy w życiu projekt płytki drukowanej 🙂 Oczywiście zdarzyło mi się wlutować jeden z komparatorów odwrotnie a potem to poprawiać. I tu uwaga do Forbota: w kursie lutowania brakuje informacji i praktyki w wylutowywaniu układów scalonych - na prawdę by się przydało! 🙂 Jakoś to jednak poszło i efekt był taki:

 

Z racji uśredniania na filtrze RC który jest częścią obwodu czas odpowiedzi na sygnał to 3ms. Oczywiście nie chciałem takiego obwodu powtarzać dla każdego testowanego pola szachownicy, zastosowałem więc multipleksowanie - obwód załączany jest tranzystorami kolejno do wszystkich czujników, co jak łatwo policzyć daje <200ms na zeskanowanie stanu szachownicy (uwzględniając szybkość I2C i czasy przełączania w praktyce są to 3 pełne skany na sekundę - wystarcza). Skoro już umiałem testować pojedyncze pole, nadszedł czas na zaprojektowanie płytek do samej szachownicy. Tu użyłem ekspandera wyprowadzeń MCP23017 oraz demultiplexera MC74HC154. Skoro i tak nie mogę testować więcej niż jednego pola na raz, demultiplexer zapewnił mi  rozsądne wykorzystanie wyprowadzeń MCP23017 - dzięki temu wystarczył jeden ekspander na 16 pól szachownicy (każde ma jedną diodę świecącą i jeden czujnik wspomniany wczesniej SG-2BC). Prototyp tego rozwiązania wyglądał następująco:

Projekt płytki pokrywającej 16 pól (przed ułożeniem ścieżek, wizualizacja ze ścieżkami, gotowe płytki):

Na całą szachownicę użyłem 4 takich samych równolegle połączonych płytek:

Czemu nie dwóch - po jednej na stronę szachownicy? Z tej oto przyczyny że darmowa licencja DIPTrace pozwala na 300 padów na płytkę 🙂 Po polutowaniu i zmontowaniu całości otrzymałem taki oto efekt:

W montażu najtrudniejsze okazało się jednoczesne wcelowanie 32-ma okrągłymi elementami w wywiercone otwory:

Aby tego dokonać ułatwić płytki umieściłem na mosiężnych dystansach 1cm przyklejonych klejem na ciepło do wewnętrznej strony szachownicy, przewlokłem diody i czujniki przez płytkę, zakleilłem otwory w szachownicy od jej frontowej strony przezroczystą taśmą klejącą i manewrowałem cierpliwie elementami oraz samą płytkę aż wskoczyły na swoje miejsce. Dopiero wtedy płytkę przykręcałem a nóżki elementów lutowałem.

Pozostało to oprogramować 🙂 Jako że programuję od ponad 20 lat i do tej pory nie pisałem jeszcze enginu szachów, postanowiłem nie używać „cudzego” i napisać własny. Biorąc pod uwagę ograniczenia Arduino było to naprawdę fajnym wyzwaniem i zajęło mi około 2 tygodnie. Zaimplementowałem mini-max z przycinaniem alpha-beta i iteracyjnym pogłębianiem. Engine nie alokuje żadnej pamięci dynamicznie, a ze stosu bierze nie więcej niż 600B, co uważam za swój sukces. Ostatecznie wygrywa nie tylko ze mną (żaden ze mnie wybitny szachista), ale i z Stockfishem na poziomie 3, z czego jestem dumny 🙂

Ostateczny kształt szachownicy w działaniu wygląda tak:

 

Szachownica rozpoznaje ustawienie początkowe i sygnalizuje to spiralnym zaświeceniem wszystkich diod. Grę rozpoczynamy białymi lub sygnalizujemy szachownicy ze chcemy grać czarnymi poprzez podniesienie na chwile czarnego króla. Po podniesieniu bierki gracza, szachownica pokazuje dostępne pola na które figura ta może się ruszyć umieszczonymi w ich rogach diodami (mój niespełna 6-cio letni syn bardzo to docenia). Ruch szachownicy również sygnalizowany jest diodami i szachownica czeka aż zostanie wykonany. Dodatkowe dwie małe diody na krawędzi szachownicy sygnalizują po czyjej stronie jest ruch. Zdjęcie dwóch własnych bierek z szachownicy jest dla niej gestem do zapisania stanu gry do EEPROMU. Po tym można ją wyłączyć i wznowić grę np. za tydzień. Po włączeniu szachownica czyta stan z EEPROMU i czeka aż jeden ze stanów (początkowy lub zapisany) zostanie ustawiony na szachownicy. Jeśli nie była w tym czasie składana, a bierki nie były ściągane - grę można kontynuować natychmiast po włączeniu. Szachownicę można normalnie składać, niestety nie mieszczą się już do niej szachy 😉

Mam nadzieje mój pierwszy projekt się Wam spodobał, ja jeszcze wciąż się nim cieszę jak dziecko. Chciałbym przy tym podziękować Forbotowi za naprawdę świetne kursy które nie tylko dały mi niezbędną w realizacji wiedzę, ale też zainspirowały to zrobienia tejże zabawki.
 

Pozdrawiam, Okjak

Edytowano Maj 6, 2020 przez okjak

[Treker (Damian Szymański)]

@okjak witam na forum i dziękuję za opis ciekawego projektu! Miło widzieć, że nauka z naszych kursów przynosi takie efekty 🚀

[Gieneq]

O nie! Kolega mnie uprzedził 😄 od dłuższego czasu myślę nad szachownicą, ale okazało się za drogie.

Cytat

Zaimplementowałem mini-max z przycinaniem alpha-beta i iteracyjnym pogłębianiem.

Wow, interesujące! A mógłbyś napisać nieco więcej na ten temat? Też zastanawiałem się nad algorytmem i doszedłem do API szachownicy, ale Twój pomysł jest dużo bardziej ambitny.

Cytat

Skoro już umiałem testować pojedyncze pole, nadszedł czas na zaprojektowanie płytek do samej szachownicy. Tu użyłem ekspandera wyprowadzeń MCP23017 oraz demultiplexera MC74HC154.

Też ciekawy pomysł, choć czy nie dało się uniknąćekspandera?

Miałem kilka planów odnośnie szachownicy. Wymyśliłem najpierw że pola będą z PCB (64 PCB na pola i 64 na pionki... cena kosmiczna). Na polach i pionkach miały być koncentryczne pola stykowe łączone przy pomocy sprężynowych test pinów i dociskane magnesami. Każdy pionek miał mieć w sobie komórkę adresowaną np z 1-wire albo I2C, a najlepiej małego attina żeby dało się przy starcie gry przypisywać rolę i stronę dla pionka. Ale właśnie jak określić specyficzny kształt (typ pionka)... Tu można by zrobić pionki al'a warcaby (albo japońskie shogi) z małym wyświetlaczem.

To prostszy pomysł, niestety bez inteligentnych pionków z mikrokontrolerem tylko magnesik i hallotrony. Kupiłem dla testu kilka wersji hallotronów z otwartym kolektorem i złożyłem w multipleksowaną matrycę i efekt był świetny - 16 połączeń i tyle 🙂 czysta plansza nie wzbudzająca podejrzeń i cena też dość niska.

Ten pierwszy pomysł był wodotryskiem ale zabijała go cena PCB, koszt jednej sztuki to byłby ponad 1000zł. Drugi był już realny ale wtedy przyszła korona i nie dało się robić PCB 😞 Projekt na razie zawiesiłem ale ciesze się że jest ktoś kto tak łatwo się nie poddał 🙂 Super sprawa, powodzenia w dalszych projektach! 🙂 

Edytowano Maj 8, 2020 przez Gieneq

[okjak]

Hej, dziękuję bardzo 🙂

O samym algorytmie mogę napisać bardzo dużo, więc odpowiem chętnie jak będziesz miał bardziej szczegółowe pytania. Sercem algorytmu jest min-max, często używany w grach dwuosobowych o sumie zerowej (lepiej dla Ciebie to gorzej dla przeciwnika i vice versa). Sam min-max jest algorytmem typu brute force, przeszukuje drzewo ruchów na każdym poziomie szukając ruchu który da najlepszy rezultat dla gracza który go wykonuje. Zakładamy że każdy gracz wykonuje ruch najlepszy dla siebie, zatem Twój najlepszy ruch to taki dla którego sytuacja na szachownicy po najlepszym ruchu Twojego przeciwnika jest dla Ciebie najlepsza. Oczywiście nie możemy analizować w ten sposób drzewa gry zbyt głęboko bo średni współczynnik rozgałęziania dla szachów to 35, dlatego na ustalonym z góry poziomie głębokości sytuację na szachownicy oceniamy jakąś prostą (mniej lub bardziej) heurystyką. W przypadku mojego algorytmu to proste zliczanie punktów bierek, przy czym bierki oceniane są nie tylko pod względem swojej wartości, ale również pozycji (np. biały pion stojący na linii 7-mej ma większą wartość niż stojący na linii drugiej, bo zaraz możemy go wymienić na hetmana. Z ciekawostek w mojej implementacji aby uniknąć kosztownych wywołań funkcji i powrotów oraz w celu oszczędzania wielkości stosu rekurencja została "rozwinięta". Trzymam tablicę obiektów reprezentujących stan przeszukiwania na danym poziomie i iteruję się po drzewie w ramach jednej pętli while.

Jak widać w min-max mamy rekurencję i to o dużym poziomie rozgałęziania, stąd goły min-max ma zastosowanie raczej czysto akademickie. Przycinanie alpha-beta jest usprawnieniem min-max pozwalającym obcinać gałęzie przeszukiwania w sytuacji gdy ruch który już znaleźliśmy jest lepszy niż najlepszy jaki moglibyśmy z danej gałęzi uzyskać. Czy jak można się spodziewać jego wydajność (ilość obciętych gałęzi przeszukiwania) zależy od tego jak szybko odnalezione zostanie "dobre" (niekoniecznie najlepsze) rozwiązanie, dlatego można go wspomagać różnymi heurystykami. Więcej o alfa-beta znajdziesz choćby na wikipedii: https://pl.wikipedia.org/wiki/Algorytm_alfa-beta.

Jedną z heurystyk dających szansę na znalezienie w miarę szybko dobrego ruchu iteracyjne pogłębianie, które w skrócie polega na tym że najpierw przeszukujemy drzewo w poszukiwaniu najlepszego ruchu do niewielkiego poziomu (u mnie 3: ruch szachownicy, ruch przeciwnika, kolejny ruch szachownicy). W wielu przypadkach będzie to już całkiem niegłupi ruch który przy głębszym przeszukaniu może ale nie musi okazać się najlepszym. Następnie przeszukujemy drzewo do pełnej już (założonej) głębokości rozpoczynając od tego znalezionego w pierwszej iteracji ruchu - to daje szansę na obcięcie znacznie większej ilości gałęzi niż gdybyśmy zaczynali od losowego czy pierwszego możliwego ruchu. W mojej implementacji zastosowałem dodatkowo podrzucanie najlepszych ruchów również na niższych poziomach drzewa tzn: jeśli w pierwszym przeszukaniu do głębokości 3 najlepszy ruch szachownicy to X, dla którego najlepszym Twoim ruchem jest Y, a kolejnym najlepszym ruchem szachownicy Z, to w drugiej iteracji zaczynam przeszukiwać drzewo podrzucając w pierwszej kolejności te 3 ruchy na odpowiednich poziomach drzewa. Dodatkowo zmniejszam głębokość przeszukiwania jeśli nie udało mi się go skończyć w rozsądnym czasie (przyjąłem 90s), dzięki czemu nie czekamy długo na odpowiedź szachownicy w trudnych do analizy sytuacjach - troszkę to też "uczłowiecza" algorytm bo w trudnych sytuacjach jest większa szansa na zrobienie troszkę głupszego ruchu z jej strony

Kolejnym usprawnieniem, które testowałem ale ostatecznie NIE użyłem jest iteracyjne wewnętrzne pogłębianie. Jak będziesz chciał to powiem o tym coś więcej, póki co tylko tyle że przy jego użyciu często ocenia się wielokrotnie tą same sytuacje, więc aby w pełni wykorzystać jego zalety przydałaby się tzw. tablica transpozycji (hash mapa [pozycja]->[wartość]) której w żadnych rozsądnych rozmiarach nie da się zaimplementować dysponując 2000B w Arduino Uno/Mini.

Z innych ciekawostek nie mogłem sobie pozwolić na tworzenie tablicy legalnych ruchów, a to również z przyczyn pamięciowych. Ruch może być reprezentowany przez nie mniej niż 3B, a istnieją sytuacje w których ilość możliwych ruchów dochodzi do 218, co dawałoby 654B na samą tylko tablicę ruchów na danym poziomie. Musiałem więc zaimplementować iterator po legalnych ruchach co samo w sobie jest pewnie na kilka akapitów, więc niepytany tu się zatrzymam.

 

A co do elektroniki 🙂

Wpadłem również na pomysł z halotronami ale już po tym jak kupiłem 70 (kilka na zapas) SG-2BC, a że nie były tanie to już nie zmieniałem koncepcji 🙂 Moja szachownica również nie rozpoznaje figur jakie na niej stoją. Zakłada że ustawiasz szachy poprawnie, a następnie śledzi ich ruchy. I wściekle miga diodą sygalizującą Twój ruch jeśli wykonasz ruch niepoprawny 🙂 Jeśli chodzi o I2C to jest to u mnie jedyna forma komunikacji mikrokontrolera  z oprzyrządowaniem szachownicy i cieszę się że go użyłem. To bardzo sprytny protokół, ponieważ urządzenia slave nie mogą wystawiać stanu wysokiego, mogą go tylko ściągać do GND, dzięki czemu możliwa jest komunikacja komponentów pracujących na różnych napięciach. A dzięki temu np. wymieniłem ostatnio swoje pro mini (robię teraz na nim zabawkę dla dziecka, którą może się później pochwalę) na Teensy 4.0 które pracuje na 3V podczas gdy całe oprzyrządowanie szachownicy mam policzone dla 5V. Przepięcie się na Teensy było przepięciem 2 kabelków i dodanie dwóch pull-up rezystorów dla obu linii I2C - reszta pracuje jak dotychczas:

W Teensy mam również możliwość sterowania zegarem procesora (do 600MHz!), więc ustawiam go domyślnie na 12MHz jak Arduino, a przestawiam na 600MHz wyłącznie na czas "myślenia" nad ruchem przez szachownicę (zjada wtedy 100mA). Swoje płytki robiłem już w korona-czasie, Satland pracuje! 🙂

Dzięki za miłe słowa i pozdrawiam!

Okjak
 

 

 

Edytowano Maj 8, 2020 przez okjak

[Polecacz 101]

Produkcja i montaż PCB - wybierz sprawdzone PCBWay!
   • Darmowe płytki dla studentów i projektów non-profit
   • Tylko 5$ za 10 prototypów PCB w 24 godziny
   • Usługa projektowania PCB na zlecenie
   • Montaż PCB od 30$ + bezpłatna dostawa i szablony
   • Darmowe narzędzie do podglądu plików Gerber
Zobacz również » Film z fabryki PCBWay

[jaceksz73]

A nie próbowałeś zaimplementować "myślenia" podczas ruchu przeciwnika?

[okjak]

Masz na myśli aby szachownica myślała nad swoim ruchem zanim ruch wykona przeciwnik? Nie myślałem o tym, ale teraz jak o tym wspomniałeś widzę kilka zalet i wad:
Zalety:
- możliwa szybka odpowiedź na ruch jeśli zdążyłem już przeanalizować odpowiedzi na ruch który użytkownik wykonał (ale z Teensy 4.0 pomimo zwiększenia głębokości przeszukiwań o dwa poziomy, średni czas myślenia szachownicy nad ruchem to kilka sekund),

Wady:

- marnowałbym trochę prąd z baterii rozpatrując odpowiedzi na wszystkie możliwe ruchy przeciwnika, zamiast jedynie na ten który rzeczywiście zrobi,

- komplikacja programu: obecnie myślenie nad ruchem to wywołanie synchronicznej funkcji chess_engine::getTheBestMove() - do czasu jej zakończenia nie mógłbym skanować szachownicy, a wykrywanie ruchu użytkownika to intensywne skanowanie szachownicy (np. w przypadku bicia różnica stanu binarnego to jedynie zniknięcie bierki z jednego pola, aby wykryć że było to bicie muszę zauważyć że w międzyczasie zniknęła też na chwilę bierka z pola na którym była bita figura). Aby to rozwiązać musiałbym przenieść wykrywanie ruchu użytkownika do obsłgi przerwania,

- zwięszone zużycie pamięci: ruch to jak wspominałem 3B, gdybym chciał zapamiętać do późniejszego wykorzystania odpowiedzi na wszystkie możliwe ruchy przeciwnika, musiałbym odłożyć sobie na stosie na to 654B (alokowanie dynamiczne i re-alokowanie w Arduino to proszenie się o problemy).

 

Biorąc pod uwagę powyższe raczej nie będę szedł w tą stronę, tym bardziej że jedyny problem który by to rozwiązało (szybkość odpowiedzi) nie istnieje już na Teensy.

 

Pozdrawiam, Okjak

[jaceksz73]

Według mnie warto przejść na przerwania. 

Warto też zastanowić się nad STM32H7. Będziesz miał wtedy dużo więcej pamięci do dyspozycji.

Odnośnie myślenia przy ruchu przeciwnika, to przy zasilaniu bateryjnym może być problem.

Ale jeśli będą to akumulatory i wystarczą na partię, to na pewno warto.

Można wtedy spróbować zejść o poziom głębiej z analizą. 

A Ty jak grasz w szachy to myślisz przy ruchu przeciwnika? 

Generalnie gra w szachy to gra na czas. 

Gratuluję pomysłu i konsekwencji w realizaji. Naprawdę super projekt.

Zarówno sprzętowo jak i programowo. 

[okjak]

STM32H7 jest porównywalny z Teensy 4, ten sam Cortex M7, 1MB RAM.

Rzeczywiście mógłbym teraz wykorzystać więcej RAMu, który daje mi Teensy. Na pewno będę projekt rozwijał jak tylko zacznę z nim wygrywać - póki co udało mi się to zaledwie 2 razy.

Duża część uroku tej szachownicy to dla mnie jej tradycyjna forma, więc wszelkie kable wychodzące po bokach odpadają. Używam obecnie akumulatorka 9V, masz na myśli inny który zmieściłby mi się w szachownicy? Może dwie 18650?

Oczywiście że myślę nad ruchem podczas tury przeciwnika, ale z drugiej strony ciężko porównać mnie do komputera, analityczne procesy przeprowadzam na pewno wolniej, ale jestem z pewnością nieco bardziej kreatywny 😉 Choć to co wyprawiają w szachach ostatnio sieci neuronowe jest też niesamowite.

Szczerze mówiąc nie traktuję szachów jako grę na czas, przynajmniej nie w podstawowej formie. W czasach licealnych grałem w klubie szachowym turnieje blitza ale nigdy nie była to moja ulubiona forma gry w szachy.

Wielkie dzięki za sugestie i miłe słowa 🙂

Edytowano Maj 8, 2020 przez okjak

[Arduino]

Proponuję do pionków zamontować kawałki metalu a w szachownicy elektromagnesy, które szachownica włączałaby i przyciągała pionki.

[japko1024]

Zapis do EEPROM może się przydać też podczas gry z drugą osobą, jakby trzeba było nagle przerwać. Trzeba tylko znaleźć sposób zaprezentowania, gdzie trzeba ustawić bierki, jeśli były złożone. Najprościej (bez żadnych modyfikacji hardware'u) byłoby albo odczytywać zawartość pamięci za pomocą komputera (i ew. napisać działający na nim program do pokazywania zapisu w formie graficznej), albo ustalić jakąś kolejność, w której poszczególne bierki będą ustawiane na szachownicy - dioda będzie pokazywać, na którym polu postawić jedną z nich, po wykryciu postawienia przez czujnik będzie się zaświecać następna.

[okjak]

Wydaje mi się że do gry z drugą osobą łatwiej może być zrobić zdjęcie komórką, szachownica nie musi znać położenia pionków, nie musi być nawet włączona 🙂

Jeśli chodzi o elektromagnesy - czemu szachownica miałaby przyciągać pionki? Czy może masz na myśli mechanizm który ruszałby pionkami za pomocą elektromagnesów?

[Arduino]

Tak żeby szachownica sama wykonywała swój ruch.

[Yubi]

@Arduino Fajny pomysł, przypomina mi to trochę: https://www.youtube.com/watch?v=a6WQZuIV_hk - no może pionki nie będą się tak ładnie animowały 🙂

Co do samego projektu kozak, jeżeli naprawdę byłeś w stanie po kilku miesiącach zbudować takie cudo to zazdroszczę wiedzy i umiejętności. 

 

[okjak]

Dzięki Yubi 🙂

Wiedzę elektroniczną zdobywałem w trakcie projektowania i prototypowania, kursy Forbota dały mi na prawdę fajny start. Potem już noty katalogowe, tani oscyloskop i debugowanie problemu po problemie, aż się skończyły problemy 😉 Programowaniem zajmuję się od dzieciaka i zawodowo od 16 lat, skończyłem też studia informatyczne z (między innymi) specjalnością AI, więc sam engine szachów zajął mi mniej więcej czas oczekiwania na realizację zaprojektowanych płytek - dzięki temu też mi się tak nie dłużyło 😛