Warcaby - tworzenie AI

0

Witam,
mam na zajęcia stworzyć grę warcaby w C.Gra ma umożliwić zabawę z komputerem, który nie będzie wykonywał losowych ruchów (generowanych przez rand), a jakieś konkretne.
Problemem jest to, że nie wiem jak do tego podejść. Czytałem o różnych algorytmach przeszukiwania drzewa gry. Ale nie wiem jak takie drzewo gry się generuje (chociaż by dla 2 ruchów do przodu).

Proszę o jakieś rady =D

1

to jeszcze może być przydatne:

http://library.msri.org/books/Book29/files/schaeffer.pdf

Zobacz stronę (7) 125 - ile jest możliwych ruchów - ja bym zrobił drzewo na max 3-4 ruchy do przodu, chyba że masz dużo pamięci.

Film na jołtjubie z min-max AI na przykładzie warcabów:

0

Dzięki Wybitny Lew za szybką odpowiedz ;-).

0

A czy ktoś miał by takie proste drzewo do 2 ruchów napisane lub napisał by?

1

Jak napiszesz dla jednej tury (ruchu) to nie będziesz miał problemów dla N ruchów ;)

To jest prosty algorytm, dobrze opisany w Sieci.

Ale jak byś się poddał i zupełnie nie miał pomysłu to tu masz gotowca w C++:

https://github.com/MarkJr94/checkers

0

Biały Pomidor dzięki

1

Na wiki jest pseudokod do alfa-beta cięć, który jest ulepszeniem algorytmu min-maks - dzięki "odcinaniu" nieistotnych gałęzi drzewa można rozpatrzyć więcej kroków do przodu, np. 8 czy 9. https://en.wikipedia.org/wiki/Alpha%E2%80%93beta_pruning

0

Problemem nie jest przechodzenie drzewa gry (może się pojawić potem, ale jest dużo przykładów), a stworzenie drzewa gry, którego nie potrafię zrobić.

1

Drzewo gry składa się z węzłów, a każdy węzeł reprezentuje konkretną sytuację na planszy. Każdy węzeł może mieć też wiele dzieci, i ma jednego rodzica.

Zatem węzeł może wyglądać tak:

class CTreeNode
{
    CBoardState         m_board; // reprezentacja sytuacji na planszy
    CTreeNode*          m_pParent; // wskaźnik na rodzica
    QList <CTreeNode*>  m_children; // lista wskaźników na dzieci

// mogą się też przydać...

    quint8              m_ucLevel; // poziom zagnieżdżenia w drzewie
    qint32              m_uiValue; // ocena planszy wg jakiegoś algorytmu
};

Samo drzewo potrzebuje tylko wskaźnika na root drzewa:

class CTree
{
    CTreeNode *m_root;
};

Po stworzeniu pustego drzewa musisz dodać węzły-dzieci do roota. To będą wszystkie możliwe plansze po wykonaniu pierwszego ruchu. Czyli najpierw szukasz wszystkich możliwych do wykonania ruchów i zapisujesz je. Potem dla każdego ruchu tworzysz nową planszę (CBoardState) i wykonujesz na niej odpowiedni ruch. Każda z otrzymanych planszy tworzy nowy węzeł drzewa gry, dzieci roota.

Potem na każdym z dzieci wykonujesz to samo, szukasz możliwych ruchów, i wykonujesz je na osobnych planszach. Tak powstają kolejne dzieci i poziomy drzewa.
Mam nadzieję że mój opis trochę pomógł:)

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0