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
	» Mariosti 02:28 » elliot_pl 02:25 » cVas 02:04 » piszczyk 01:08 » Rafael_3D 01:04 » Zbyszek.J 00:50 » Fl@sh 00:31 » MARC 00:31 » Star Ride 00:26 » Holyboy 00:16 » Paweł27 00:05 » abes99 00:02 » wrrr 23:58 » emigrus 23:52 » Wedrowiec 23:52 » hideox 23:51 » Soulburne 23:35 » tuptun 23:23 » Magnus 23:22 » Wolf 23:18 Dzisiaj przeczytano 41112 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 ;)