Bot do gry w statki

Cześć mam do napisania bota, który będzie grał w statki, przy czym zależy mi, aby bot wykonał jak najmniej strzałów. Przeczytałem fajny artykuł opierający się na prawdopodobieństwie znalezienia statku w danym rejonie (tutaj link dla zainteresowanych :) https://www.datagenetics.com/blog/december32011/index.html , jednakże zastanawiam się czy nie lepiej starać się zatopić coraz to mniejsze statki zaczynając od największego? Mam na myśli, aby strzelać co 5 pól wtedy na pewno trafimy w jednostkę o 5 polach. I potem po kolei strzelać co 4 , 3 ... aż uda zatopić mi się wszystkie . Co o tym sądzicie ? Może macie jakieś lepsze pomysły?

Myślę, że do momentu znalezienia statku strzelanie "na oślep" ( byle bez powtórzeń ) będzie równie skuteczne. Po zatopieniu statku wykluczyć pola otaczające go, w których nie może znaleźć się inny statek ( bo nie mogą się stykać ) i dalej walić "na oślep".
Jak to ogarniesz wtedy można kombinować coś ze strzelaniem co 5 czy co 2 i ewentualnym wykluczaniem obszarów gdzie nie ma prawa być dużych statków ( zakładając, że małe są wybite ).
Przypuszczam, ze równie dobrze można do tego zaciągnąć sieci neuronowe.

Swoją drogą fajny artykuł.

Są rożne wersje statków, więc może zacznij od opisania, o której wersji mówisz.
Różnice są:

• kształt i wielkość statków
• reguły rozmieszania - czy i jak mogą się stykać: dowolnie, rogami, wcale.
• jak się strzela: pojedyncze strzały, salwy (po trzy).
• czy istnieją dodatkowe funkcje (kiedyś grałem w wersję z sonarem).

Mam na myśli klasyczną 10 x 10 , nie mogą sie stykać, strzela się po raz i nie ma żadnych funkcji
I mam pytanie czy algorytm, który szedł by od lewej do prawej po polach tablicy i gdyby trafił to starałby się zatopić statek byłby skuteczny? Czy tak jak było pisane wyżej najlepszym sposobem jest po prstu strzelanie z obliczaniem prawdopodobieństwa na trafienie?

Jakoś by działał. Oczywiste ulepszenia to strzelanie w odstępach, co zwiększa szansę na trafienie w jakiś statek (jednomasztowców jest zazwyczaj dosyć mały odsetek całości) i odrzucanie przestrzeni zbyt małych, by się tam zmieścił jakiś okręt.

Może Ci się przyda. Żeby był "idealny" brakuje mu jednej rzeczy: sprawdzania czy któryś ze statków już jest zatopiony. Pozwoli to, dla przykładu, przerwać ostrzał statku, jeśli już zatopiłeś trzy maszty, a czteromasztowiec był zatopiony wcześniej. Kod brzydki i do refaktoryzacji, ale działa :)

@Injectable()
export class AiService {
  constructor(private board: BoardService) {}

  public getFireCoordinates(board: BoardCell[][]): Coordinates {
    let hits: BoardCell[] = this.board.getCurrentHits(board); // hit cells
    let missed: BoardCell[] = this.board.getCurrentMissed(board); //missed cells
    let forbidden: BoardCell[] = []; //can not shoot there
    let targets: BoardCell[] = []; //potential targets
    let isRandomCoordinateForbidden: boolean = true;
    let randomCoordinates: Coordinates = {
      row: -1,
      col: -1,
    } as Coordinates;
    forbidden.push.apply(forbidden, this.board.getCornerCells(hits));
    forbidden.push.apply(forbidden, missed);
    forbidden.push.apply(forbidden, hits);
    targets = this.board.getPotentialTargets(forbidden, hits);
    //todo: count hits in line and remove ships from list
    if (targets.length > 0) {
//todo: DRY
      while (isRandomCoordinateForbidden) {
        randomCoordinates = targets[Math.floor(Math.random() * targets.length)];
        if (!this.checkIfRandomIsForbidden(forbidden, randomCoordinates)) {
          isRandomCoordinateForbidden = false;
        }
      }
      return {
        row: randomCoordinates.row,
        col: randomCoordinates.col,
      } as Coordinates;
    } else {
//todo: DRY
      while (isRandomCoordinateForbidden) {
        randomCoordinates = this.getRandomCoordinates();
        if (!this.checkIfRandomIsForbidden(forbidden, randomCoordinates)) {
          isRandomCoordinateForbidden = false;
        }
      }

      return randomCoordinates;
    }
  }

  private checkIfRandomIsForbidden(
    cells: BoardCell[],
    coord: Coordinates
  ): boolean {
    for (let i = 0; i < cells.length; i++) {
      if (cells[i].row == coord.row && cells[i].col == coord.col) {
        return true;
      }
    }

    return false;
  }

  private getRandomCoordinates(): Coordinates {
    return {
      row: Math.floor(Math.random() * 10),
      col: Math.floor(Math.random() * 10),
    } as Coordinates;
  }
}

EDIT: algorytm dla klasycznej wersji gry w statki.

Grałem w taką wersję:

Jeżeli założyć, że statki nie mogą być wygięte ani się dotykać (nawet rogami), to na pustej planszy łatwiej trafić statek większy niż 1-masztowiec strzelając po przekątnej, jak w szachownicy. W tym filmiku można zaobserwować, jak bot "wybiera" miejsce strzału i wydaje się, że taką strategię przyjmuje.

W filmiku jak bot gra, to strzał spada z góry na planszę, a jak gracz gra, to obserwuje ostrzeliwany statek przez celownik (tylko taka animacja, nie ma żadnego celowania przez celownik).