tło

Hex to abstrakcyjna gra strategiczna dla dwóch graczy, rozgrywana na K×Krombie sześciokątnych płytek. Dwie przeciwne strony rombu są w kolorze białym, a pozostałe dwie czarne, a dwaj gracze, czarno-biały, umieszczają kolejno swój symbol koloru na niezajętym kafelku. Gracz, który jako pierwszy zdoła zbudować ścieżkę między przeciwnymi stronami swojego koloru, jest zwycięzcą. Wiadomo, że gra nie może zakończyć się remisem i że pierwszy gracz ma strategię wygraną niezależnie od wielkości planszy (szczegóły na stronie Wikipedii).

Zadanie

W tym wyzwaniu ustalamy rozmiar planszy na K = 4i reprezentujemy planszę jako następującą siatkę. Grube linie oznaczają sąsiadujące płytki.

Twoim zadaniem jest opracowanie zwycięskiej strategii dla pierwszego gracza, którą możesz wybrać jako czarny lub biały. Oznacza to, że niezależnie od tego, jakie legalne ruchy wykona przeciwny gracz, twoja gra musi zakończyć się zwycięstwem. Twój wkład to pozycja w grze (układ żetonów na planszy), a twój wynik to legalny ruch, w formacie określonym poniżej. Jeśli chcesz sam znaleźć zwycięską strategię, nie czytaj tego spoilera:

Zarys jednej możliwej strategii wygranej, przy założeniu, że biały jest pierwszy. Najpierw wybierz 5. Następnie, jeśli masz ścieżkę od 5 do dolnego rzędu LUB czarny wybiera 0 lub 1 w dowolnym punkcie, odpowiedz, wybierając dowolną z 0 lub 1, która jest pusta. Jeśli czarny wybierze 9 lub 13, wybierz 10, a następnie którykolwiek z 14 lub 15 jest wolny. Jeśli czarny nie wybierze 9, 13 lub 14, wybierz 9, a następnie którykolwiek z 13 lub 14 jest wolny. Jeśli czarny wybierze 14, odpowiedz, wybierając 15. Następnie wybierz 10, jeśli jest wolny; jeśli czarny wybierze 10, odpowiedz 11. Jeśli czarny wybierze 6, odpowiedz 7, a następnie dowolna z 2 lub 3 jest pusta. Jeśli czarny nie wybierze 6, wybierz go, aby uzyskać ścieżkę od 5 do dolnego rzędu.

Wejście i wyjście

Twój wkład to ciąg 16 znaków WBE, które oznaczają białe, czarne i puste. Reprezentują płytki planszy, jak wyliczono powyżej. Możesz wybrać metodę wprowadzania (która określa również metodę wyjściową) z następujących czynności:

1. Wejście ze STDIN, wyjście do STDOUT.
2. Wprowadź jako jeden argument wiersza poleceń, wyślij do STDOUT.
3. Wprowadź jako 16 jednoznakowych argumentów wiersza poleceń, wyślij do STDOUT.
4. Dane wejściowe jako argument funkcji o nazwie, dane wyjściowe jako wartość zwracana.

Twój wynik reprezentuje płytkę, na której umieszczasz następny żeton, ponieważ twoja kolej na ruch. Możesz wybrać jeden z następujących formatów wyjściowych:

1. Indeks zerowy (jak na powyższym obrazku).
2. Indeks oparty na jednym.
3. Łańcuch wejściowy z jednym Ezamienionym na którykolwiek Wlub Bwybrany przez gracza.

Zasady

Twoja strategia musi być deterministyczna. Nie musisz poprawnie obsługiwać pozycji w grze, które są nieosiągalne z pustej planszy za pomocą strategii, lub pozycji, które już wygrywają dla któregoś z graczy, i możesz się na nich upaść. I odwrotnie, na planszach, które są osiągalne dzięki twojej strategii, musisz zwrócić legalny ruch.

To jest golf golfowy, więc wygrywa najmniejsza liczba bajtów. Standardowe luki są niedozwolone.

Testowanie

Napisałem kontroler Python 3 do sprawdzania poprawności wpisów, ponieważ byłoby to bardzo żmudne robić ręcznie. Możesz go znaleźć tutaj . Obsługuje pierwsze trzy formaty wejściowe i funkcje Pythona 3 (funkcje w innych językach muszą być opakowane w programy), wszystkie trzy formaty wyjściowe i oba odtwarzacze. Jeśli strategia nie wygrywa, wyświetli znalezioną przegraną grę, abyś mógł ulepszyć swój program.

Cudowny, 973b

To naiwne wdrożenie wskazanej strategii w pytaniu. Oczekuje, że tablica zostanie podana jako 16 parametrów linii poleceń / płyty głównej, hex.mbl B W E E E W E E E B E E E E E Ei wyświetli zindeksowaną pozycję następnego ruchu bieli.

00 }1 }0
&G B? W!
&0 &G &G
!!
00 }0 }1
&H B? W!
&1 &H &H
!!
.. }D .. }9 }9 }D }E }A }D }9 }A .. }E }F }5
}9 B! }E E? W? E? .. E? B? B? W? .. E? .. E?
B! ?0 B! &M &N &O E? &I \\ .. &J .. &K E? &5
?0 ++ ?0 &9 .. &D &P &A &I /\ &J .. &E &L !!
++ .. ++ !! .. !! &E !! \/ &L /\ &K !! &F
\\ .. // .. .. .. !! .. .. \/ .. \/ .. !!
.. =3 \/
&M /\ &N
\/ &O /\ &P
}0 }1 }6 .. }6 .. }7 &7 }2 }3 }A }A }B }E }F
..
..
..
..
..
..
..
..
..
.. .. .. .. .. .. .. .. .. .. .. .. .. B? W!
.. .. .. .. .. .. .. .. .. .. .. .. .. &Q &Q
.. .. .. .. B? .. E? W? E? .. E? B? E? &F \/
.. .. .. &S /\ &T &S &T &U E? &A &R &R !!
.. .. .. &7 .. .. \/ .. &2 &V !! &B \/
.. .. .. !! .. .. &U /\ &V &3 .. !!
.. .. .. .. .. .. .. .. .. !!
.. .. ..
.. .. E?
E? .. &6
&X E? !!
!! &Y
.. !!
}4 }8 }C
\/ \/ \/
30 30 31 31 32 33 35 36 37 39 31 30 31 31 31 33 31 34 31 35
&0 &X &1 &Y &2 &3 &5 &6 &7 &9 &A &A &B &B &D &D &E &E &F &F
:W?
}0
^4
=1
{0
:B?
}0
^0
=0
{0
:E?
}0
^1
=0
{0
:W!
}0
^4
=0
{0
:B!
}0
^0
>0
{0

Wydaje mi się, że mogę z tego zrobić około 200 znaków dzięki lepszemu rozgałęzieniu i wyeliminowaniu ponownego użycia kodu.

Python 3, 100b

b=input()
i=b.find('B')
if b[i]in'BW'and'E'in b:i-=1+(b[i-1]is'W')*4
print((b[:i]+'B'+b[i+1:])[:16])

• Gracz: CZARNY
• Metoda: STDIN / STDOUT, MODIFIED_BOARD

Strategia polega na tym, aby najpierw wyszukać Bna tablicy. Jeśli nie ma, zwraca to -1, co w pythonie jest takie samo jak last index. Tak więc na pustej planszy będzie mój pierwszy indeks index=-1, od którego zacznę się ruszać.

Jeśli pole po mojej lewej stronie ( index-1) jest wolne, mój następny ruch tam idzie. Jeśli zostanie zrobione, idę w górę w lewo. Nigdy nie muszę się wspinać: jeśli to zrobię, stracę tempo i przegram grę.

Na pełnej planszy ( Enigdzie nie ma ) nie wykonuję ruchu.

Na początku printwydaje się to trochę dziwne: muszę zbudować nową planszę (co robię poprzez krojenie), ale potem muszę wyciąć 16 znaków. Jest to relikt, ponieważ pracuję z ujemnymi indeksami i b[i+1:]dlatego zwrócę planszę z dziurami i resztę, której oczekuję, dlatego ważne jest, aby odciąć resztę. Innym sposobem byłaby praca z dodatnimi indeksami, np. Przyjmowanie (b.find('B')+16)%16, ale (+16)%16jest to o jeden bajt więcej niż ()[:16].

Nie golfowany:

board = input()
index = board.find('B')
if board[index] in 'BW' and 'E' in board:
    index -= 1 + (board[index-1] is 'W') * 4
print((board[:index] + 'B' + board[index+1:])[:16])

Test

Podczas uruchamiania zestawu testów kontrolera szesnastkowego napotkałem dziwne zachowanie:

OUT: EEEEEEEEEEEEEEEB
OUT: WEEEEEEEEEEEEEBB
OUT: WWEEEEEEEEEEEBBB
OUT: WWWEEEEEEEEEBBBB
OUT: WWWWEEEEEEEBBBBB
OUT: WWWWWEEEEEBBBBBB
OUT: WWWWWWEEEBBBBBBB
OUT: WWWWWWWEBBBBBBBB
OUT: WWWWWWWWBBBBBBBB

Incorrect response 'WWWWWWWWBBBBBBBB' to message 'WWWWWWWWBBBBBBBB'.

Myślę, że albo powinienem wygrać po czwartej turze, albo odpowiedź z tą samą tablicą na pełną tablicę powinna być poprawną odpowiedzią. Nie jestem pewien, co się tam dzieje, nie zanurkowałem głębiej - chciałem tylko sprawdzić, czy dostałem wszystkie „specjalne” przypadki. Ale ponieważ nie muszę ukrywać sytuacji, w których ktoś zaczyna na około 4 przestrzeni, to i tak nie ma znaczenia.

85b

Jeśli jednak pozwolę sobie nie sprawdzać pełnej płyty (tzn. Pomijając to 'E' in b, mogę dodatkowo uprościć kod, aby używał tylko 85 bajtów:

b=input();i=b.find('B')
if i!=-1:i-=1+(b[i-1]is'W')*4
print((b[:i]+'B'+b[i+1:])[:16])

Doprowadzi to jednak do następujących sytuacji:

Incorrect response 'WWWBWWWWBBBBBBBB' to message 'WWWWWWWWBBBBBBBB'.

To może, ale nie musi być policzone, a ponieważ uznałem, że to nie był prawidłowy ruch, postanowiłem wybrać dłuższą, ale bardziej poprawną odpowiedź.