Kółko i Krzyżyk na 5

Force

W tym gotowcu chcę zaprezentować program w którym można grać w kółko i krzyżyk na pięć z czlowiekiem, Oprócz tego do programu dołączony jest unit z sztuczną inteligencją, z którą można zagrać. Trzecia opcja w grze pozwala na oglądanie pojedynku między dwoma komputerami. Jak narazie zawsze, któryś komputer wygra. Oprócz moduły inteligencji jest jeszcze moduł mapy, z którego korzysta sztuczna inteligencja.

user image

Moduł mapy

Tak wygląda klasa obsługująca mapę

TXOMap = class
  public
      Map : array[0..19,0..19] of byte;
      LastMove : TMove;
      constructor Create();
      destructor Destroy(); override;
      function CanPut(X,Y : byte):boolean;
      function Put(X,Y : byte):boolean;
      function WinnerExists():TWinner;
    private
      Token : byte;
      function Sum(X1,Y1,X2,Y2 : byte):byte;
  end;

Zmienna ?Map? zawiera informacje na temat postawionych znaków w każdą komórkę planszy. 0 ? oznacza pustą kratkę, 1 ? krzyżyk, a 6 kółko. Jest to najwygodniejszy sposób oznaczania, bo skoro w pięciu polach w linii mają być takie same znaki, to zwycięzca jest wtedy, gdy w pięciu kolejnych polach suma wynosi 5 (same krzyżyki), lub 30 (same kółka). Jest to także wygodne oznaczenie, gdy programuje się ruchy komputera. Dla przykładu: gdy komputer jest kółkiem i w pięciu polach w linii suma wynosi 24, to on wie że ma cztery znaki i ma postawić piąty (innej kombinacji dla sumy 24 nie ma).

Zmienna ?LastMove? jest rekordem zawierającym o ostatnim ruchu, czyli X, Y ? położenie i Token czyli znak jaki postawiono.

Zmienna ?Token? określa znak jaki ma być postawiony w najbliższym ruchu (Jeśli właśnie postawiono kółko, to wynosi ona TokenX (1) )

Funkcja ?CanPut(X,Y : byte):boolean" sprawdza czy pole o współrzędnych X,Y jest niezajęte, czyli ma wartość 0.

Funkcja ?Put(X,Y : byte):boolean? stawia a pole o współrzędnych X, Y znak jaki przechowuje zmienna ?Token?, zwraca wartość False, jeśli się jej nie udało

Funkcja ?WinnerExists():TWinner? sprawdza czy istnieje zwycięzca. Zwraca ona wynik w postaci:

TWinner = record
    X1,Y1 : byte;
    X2,Y2 : byte;
    Token : byte;
end;

Jeżeli Token = 0 wtedy nie ma zwycięzcy. W przeciwnym razi Token określa znak zwycięzcy, a zmienne X1, Y1, X2, Y2 wskazują początek i koniec pięciu tych samych znaków.

Moduł inteligencji

Na początek omówię jak komputer ma stawiać kółko / krzyżyk tak aby wyglądało, że wie co robi.

Inicjalizując klasę inteligencji, należ podać wskaźnik na mapę, oraz znak jaki ma komputer.
UWAGA Znak określa kim komputer się czuje (czy kółkiem, czy krzyżykiem), a nie jaki znak stawia. Znak jaki komputer stawia zależy od klasy mapy

Klasa TXOAI posiada zmienną TempMap, która jest tablicą 20x20. Zawiera ona priorytety, dla każdego pola, które komputer oblicza przy każdym ruchu. Po obliczeniu priorytetów, szuka on pola z najwyższym priorytetem. Jeśli pola mają taki sam priorytet to losuje, które ma wybrać. Jeśli okaże się, że najwyższy priorytet wynosi 0, to losuje położenie w środku planszy.

Komputer przy ustalaniu priorytetów korzysta z funkcji

function TXOAI.Sum(X1,Y1,X2,Y2 : byte):byte;
var
	i : byte;
begin
	Result := 0;
  if X1 = X2 then  // Pionowo
  	For i:=Y1 To Y2 Do
      Inc(Result,Map.Map[X1,i])
  else
  if Y1 = Y2 then  // Poziomo
  	For i:=X1 To X2 Do
      Inc(Result,Map.Map[i,Y1])
  else
  if (X1 < X2) and (Y1 < Y2) then // Ukos z lewgo górnego rogu
  	For i:= X1 To X2 Do
    	Inc(Result,Map.Map[i,Y1+i-X1])
  else
  if (X1 < X2) and (Y1 > Y2) then  // Ukos z lewego dolnego rogu
  	For i:= X1 To X2 Do
    	Inc(Result,Map.Map[i,Y1+X1-i]);
end;

Sumuje ona wartości z mapy, z linii (X1,Y1) do (X2,Y2). Funkcja jest prywatna, wiec nie sprawdza poprawności wpisanych położeń, zakładając, że parametry są poprawne. W zależności od parametrów przeszukuje, linie w poziomie, w pionie, lub którąś z przekątnych.

Wszystkie procedury sztucznej inteligencji, wywoływane są w pętli
For i := 0 To 19 Do
For j := 0 To 19 Do

Deklaracja pierwszej wywołanej procedury wygląda następująco:
MoveCompEmpty(x,y : byte)

Jej zadaniem jest podwyższenie wszystkim polom wokół pola X,Y priorytetu o 1. Dzięki temu komputer nie będzie stawiał znaku na już zajętym polu (które ma priorytet 0) i będzie stawiał swoje znaki blisko rozgrywki.

W następnych krokach wywoływane są procedury, które wyszukują schematów a polom, które należą do schematu, a są puste podwyższają priorytet zgodnie z podanymi poniżej liczbami (oczywiście można je zmieniać, zastąpić stałymi, itp.):

Dwójka komputera: 4
Dwójka przeciwnika: 1
Trójka komputera: 60
Trójka przeciwnika: 15
Czwórka komputera: 2000
Czwórka przeciwnika: 400

Schematy są wyszukiwane od pola i,j (zmienne z pętli) do pola i+4,j (poziomo w prawo); i,j+4 (pionowo w dół), i+4,j+4 (na ukos w prawo dół); i+4,j-4 (na ukos w prawo góra); Oczywiście procedury sprawdzają czy nie wychodzą poza obrzeże planszy (np. pole 24,25 czy 17,21).

Do poszukiwania schematów służy funkcja TXOAI.Sum(X1,Y1,X2,Y2 : byte):byte
Komputer reaguje tylko na niektóre wyniki:

2*Token ? Są tylko dwa pola komputera w pięcioznakowej linii. Uzupełnienie da trójkę

2*Token2 ? Są tylko dwa pola przeciwnika w pięcioznakowej linii. Uzupełnienie uniemożliwi stworzenie przez przeciwnika trójki

3*Token ? Są tylko trzy pola komputera w pięcioznakowej linii. Uzupełnienie da czwórkę, a ona daje szanse na zwycięstwo

3*Token2 ? Są tylko trzy pola przeciwnika w pięcioznakowej linii. Uzupełnienie zablokuje możliwość powstania czwórki u przeciwnika

4*Token ? Są tylko cztery pola komputera w pięcioznakowej linii. Uzupełnienie da zwycięstwo

4*Token2 ? Są tylko cztery pola przeciwnika w pięcioznakowej linii. Uzupełnienie może zażegnać zwycięstwu przez gracza

Na koniec trzeba jeszcze wyjaśnić co to jest Token i Token2.
Token określa znak komputera, a Token2 znak gracza. 1 (TokenX) ? krzyżyk, 6 (TokenY) - kółko

Aby nie zajmować serwera, tutaj jest link już do skompilowanej wersji:
http://www.force.republika.pl/KiK.exe

14 komentarzy

TomRiddlem da sie wygrac bez problemu. Wygrałem za czwartym razem :)

Ej, a czy ty w ogóle sprawdzałeś czy z tą sztuczną inteligencją da się wygrać?

jak ktoś ma kod tego programu w delphi to bardzo bym prosil na morozof@tlen.pl

prośba do autora: zamieść źródło na 4programmers lub podaj do niego link bo tacy jak ja i ten poniżej nie wiedzą co do czego i chcieli by się czegoś nauczyć!

fajny programik, szkoda ze plikow wykonawczych nie ma dolaczonych, bo mi to nie idzie... dopiero zaczynam, chcialbym zobaczyc jak calosc jest napisana... nie mozna by wkleic calego kodu programu?

Co to za interes, aby porgram nie dało się pokonać? Kto gra aby przegrać?

Jednak nie taki dobry program Koleżanka grała 6 razy 4x wygrała
Grałem 7 razy 3x przegrałem 4 wygrałem
profesor od informatyki grał 2x i 2x wygrał {wskaźnik wśród profesorów 100% wygranych}
Kumple grali w sumie 21razy 10 razy przegrali
doszliśmy do wniosku takiego program nie przelicza wyżej niż 3 posunięcia

Piotrekdp, dobry pomysł. Jakbyś przysłał, to bym zrobił partię międzu oboma komputerami, znaczy grając w kółko Twojego kolegi stawiałbym znaki tam gdzie mój program proponuje. Może by remis wyszedł

Od razu lepiej ;)

Chyba zrozumiałem o co wam chodzi. Już dodałem "co i do czego", a kod przeniosłem na ten serwer. Mam nadzieję, że już jest dobrze, bo z pisania "co i do czego" nie jestem najlepszy.

A odnośnie ameby to chyba tej nazwy używaj biolodzy

Ode mnie jeden. Równie dobrze mozna by to do kodów źródłowych wrzucić, a nie jako artykuł.

Nie no, nie wystarczy wkleic link do kodu ktory jeszcze znajduje sie na innym serwere :/ Wlasnie chodzi by w artykule opisac co i do czego, dlaczego taki kod a nie inny, jak to dziala... :/

Ode mnie 1. W niedlugim czasie jezeli nie zostanie naprawione - zostanie to usuniete.

ameba? to raczej taki pierwotniak :]

Kółko i Krzyżyk na 5 nazywa się ameba.
Ciekawe...