Skocz do zawarto艣ci

Pomocna odpowied藕

Podoba Ci si臋 ten projekt? Zostaw pozytywny komentarz i daj zna膰 autorowi, 偶e zbudowa艂 co艣 fajnego!

Masz uwagi? Napisz kulturalnie co warto zmieni膰. Doce艅 prac臋 autora nad konstrukcj膮 oraz opisem.

@okjak聽witam na forum i dzi臋kuj臋 za opis ciekawego projektu! Mi艂o widzie膰, 偶e nauka z naszych kurs贸w przynosi takie efekty 馃殌

  • Lubi臋! 1

Udost臋pnij ten post


Link to post
Share on other sites
(edytowany)

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 przez Gieneq
  • Lubi臋! 1

Udost臋pnij ten post


Link to post
Share on other sites
(edytowany)

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:

IMG-8785.thumb.jpg.1365e4cb48ce5139ddbf0e4eaf1a0db2.jpg

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 przez okjak
  • Lubi臋! 1

Udost臋pnij ten post


Link to post
Share on other sites

A nie pr贸bowa艂e艣 zaimplementowa膰 "my艣lenia" podczas ruchu przeciwnika?

Udost臋pnij ten post


Link to post
Share on other sites

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

Udost臋pnij ten post


Link to post
Share on other sites

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.聽

Udost臋pnij ten post


Link to post
Share on other sites
(edytowany)

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 przez okjak
  • Lubi臋! 1

Udost臋pnij ten post


Link to post
Share on other sites

Proponuj臋 do pionk贸w zamontowa膰 kawa艂ki metalu a w szachownicy elektromagnesy, kt贸re szachownica w艂膮cza艂aby i przyci膮ga艂a pionki.

Udost臋pnij ten post


Link to post
Share on other sites

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.

  • Lubi臋! 1

Udost臋pnij ten post


Link to post
Share on other sites

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?

Udost臋pnij ten post


Link to post
Share on other sites

Tak 偶eby szachownica sama wykonywa艂a sw贸j ruch.

Udost臋pnij ten post


Link to post
Share on other sites

@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.聽

  • Lubi臋! 1

Udost臋pnij ten post


Link to post
Share on other sites

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 馃槢

  • Lubi臋! 1

Udost臋pnij ten post


Link to post
Share on other sites
Zarejestruj si臋 lub zaloguj, aby ukry膰 t臋 reklam臋.

jlcpcb.jpg

jlcpcb.jpg

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

Do艂膮cz do dyskusji, napisz odpowied藕!

Je艣li masz ju偶 konto to zaloguj si臋 teraz, aby opublikowa膰 wiadomo艣膰 jako Ty. Mo偶esz te偶 napisa膰 teraz i zarejestrowa膰 si臋 p贸藕niej.
Uwaga: wgrywanie zdj臋膰 i za艂膮cznik贸w dost臋pne jest po zalogowaniu!

Anonim
Do艂膮cz do dyskusji! Kliknij i zacznij pisa膰...

×   Wklejony jako tekst z formatowaniem.   Przywr贸膰 formatowanie

  Dozwolonych jest tylko 75 emoji.

×   Tw贸j link b臋dzie automatycznie osadzony.   Wy艣wietla膰 jako link

×   Twoja poprzednia zawarto艣膰 zosta艂a przywr贸cona.   Wyczy艣膰 edytor

×   Nie mo偶esz wklei膰 zdj臋膰 bezpo艣rednio. Prze艣lij lub wstaw obrazy z adresu URL.


×
×
  • Utw贸rz nowe...