Algorytm proof-number search jest znanym algorytmem służącym do rozwiązywania gier logicznych. Rozwiązanie gry jest jednoznaczne ze znalezieniem optymalnej strategii i pozwala przeprowadzić rozgrywkę w sposób pozwalający na osiągnięcie najlepszego możliwego wyniku. Jedną z największych wad tego algorytmu, naturalnie pracującego na strukturze drzewa, jest wielokrotne rozwijanie identycznych poddrzew gry co prowadzi do nadmiarowego zużycia pamięci. Jednym z możliwych sposobów służących rozwiązaniu tego problemu jest zastosowanie struktury digrafu acyklicznego zamiast drzewa. Może to jednak prowadzić do przeoczenia przez tak zmodyfikowany algorytm pewnych strategii, a to z kolei prowadzi do nieoptymalnej gry. W niniejszym artykule przeprowadzono badania wydajności i poprawności działania tak zmodyfikowanego algorytmu przy wykorzystaniu różnych wariantów gry logicznej "Skoczki".
Authors
Additional information
- Category
- Publikacja w czasopiśmie
- Type
- artykuły w czasopismach recenzowanych i innych wydawnictwach ciągłych
- Language
- polski
- Publication year
- 2011
