Code Bots 3: Parallel Programming Antipatterns

13

Witamy spowrotem! Jestem podekscytowany, że mogę zaprezentować trzecie wyzwanie CodeBots. Ten był od dawna w trakcie tworzenia. Wyzwanie zostanie podzielone na 3 części: krótką, długą i dodatkowe szczegóły.

Krótka wersja

Każdy zawodnik napisze program z 24 poleceniami. Boty te będą się przemieszczać na całym świecie i kopiować swój kod do innych botów, jednocześnie próbując uniemożliwić innym botom zrobienie tego samego. Jednym z możliwych poleceń jest brak operacji Flag. Jeśli bot ma więcej twoich Flagniż jakikolwiek inny bot Flag, dostajesz punkt. Wygrywasz, mając najwięcej punktów.

Wszystkie powyższe dotyczyły dwóch ostatnich wyzwań. Tym razem boty będą mogły uruchamiać wiele linii kodu jednocześnie.

Wersja długa

API

Każdy bot będzie miał dokładnie 24 linie, przy czym każda linia ma następujący format:

$label command parameters //comments

Etykiety i komentarze są opcjonalne, a każde polecenie ma inną liczbę parametrów. Wszystko nie rozróżnia wielkości liter.

Parametry

Parametry są wpisane i mogą mieć następujące formaty:

  1. Wartość od 0 do 23.
  2. Zmienna: A, B, C,D
  3. Wartość wykorzystująca dodatek: A+3lub2+C
  4. Wiersz kodu, który jest oznaczony za pomocą #znaku ( #4reprezentuje piątą linię, a #C+2reprezentuje linię obliczoną przez C+2).
  5. Możesz użyć $labelzamiast oznaczenia linii kodu.
  6. Zmienna lub linia kodu przeciwnika, wyznaczona przez *. Twój przeciwnik jest botem na kwadracie, przed którym stoisz. ( *Breprezentuje Bwartość przeciwnika , a *#9reprezentuje 10. linię przeciwnika). Jeśli na tym kwadracie nie ma nikogo, polecenie nie zostanie wykonane.

Polecenia

Przesuń V.

Porusza bota North+(V*90 degrees clockwise). Ruch nie zmienia kierunku.

Skręć w V.

Obraca bota w V*90 degreesprawo.

Skopiuj VW

Egzemplarzy, co jest w Vw W. Jeśli Vjest to numer linii, to Wmusi to być numer linii. Jeśli Vjest zmienną lub wartością, to Wmusi być zmienną.

Flaga

Nic nie robi.

Gwiazda telewizyjna

Rozpoczyna nowy wątek dołączony do zmiennej V. Natychmiast i przy każdej kolejnej turze wątek wykona polecenie on-line V.

Jeśli Vjest już dołączony do wątku, to polecenie nie działa. Jeśli Vjest zmienną przeciwnika, przeciwnik rozpocznie wątek dołączony do tej zmiennej.

Stop V.

Zatrzymuje nić dołączoną do zmiennej Vna końcu tej tury.

Zablokuj V.

Zapobiegaj Vużywaniu linii lub zmiennej w jakikolwiek sposób, z wyjątkiem wywoływanego wątku Lock. Kolejne wywołanie Locktego samego wątku odblokowuje się V. Blokad nie można wywoływać na zmiennych lub liniach przeciwnika.

Jeśli Cond VW

To przetestuje Cond. Jeśli warunek jest spełniony, wówczas wskaźnik nitki przesunie się na numer linii V, w przeciwnym razie na numer linii W. Ta linia zostanie natychmiast wykonana.

Warunkowe może być X=Y, X<Y, !X, lub ?X:

  1. X=Y sprawdza, czy dwie linie są tego samego typu i od tego samego bota, lub testujesz, czy dwie wartości są równe tej samej wartości.
  2. X<Ysprawdza, czy wartość Xjest mniejsza niż Y.
  3. !Xsprawdza, czy zmienna lub linia Xjest zablokowana (zwraca true, jeśli zablokowana)
  4. ?X sprawdza, czy dana zmienna ma dołączony wątek

Dodatkowe Szczegóły

Interakcje wielowątkowe

Działania tego samego typu są wykonywane jednocześnie. Akcje są wykonywane w następującej kolejności:

  1. Zamek. Jeśli kilka wątków spróbuje zablokować zmienną, wszystkie zawiodą. Jeśli wątek odblokowuje zmienną, podczas gdy inny próbuje ją zablokować, zmienna pozostanie odblokowana.

  2. Początek. Jeśli kilka wątków podejmie próbę uruchomienia wątku na zmiennej, będzie to liczone jako pojedynczy początek.

  3. Kopiuj. Jeśli dwa wątki zostaną skopiowane do tej samej zmiennej, zmienna zakończy się losową wartością. Jeśli oba zostaną skopiowane do tej samej linii, żadne z nich nie będzie działać. Jeśli wątek kopiuje do tej samej zmiennej, z której kopiuje inny wątek, to ten drugi wątek skopiuje losową wartość. Jeśli oba wątki kopiują z tej samej zmiennej, oba będą działać poprawnie.

  4. Gdyby. Wszystkie warunki warunkowe będą testowane jednocześnie, a następnie zmienne wątku zostaną zaktualizowane po. Wykonanie Ifmoże spowodować dodanie akcji o wyższym priorytecie. Działania o wyższym priorytecie zostaną wykonane przed przejściem dalej If, natomiast działania o niższym priorytecie zostaną wykonane po If.

  5. Ruszaj się. Wiele ruchów tego samego bota spowoduje przesunięcie bota o sumę wszystkich ruchów. Jeśli wiele botów znajdzie się w tym samym miejscu, zostaną one przywrócone do miejsca początkowego.

  6. Skręcać. Suma wielokrotnych włączeń tego samego bota.

  7. Zatrzymać. Wiele poleceń zatrzymania dla tej samej zmiennej będzie liczonych jako pojedynczy zatrzymanie.

Inne szczegóły

Twój początkowy wątek zaczyna być dołączany do Dzmiennej

Ponowne użycie polecenia If(o Ifskierowanej do siebie instrukcji) spowoduje, że bot nie będzie nic robił

Jeśli wątek zostanie zatrzymany po zablokowaniu, zamki te zostaną odblokowane

Działania polegające na użyciu zablokowanej zmiennej lub linii nic nie zrobią.

Jeśli bot ma mniej niż 24 linie, pozostałe linie zostaną wypełnione Flag

Wykonanie zapisu na zmiennej, która jest również dołączona do wątku początkowego, spowoduje, że wątek rozpocznie wykonywanie nowej wartości, gdy wątek rozpocznie następną turę.

Boty są umieszczane w świecie toroidalnym według następującego wzoru:

B...B...B...
..B...B...B.
B...B...B...

Dodałem kilka przykładowych botów, które zostały skomentowane jako odnośniki językowe.

Kontroler znajduje się tutaj . Pracowałem nad tym przez długi czas, ale prawdopodobnie nadal zawiera błędy. Gdy specyfikacja i kontroler są ze sobą sprzeczne, specyfikacja jest poprawna.

Tablica wyników

1. 771  LockedScannerBot
2. 297  CopyAndSelfFlag
3. 289  DoubleTapBot
4. 197  ThreadCutterBot
5. 191  TripleThread
6. 180  ThickShelled
7. 155  Attacker
8. 99   RandomMover
9. 90   BananaBot
10. 56  LockedStationaryDoubleTap
Nathan Merrill
źródło
Wow, przynajmniej DoubleTap wydaje się znacznie lepszy niż próbki!
Katenkyo,
Co powinno się stać, jeśli spróbuję odczytać zablokowaną zmienną z innego wątku? Powiedzmy, że ZABLOKUJĘ A następnie w innym wątku jest PRZESUŃ A. Czy A ocenia na 0 lub wartość losową, czy ruch kończy się niepowodzeniem, czy ...?
Sparr,
To samo dzieje się, gdy nić osiągnie linię zablokowaną przez inny nić. Czy to jest noop? Czy to pomija?
Sparr
Czy „Kopiuj $ etykieta A” powinno działać? Interpretuje to jako „Kopiuj 11 A”, co nie jest poprawne i powoduje awarię interpretera, zamiast „Kopiuj 11 A”, jak bym się spodziewał.
Sparr,
możliwy błąd ... Wydaje mi się, że potrafię czytać własne linie flag, aby z nich skopiować, nawet jeśli są one zablokowane przez inny wątek.
Sparr

Odpowiedzi:

3

Zablokowany skaner Bot

Skanuje wroga tak szybko, jak to możliwe i zastępuje linie flagami.

    Lock D
    Copy $a A
    Start A
    Copy $b B
    Start B

$d  Lock $d0
    Lock $d1    
$d0 Copy $flag *#C+1
$d1 If 1=1 $d0 $d0

$a  Lock A
    Lock $a0
    Lock $a1
    Lock $a2
$a0 Copy $flag *#C
$a1 Copy C+2 C
$a2 If !*#C $a1 $a0

$b  Lock B
    Lock $b0
    Lock $b1
    Lock $b2
$b0 Move C
$b1 Turn 1
$b2 If 1=1 $b0 $b0

$flag Flag
Numer jeden
źródło
Jestem ciekawy warunków w twoim wątku A. ! * # C sprawdza, czy linia twojego celu #C (twoje C) jest zablokowana, prawda? Jak to jest pomocne?
Sparr
@Sparr Wątek A nie marnuje czasu, zastępując linię kodu przeciwnika flagą, jeśli jest zablokowana.
TheNumberOne
Dzięki. Źle odczytałem specyfikację dotyczącą szybkości instrukcji If.
Sparr
3

DoubleTapBot

Ten bot ma 3 wątki: jeden do poruszania się (A), dwa pozostałe do oznaczania (B i D). Flaga B 1/2 obrotu, flaga D 1/3 obrotu. Więc w pewnym momencie podwoi flagę przeciwnika :).

Zakładam, że C powróci do 0, jeśli przekroczy 23.

Powinno być całkiem bezpiecznie, jeśli ma trochę czasu na przygotowanie się (8 zwojów), ponieważ zawsze będzie działał normalnie co najmniej 2 wątki (A i B).

Nie mogę tego teraz wypróbować, więc zrobię test, kiedy wrócę do domu :)

Lock D          //Thread D locks itself
Copy 6 A        //Thread A will start line 6
Start A     
Copy 13 B       //Thread B will start line 13
Start B        
Copy 20 D       //Moving Thread D to an other part of the program
Lock A          //Thread A locks itself and the line it will be using
Lock #10
Lock #11
Lock #12
Move C          //Move in a pseudo random direction
Turn 1      //always turn to the right
If 1=1 #10 #10  //return to Move C
Lock B          //Thread B locks itself and the line it will be using
Lock #13
Lock #14
Copy #18 *#C    //Copy a flag to the Cth line of the opponent
If 1=1 #16 #16  //jump back to the copy
Flag   
Flag   
Copy C+1 C      //Increment C
Copy #19 *#C+1  //Copy a flag to the Cth+1 line of the opponent
If 1=1 #20 #20  //jump back to the increment
Flag 
Katenkyo
źródło
Numer blokady nie jest prawidłowym poleceniem. Umieszczam # znaki przed każdą z liczb. Ponadto polecenie brzmi „Obróć”, a nie „Obróć”
Nathan Merrill,
@NathanMerrill Jak to jest literówka, zapomnij o #, dzięki za wskazanie go. A dla kolei zmodyfikuj swój post, więc napisałeś Turn V Obraca bot V * 90 stopni w prawo. :)
Katenkyo
O tak. Zakręt jest właściwie poprawny, wrócę więc i zaktualizuję kod
Nathan Merrill,
Blokujesz 11,12,13, kiedy chcesz zablokować 10,11,12?
Sparr,
Wow, dzięki za zwrócenie na to uwagi!
Katenkyo
2

Zablokowane stacjonarne podwójne dotknięcie

Zainspirowany DoubleTapBot @ Katenkyo, ten rezygnuje z kilku flag i wszelkiej nadziei na ruch w zamian za całkowite zablokowanie własnych wątków, więc nigdy nie będzie można go przeprogramować. Nadal jednak podatne jest na pisanie flag wroga w niepętlących obszarach kodu.

Lock $flag              // lock the only flag line, super important!
Lock D                  // lock thread D
Copy 10 A
Start A                 // start thread A at $Astart
Copy 17 B
Start B                 // start thread B at $Bstart
Lock $D1                // lock thread D lines
Lock $D2                // thread D should be safe on turn 8
$D1 Turn C              // Spin in place, once every 2 turns
$D2 If 0=0 $D1 $D1      // thread D loop
$Astart Lock A          // thread A starts here, locks itself
Lock $A1                // lock thread A lines
Lock $A2
Lock $A3                // thread A should be safe on turn 7
$A1 Copy $flag *#C      // ATTACK! once every 3 turns
$A2 Copy C+1 C          // increment C, used for attacks and turning
$A3 If 0=0 $A1 $A1      // thread A loop
$Bstart Lock B          // thread B starts here, locks itself
Lock $B1                // lock thread B lines
Lock $B2                // thread B should be safe on turn 8
$B1 Copy $flag *#C+12   // ATTACK! once every 2 turns
$B2 If 0=0 $B1 $B1      // thread B loop
$flag Flag
Sparr
źródło
Haha, Zablokowanie flagi to całkiem niezły pomysł, powinienem o tym pomyśleć! W każdym razie cieszę się, że mój bot dał komuś inspirację!
Katenkyo
@Katenkyo to dobry pomysł, jeśli działa, ale nie sądzę, że powinien działać. Reguły zgodnie z opisem sugerują, że jeśli D zablokuje linię flagi, to A / B nie będzie w stanie jej skopiować. Wydaje się jednak, że tak nie jest. Zgłoszenie błędu w komentarzach do pytania.
Sparr
1

Random Mover

Porusza się w kierunku psuedorandom

Copy 5 C
Copy 8 B
Start C
Move A // If you can't catch me, you can't modify me
If 1=1 #3 #3 //Continue to execute the above line
Start B
Copy 4 A
If 1=1 #6 #6 //Continue to execute the above line
Flag
Copy 5 A
If 1=1 #9 #9 //Continue to execute the above line
Nathan Merrill
źródło
1

Grube łuskane

Blokuje jego rzeczy tak bardzo, jak tylko może

Copy 5 B //Designating that the B thread will start on line 5
Start B //Starting the B thread
Lock C //Preventing C from being used
Copy A+1 A //The two threads are offset, meaning that the two threads shouldn't access this at the same time
Lock #A
Copy 2 B
Nathan Merrill
źródło
1

Bot atakującego

Kopiuje flagi do różnych lokalizacji

Copy A+1 A // Increment A
Move A //Move in the Ath direction
Turn A //Rotate A times
Copy #8 *#A //Copy my flag over
Copy 23 D //Loop back to the beginning.  (I use 23 here as threads auto-increment)
Nathan Merrill
źródło
0

Potrójny wątek

Ten prosty bot uruchamia trzy wątki, wszystkie z tym samym kodem. Każdy wątek atakuje o 1/3 obrotu, porusza się o 1/6, obraca o 1/6 i wykonuje księgowość 1/3.

Move 0
Start A
Start B
$loop Copy #A+9 *#C
Move C
Copy #A+9 *#C
Turn C
Copy C+1 C
If 0=0 $loop $loop
Sparr
źródło
0

Banana Bot

Próbuje wrzucić banany w koło wroga, zanim wróg będzie mógł cokolwiek zrobić. Skłonny do zgniecenia.

$d     If !*D $d1 $d0
$d0    Copy 24 *D
$d1    If !D $d2 $start
$d2    If !*B $d5 $d3
$d3    Copy 24 *B
$d4    Copy $d D

$start Lock D             //Banana's like to split.
       Copy $a A
       Start A
       Copy $b B
       Start B
       Lock $flag

$d5    Copy $start *C     //It's okay if enemy messes up our start.
       Copy $d d

$a     Lock A
$a1    Move C
       Turn 1
       Copy $a1 A

$b     Lock B
$b0    Copy C+1 C
       If !*#C $b0 $b1    //Banana's are good at slipping.
$b1    Copy $flag *#C
$b2    Copy $b0 B

$flag  Flag
Numer jeden
źródło
0

Obcinacz nici Bot

   Lock D
   Lock $f
   Copy 16 C
$S If ?*D $1 $2
   Move 1
   Copy $S D
$f Flag
$1 Stop *D
$2 If ?*A $3 $4
$3 Stop *A
$4 If ?*B $5 $6
$5 Stop *B
$6 Copy $f *#C
   Copy C+1 C
   If *#C=#C $E $6
   Copy 2 D
$E Start *D

Zatrzymaj wszystkie wątki wroga przed wypełnieniem kodu.

MegaTom
źródło
0

Kopiowanie i samodzielna flaga

Ten bot uruchamia trzy wątki. Wątek D porusza się, dopóki nie trafi na wroga, a następnie próbuje skopiować do niego flagę, a następnie przesuwa się w losowym kierunku. Wątek A kopiuje własną flagę przez niepotrzebne wiersze kodu bota. Wątek B to tylko licznik. Zmienna, flaga i wiersze kodu używane przez każdy wątek są całkowicie zablokowane w pierwszych 15 zwojach, a bot zastępuje prawie cały kod startowy własnymi flagami. Nie sądzę, że po 15. rundzie można przekonwertować tego bota na baner innej drużyny bez dedykowanego bota atakującego, który napisałby do niego flagi.

    Lock D              // Lock D thread
    Copy $AS A
    Start A             // Start A thread at $AS
    Start B             // B is just a counter
    Copy $DL D          // Jump to D thread startup code
$DC Start B             // Don't let B thread get stopped
$D0 If !*#B $D1 $D2
$D1 Copy $DF *#B
$D2 If !*#B+6 $D3 $DM
$D3 Copy $DF *#B
$DM Move B              // Move some direction after attacking
$DA Move 0              // Move north ...
    If ?*D $DC $DA      // until we hit a live target
$DF Flag                // Flag to copy
$DL Lock #B+3           // Lock the D thread's lines
    If B<12 $DL $DA     // jump to `Move 0` when D thread is safe
$AS Lock A
$AL Lock #B+20
    If B<4 $AL $AD
    Copy 23 B           // reset B so A doesn't overwrite its own code
$AF Flag
    Flag
$AD Copy $AF #B+1       // Copy a safe flag over every unused line of code
    If B<18 $AD $AF
Sparr
źródło
Move 0przesuwa się na północ, a nie do przodu.
MegaTom,
@MegaTom aha, dzięki. Tęsknie za tym.
Sparr