Projekt · W budowie

Ramię robota grające w warcaby

Budujemy ramię robota, które rozgrywa partię warcabów na prawdziwej planszy i samo przestawia pionki.

Plansza
8 × 8, 32 pola gry
Kalibracja
5 punktów
Wybór ruchu
2 półruchy naprzód
Testy
68 w pytest

Pozycja startowa

Rys. 1. Symulacja partii w przeglądarce. Ruchy wybiera ten sam algorytm co program ramienia (sekcja 4), a pokaz kończy się najpóźniej po 40 ruchach.

Streszczenie

Zbudowaliśmy stanowisko, na którym ramię robota samo gra w warcaby na prawdziwej planszy. Program zna zasady gry i gra za obie strony. Przed każdym ruchem sprawdza, co może odpowiedzieć druga strona, i wybiera ruch, po którym strona, która ma ruch, ma największą przewagę w pionkach. Przed grą ręką ustawiamy ramię nad czterema rogami planszy, a program sam wylicza, gdzie są pozostałe pola. Komputer wysyła ramieniu polecenia przez Wi-Fi. Na razie ramię gra samo ze sobą, za obie strony. Teraz pracujemy nad kamerą: program ma zobaczyć, jaki ruch zrobił człowiek, żeby ramię mogło z nim zagrać.

Słowa kluczowe: ramię robota, warcaby, wybór ruchu, ustawienie planszy, kamera.

1 / Wprowadzenie

Ramię gra samo ze sobą.

Ramię rozgrywa partię warcabów angielskich za obie strony. Podnosi pionek przyssawką, stawia go na nowym polu, a zbite pionki odkłada do pudełka obok planszy. Stan gry i listę legalnych ruchów daje biblioteka pydraughts [1].

W tym trybie program nie widzi planszy. Zna tylko stan gry w pamięci, więc przed startem ustawiamy pozycję startową i nikt nie dotyka pionków.

2 / Stanowisko

Z czego się składa.

  1. 01

    Dobot Magician

    Biurkowe ramię robota. Program podaje mu pozycję końcówki: x, y i z w milimetrach oraz obrót r w stopniach.

  2. 02

    Przyssawka z pompką

    Podnosi pionek od góry. Po włączeniu pompki program czeka 300 ms, zanim podniesie ramię, aby przyssawka zdążyła złapać.

  3. 03

    Moduł Wi-Fi USR-C322

    Działa jako serwer UDP na porcie 8899. Każdy pakiet z komputera przekazuje na port szeregowy ramienia, więc komputer nie potrzebuje kabla do ramienia.

  4. 04

    Plansza i pudełko

    Zwykła plansza 8x8 z pionkami. Obok planszy stoi pudełko, do którego ramię odkłada zbite pionki.

3 / Zasady gry

Warcaby angielskie.

Program gra w wariant angielski (checkers) [3]:

  • Każda strona ma 12 pionków na ciemnych polach. Ciemne zaczynają.
  • Pionek idzie po skosie o jedno pole do przodu.
  • Bicie jest obowiązkowe. W jednym ruchu pionek może bić kilka razy i musi wykonać wszystkie bicia w wybranej sekwencji, ale nie musi wybrać sekwencji z największą liczbą bić.
  • Pionek, który dojdzie do ostatniego rzędu, zostaje damką, a ruch się kończy. Damka może iść o jedno pole także do tyłu.
  • Strona, która nie ma ruchu, przegrywa.

Grywalne pola mają numery od 1 do 32. Zapis 22-18 to zwykły ruch, a 18x9 to bicie. Tak samo zapisujemy ruchy, które wysyłamy do ramienia.

W dalszej części oznacza pozycję, zbiór legalnych ruchów w tej pozycji, a pozycję po ruchu .

4 / Wybór ruchu

Jak program decyduje.

4.1 Funkcja oceny

Program ocenia pozycję z punktu widzenia strony, która wybiera ruch, bilansem materiału:

(1)

gdzie to pionki strony, która wybiera ruch, a pionki drugiej strony. Gdy gra się skończyła, pozycja wygrana ma ocenę , a przegrana . Przy remisie zostaje bilans materiału.

4.2 Reguła wyboru

Program sprawdza każdy ruch strony, która ma ruch, i każdą odpowiedź drugiej strony , czyli dwa półruchy naprzód. Dla każdego ruchu liczy : najgorszy bilans punktów po odpowiedzi drugiej strony. Potem wybiera ruch z największym :

(2)

Algorytm 1 zapisuje tę regułę krok po kroku, a Rys. 2 wykonuje go ręcznie na przykładzie. Algorytm dodaje jeden przypadek: jeśli po ruchu gra się kończy, (linia 2). Gdy kilka ruchów ma to samo , program losuje jeden z nich (linia 5), dlatego każda partia wygląda inaczej.

Algorytm 1. Wybór ruchu (choose_move, głębokość 2)
wejście: pozycja s1  dla każdego ruchu m ∈ M(s):2      jeśli po m gra się kończy:  v(m) ← ±100 (przy remisie E(s·m))3      w przeciwnym razie:         v(m) ← najmniejsze E(s·m·m′) po m′ ∈ M(s·m)4  N ← ruchy m z największym v(m)5  m* ← losowy ruch z N

Pozycja s M(s): 3 możliwe bicia

  1. ruch ABicie jednego pionka, bez odbicia

    • odpowiedź m′Druga strona nie ma bicia i robi spokojny ruch?
    • odpowiedź m′Druga strona robi inny spokojny ruch?

  2. ruch BBicie dwóch pionków naraz

    • odpowiedź m′Druga strona musi bić i odbija jeden pionek?
    • odpowiedź m′Druga strona musi bić i odbija dwa pionki naraz?

  3. ruch CBicie jednego pionka w drugą stronę

    • odpowiedź m′Druga strona musi bić i odbija jeden pionek?
    • odpowiedź m′Druga strona odbija jeden pionek w inny sposób?

Strona, która ma ruch, może bić, więc musi bić: M(s) to trzy bicia, A, B i C. Przed ruchem bilans wynosi 0. Na razie nie znamy wyników.

Rys. 2. Algorytm 1 wykonany ręcznie na małym drzewie gry. Liczby są przykładowe: to bilans punktów strony, która wybiera ruch, po jej ruchu i odpowiedzi drugiej strony. Bicie jest obowiązkowe, więc gdy strona może bić, wszystkie jej możliwe ruchy to bicia.

5 / Kalibracja

Skąd ramię wie, gdzie jest pole.

Ramię zna tylko swoje współrzędne, a nie położenie planszy. Dlatego przed grą robimy kalibrację (Algorytm 2). Trzymamy przycisk na przedramieniu, który odblokowuje ramię, i ręką ustawiamy przyssawkę na pionkach na czterech narożnych polach: a1, h1, a8 i h8. Dla każdego narożnego pola program zapisuje jego położenie i wysokość w milimetrach. Na końcu zapisuje punkt nad pudełkiem na zbite pionki, z wysokością . Z tych punktów liczy położenie każdego pola (3) i dwie wysokości: (4) i (5).

Algorytm 2. Kalibracja (calibrate_interactive)
wejście: pionki na polach a1, h1, a8 i h8, ramię odblokowane1  dla każdego narożnego pola k ∈ {a1, h1, a8, h8}:2      ustaw przyssawkę na pionku na polu k, zapisz p_k = (x, y) i z_k3  ustaw przyssawkę nad pudełkiem, zapisz jej położenie i z_pudełko4  z_chwyt ← średnia z czterech z_k                       (4)5  z_bezp ← max(z_chwyt + 40 mm, z_pudełko)                (5)6  jeśli max z_k − min z_k > 5 mm: ostrzeż, że plansza może leżeć krzywo7  zapisz wszystko w pliku robot_calibration.json

5.1 Położenie pola

W czasie gry program liczy środek pola w kolumnie i rzędzie , gdzie ( to kolumna a, to rząd 1), interpolacją dwuliniową z czterech narożnych pól:

(3)

gdzie i . Liczby przed to wagi narożnych pól. Zawsze sumują się do 1. Dzięki temu plansza nie musi leżeć prosto względem ramienia.

5.2 Wysokość

Wysokość chwytu to średnia z czterech pomiarów (linia 4). Między polami ramię jeździ na bezpiecznej wysokości : domyślnie 40 mm wyżej, ale nie niżej niż punkt nad pudełkiem (linia 5):

(4)
(5)

Gdy , program ostrzega, że plansza może nie leżeć poziomo (linia 6).

Pole d4: c = 3, r = 3, więc u = 3/7 ≈ 0,43 i v = 3/7 ≈ 0,43.

Narożne poleWaga(x, y) w mm
a10,33(267,4; −110,8)
h10,24(299,0; −9,3)
a80,24(171,3; −83,7)
h80,18(201,1; 18,9)

p(d4) = (239,4; −55,5) mm

zchwyt = −23,4 mm, zbezp = −23,4 + 40 = 16,6 mm

Rys. 3. Równanie (3) na prawdziwych pomiarach z kalibracji naszego stanowiska (plik robot_calibration.json). Kliknij pole, aby zobaczyć wagi narożnych pól i wyliczone położenie. Współrzędne są w milimetrach, w układzie ramienia.

6 / Wykonanie ruchu

Co robi ramię w czasie ruchu.

  1. 01

    Ramię jedzie nad pole startowe na wysokości z równania (5).

  2. 02

    Zjeżdża w dół po linii prostej do wysokości , aż przyssawka dotknie pionka.

  3. 03

    Włącza przyssawkę i czeka 300 ms.

  4. 04

    Podnosi pionek i jedzie nad pole docelowe. Przy wielokrotnym biciu jedzie od razu na ostatnie pole.

  5. 05

    Zjeżdża w dół, wyłącza przyssawkę i wraca do góry.

  6. 06

    Każdy zbity pionek podnosi tak samo i puszcza nad pudełkiem.

7 / Komunikacja

Pakiety przez Wi-Fi.

Każde polecenie to krótki pakiet binarny w protokole szeregowym Dobota [2]. Rys. 4 pokazuje polecenie, które włącza przyssawkę.

Rys. 4. Pakiet z poleceniem 62 (przyssawka), zapisany do kolejki ramienia.

7.1 Suma kontrolna

Niech to bajty polecenia, kontroli i parametrów. Ostatni bajt pakietu to

(6)

Dla pakietu z Rys. 4: , więc . Program liczy tę samą sumę dla każdej odpowiedzi ramienia i odrzuca odpowiedź ze złą sumą.

7.2 Kolejka i zgubione pakiety

Ruchy, przyssawka i czekanie trafiają do kolejki w ramieniu. Każde polecenie w kolejce dostaje numer. Co 0,2 s program pyta o numer polecenia, które ramię właśnie wykonuje, i tak wie, kiedy ruch się skończył.

UDP może zgubić pakiet, a pierwsza odpowiedź po przerwie potrafi przyjść po ponad 2 s. Dlatego program czeka na odpowiedź do 4 s. Gdy odpowiedź nie przyjdzie, polecenie natychmiastowe (na przykład odczyt pozycji) wysyła ponownie, do dwóch razy. Polecenie do kolejki wysyła tylko raz, bo druga kopia poruszyłaby ramię dwa razy. Zatrzymanie programu od razu zatrzymuje ramię i czyści kolejkę.

8 / Co dalejW trakcie prac

Partia z człowiekiem.

Pracujemy nad kamerą, która patrzy na planszę z góry. Gdy człowiek przestawi pionek ręką, program ma rozpoznać ruch, a ramię ma odpowiedzieć.

9 / Czego się nauczysz

Co daje praca przy projekcie.

  1. 01

    Python i testy

    Kod projektu ma 68 testów w pytest. Wszystkie przechodzą bez podłączonego ramienia i bez kamery.

  2. 02

    Sterowanie robotem

    Kolejka poleceń, kalibracja, układ współrzędnych ramienia i bezpieczne zatrzymanie.

  3. 03

    Komunikacja

    Pakiety binarne, sumy kontrolne, UDP przez Wi-Fi i obsługa zgubionych odpowiedzi.

  4. 04

    Widzenie komputerowe i algorytmy

    OpenCV, transformacje perspektywiczne, przestrzenie barw oraz przeszukiwanie drzewa gry.

  • Python
  • pydraughts
  • NumPy
  • OpenCV
  • ffmpeg
  • pytest
  • Dobot Magician
  • USR-C322
  • UDP

Źródła

Bibliografia

  1. [1]

    pydraughts: biblioteka warcabów dla Pythona (generowanie ruchów, zapis PDN, warianty, w tym angielski). github.com/AttackingOrDefending/pydraughts

  2. [2]

    Dobot Communication Protocol V1.1.5. Dokumentacja protokołu ramienia Dobot Magician. download.dobot.cc/product-manual/dobot-magician/pdf/en/Dobot-Communication-Protocol-V1.1.5.pdf

  3. [3]

    English draughts. Wikipedia. en.wikipedia.org/wiki/English_draughts

Chcesz budować z nami?

Wypełnij krótki formularz. Odezwiemy się i pomożemy Ci wybrać dział.

Dołącz do SEEKWszystkie projekty