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
Na wikipedziach masz tze. min-max:
https://en.wikipedia.org/wiki/Minimax
Dodatkowo na SE:
http://gamedev.stackexchange.com/questions/16135/how-to-implement-a-i-for-checkers-draughts
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:
Dzięki Wybitny Lew za szybką odpowiedz ;-).
A czy ktoś miał by takie proste drzewo do 2 ruchów napisane lub napisał by?
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++:
Biały Pomidor dzięki
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
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ć.
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ł:)
katecpp dzięki!