Kółko i Krzyżyk — m,n,k-game z SI (Minimax + Alpha-Beta)

Implementacja uogólnionej wersji gry Kółko i Krzyżyk (tzw. m,n,k-game) w C++17 z graficznym interfejsem SFML 3 oraz sztuczną inteligencją opartą na algorytmie Minimax z cięciami alfa-beta i funkcją heurystyczną.

Projekt zrealizowany na przedmiot Projektowanie i Analiza Algorytmów (Politechnika Wrocławska, Informatyczne Systemy Automatyki).

Funkcjonalności

• Konfigurowalna plansza — dowolny rozmiar $n \times n$ (od 3×3 do 15×15) oraz dowolna liczba znaków $k$ wymaganych do wygranej
• Dwa tryby gry — Gracz vs Gracz oraz Gracz vs SI
• Sztuczna inteligencja:
  • algorytm Minimax z cięciami alfa-beta
  • funkcja heurystyczna oceniająca pozycję na dużych planszach (analiza sekwencji w 4 kierunkach)
  • natychmiastowe wykrywanie wygranych i blokowanie zagrożeń przeciwnika
  • automatyczny dobór głębokości przeszukiwania i strategii generowania ruchów w zależności od rozmiaru planszy
  • obliczenia SI w osobnym wątku (std::async) — interfejs nie zamraża się podczas "myślenia" AI
• Graficzny interfejs (SFML 3):
  • menu konfiguracyjne (rozmiar planszy, liczba znaków do wygranej, tryb gry, wybór strony)
  • panel boczny z informacją o turze/wyniku
  • przycisk restartu gry

Stos technologiczny

• C++17
• SFML 3 — okno, grafika, obsługa zdarzeń
• Visual Studio (projekt rozwijany pod Windows, kompilator MSVC)

Struktura projektu

.
├── main.cpp                  punkt wejścia, inicjalizacja menu i okna gry
├── MenuWindow.h / .cpp        ekran konfiguracyjny gry
└── game/
    ├── Types.h                podstawowe typy: Cell, GameResult, Move, GameConfig
    ├── Board.h / .cpp          reprezentacja planszy
    ├── Rules.h / .cpp          sprawdzanie warunków wygranej/remisu
    ├── MoveGenerator.h / .cpp  generowanie ruchów (wszystkie pola / sąsiedztwo)
    ├── GameState.h / .cpp      stan gry, historia ruchów, cofanie ruchów
    ├── AI.h / .cpp             Minimax, alfa-beta, heurystyka
    └── GameWindow.h / .cpp     pętla gry, rysowanie planszy i panelu, obsługa kliknięć

Architektura

Projekt rozdziela logikę gry od warstwy graficznej:

• Logika gry (Board, Rules, GameState, MoveGenerator, AI) — czysty C++17 bez żadnych zależności zewnętrznych. Można testować i uruchamiać niezależnie od SFML (np. w konsoli).
• Warstwa graficzna (GameWindow, MenuWindow) — korzysta z logiki gry wyłącznie przez publiczne API (GameState, AI), nie ingerując w jej wewnętrzną implementację.

Sztuczna inteligencja

Minimax + alfa-beta

SI przeszukuje drzewo możliwych stanów gry, zakładając optymalną grę obu stron. Cięcia alfa-beta eliminują gałęzie drzewa niemające wpływu na ostateczną decyzję, redukując złożoność z $O(b^d)$ do $O(b^{d/2})$ w najlepszym przypadku.

Heurystyka dla dużych plansz

Na planszach większych niż 5×5 pełne przeszukanie drzewa do końca gry jest niewykonalne obliczeniowo. Gdy Minimax osiągnie limit głębokości, pozycja oceniana jest heurystycznie na podstawie długości i "otwartości" sekwencji obu graczy w czterech kierunkach (poziomo, pionowo, dwa skosy).

Generowanie kandydatów

Dla małych plansz ($n \leq 5$) AI rozważa wszystkie puste pola. Dla większych plansz ograniczone jest to do pól w sąsiedztwie już postawionych znaków, co drastycznie redukuje przestrzeń przeszukiwań i czas obliczeń.

Wymagania

• Visual Studio 2022 (lub kompatybilny kompilator wspierający C++17)
• SFML 3.x (instalacja przez NuGet lub ręczna konfiguracja ścieżek w ustawieniach projektu)

Budowanie i uruchomienie

1. Sklonuj repozytorium
2. Zainstaluj SFML 3 (przez NuGet: Manage NuGet Packages → wyszukaj SFML)
3. Skopiuj plik czcionki (np. arial.ttf) do folderu assets/ w katalogu projektu oraz w katalogu wynikowym (x64/Debug/)
4. Zbuduj i uruchom projekt w Visual Studio

Autor

github.com/Czarko-exe — Informatyczne Systemy Automatyki, Politechnika Wrocławska