Algorytmy grające w warcaby - gdzie szukać, jaką taktyke obrać?

	B O A R D
	» Board » Zadaj pytanie » Archiwum » Szukaj » Stylizacja

M E N U

» Nowości

» Archiwum

» Recenzje / Testy

» Board

» Rejestracja

Szukaj @ TwojePC

	OBECNI NA TPC
	» yanix 02:26 » PaKu 02:20 » metacom 02:18 » xpx 02:17 » Shark20 02:14 » abes99 01:30 » luckyluc 01:30 » Chrisu 01:26 » PiotrexP 01:18 » Martens 00:57 » Wolf 00:44 » Visar 00:43 » CiAsTeK 00:39 » bmiluch 00:38 » Zic 00:36 » rulezDC 00:36 » Demo 00:15 » rarek 00:09 » buddookan 00:03 » bagi_glog 00:02 Dzisiaj przeczytano 41121 postów, wczoraj 25974 Szybkie ładowanie jest: włączone.

ccc

A R C H I W A L N A W I A D O M O Ś Ć

Algorytmy grające w warcaby - gdzie szukać, jaką taktyke obrać? , zozol 3/10/04 14:53
Mam do napisania programik grający w warcaby i zastanawiam sie jaka powinna byc zasada dzialania algorytmu aby po pierwsze byl skuteczny, a po drugie dzialal w miare szybko. (przeszukiwanie calej przestrzeni rozwiazan jest praktycznie niemozliwe, wiec odpada)

Jak sie do tego zabrac i gdzie ewentualnie szukac informacji i sposobow rozwiazywnia takich problemow?

s.w. , atay 3/10/04 14:56
tez jestem ciekaw :)
_- Atay -_
A standardowe podejście? , pachura 3/10/04 15:09
Przeszukujesz całą przestrzeń rozwiązań, ale do pewnej głębokości - tzn. np. 5 ruchów w przód. Oceniasz która z wynikowych sytuacji będzie dla Ciebie najlepsza (lub lepiej - najgorsza dla przeciwnika) i tą drogę wybierasz. Dodatkowo, jeśli dane odgałęzienie wygląda już bardzo źle (nie może być lepsze niż rozwiązanie znalezione do tej pory), to nie zagłębiasz się w nie.

Podstawą jest też opracowanie sensownej struktury danych, która umożliwi szybkie operacje na pionkach. Żebyś np. nie musiał za każdym razem przeglądać całej szachownicy żeby znaleźć swoje pionki. Etc. etc. ...

Oczywiście można - jak w szachach - stworzyć bazę końcówek - pozycji dla których istnieje pewne zwycięstwo/remis - i ją wykorzystywać.
1. A nie ma czegoś "sprytniejszego" ? , zozol 3/10/04 18:03
  Wolałbym coś w stylu algorytmu genetycznego, sieci neuronowej itp. - generalnie coś, co możnaby wyszkolić wcześniej, a potem tylko zastosować do wybrania kolejnego ruchu.
  Tylko czy takie algorytmy można tu w ogóle wykorzystać?
  1. Czemu nie... ale... , pachura 3/10/04 18:34
    To co Ci skrótowo opisałem to algorytm minmax z obcinaniem alfa-beta. Jest prosty i zrozumiały, można łatwo dokładać do niego różne heurystyczne ulepszacze jak np. bazy końcówek partii...
    
    Oczywiście nikt nie broni Tobie użyć innego metaalgorytmu. Tyle że 95% programów szachowych (więc pewnie warcabowych też) stosuje takie właśnie, pół-"czołgowe" przeszukiwanie przestrzeni rozwiązań.
    
    W przypadku algorytmu genetycznego musiałbyś umieć zapisać reguły wykonywania ruchów w postaci genotypu + zaimplementować jego mutacje i krzyżowanie, co wydaje się na pierwszy rzut oka trudne. W przypadku sieci neuronowej, wejściem byłaby sytuacja na planszy, wyjściem - ruch... ale Ty musiałbyś wcześniej przygotować w miarę dużą treningową bazę optymalnych ruchów dla danych sytuacji na planszy, co znów wymaga użycia standardowego algorytmu ;)