Muszę napisać grę z komputerem w skoczki. Są 2 sposoby ruchu:

  1. Przesunięcie - o 1 pole w dowolnym kierunku - po czym kontynuuje kolejny gracz
  2. Skok - przez dowolne piony, jeśli za nimi jest puste pole - po czym kontynuuje kolejny gracz
  3. Wieloskok - można wykonać więcej skoków jednocześnie, jeśli to możliwe

Cały algorytm utrudniają wieloskoki, a więc są potrzebne dodatkowe struktury danych.

Drzewko algorytmu MinMax musi przechować wykonany ruch (czyli przesunięcie, skok lub wieloskok). Co oprócz tego? Trzeba obliczyć, co się stanie np. po 3 kolejkach. Czy kopiować całą tablicę (int[10][10]) dla każdego wierzchołka drzewa (czyli dla każdego pionu na każdej głębokości), aby wykonywać na niej obliczenia, czy istnieją oszczędniejsze metody dla pamięci i procesora?

Wyobraźcie sobie, że szukacie wszystkich dozwolonych ruchów. Mając tylko tablicę int[10][10] z numerami graczy pozostaje przejechać ją 2 pętlami, sprawdzić, czy pole należy do gracza, a następnie obliczyć wszystkie możliwe ruchy.

Potrzebne są struktury danych, aby przechować:

  1. Listę dozwolonych ruchów dla danego pola (x,y)
  2. Historię wszystkich ruchów
  3. Historię bieżącego ruchu - potrzebna przy wieloskokach

Piszę w C++. Jakie struktury danych proponujecie do tych celów? Jakie obiekty utworzyć?

Kolejna rzecz - funkcja oceniająca. Jakie przyjąć kryteria? Na pewno trzeba zbadać otoczenie pionka i odległość od celu. Wydaje mi się, że to wszystko (szukanie pionków, dozwolonych ruchów, drzewa, ocena ruchu, sprawdzenie, czy gracz wygrał) zajmie za dużo czasu procesora. Nie piszę tego na wątkach (ach ta synchronizacja), więc chcę ominąć zbędne czynności.

O czym należy pamiętać przy implementacji MinMax?