Drevo igre
Drevo igre je v matematiki pojem, ki se nanaša na usmerjene grafe, kjer točke predstavljajo postavitve v igri, povezave pa poteze. Drevo igre podaja skupno število možnih »postavitev« v določeni igri in kaže njen potek. Celo drevo igre podaja potek igre od začetka in vse možne poteze za vsako postavitev.
Igre z večjim grafom imajo višjo stopnjo zapletenosti drevesa igre (zapletenost igre) in v teoriji iger veljajo za »težje«. Šah in go sta klasična zgleda za zelo zapleteni igri z velikima drevesoma igre.
Igra križcev in krožcev (tic-tac-toe) ima na primer stopnjo zapletenosti nekaj več kot 34.000, ker pa je zrcalno simetrična, je število manjše za 3/4 - 26.830.
Zapletenosti za nekatere igre uredi
| igra |
št. položajev |
stopnja zapletenosti |
povpr. dolžina |
število polj |
viri |
|---|---|---|---|---|---|
| križci in krožci | 103 | 105 | 9 | deska 3 × 3, 9 polj | [1]:15 |
| sim | 103 | 108 | 14 | 15 polj | |
| pentomine | 1012 | 1018 | 10 | 64 polj | [1]:15 |
| štiri v vrsto | 1013 | 1021 | 36 | deska 7 × 6, 42 polj | [1]:15[2] |
| angleška dama | 1018 | 1031 | 70 | deska 8 × 8, 64 polj | [2][3] |
| mlin | 1010 | 1050 | 50 | 50 polj | [1]:15 |
| Lines of Action | 1024 | 1056 | 63 | deska 8 × 8, 64 polj | [1]:15 |
| reversi (othello) | 1028 | 1058 | 58 | deska 8 × 8, 64 polj | [1]:15 |
| gomoku | 10105 | 1070 | 30 | deska 15 × 15, 225 polj | [2] |
| Hex | 1057 | 1098 | 40 | deska 11 × 11, 121 polj | [1]:15 |
| šah | 1047 | 10123 | 80 | deska 8 × 8, 64 polj | [1]:15 |
| backgammon | 1020 | 10144 | 50-60 | 2 × 12 + 4 = 28 polj | [1]:15 |
| kitajski šah | 1048 | 10150 | 95 | 90 polj | [1]:15 |
| Abalone | 1024 | 10154 | 87 | 61 polj | [1]:15 |
| amazonke | 1040 | 10212 | 84 | deska 10 × 10, 100 polj | [4][5] |
| šogi | 1071 | 10226 | 110 | deska 9 × 9, 81 polj | [1]:15 |
| go | 10171 | 10360 | 150 | deska 19 × 19, 361 polj | [1]:15 |
| arimaa | 1043 | 10402 | 92 | deska 8 × 8, 64 polj | [6][7][8] |
| Stratego | 10115 | 10535 | 381 | deska 10 × 10, 92 polj | [9] |
Glej tudi uredi
Sklici uredi
- ↑ 1,00 1,01 1,02 1,03 1,04 1,05 1,06 1,07 1,08 1,09 1,10 1,11 1,12 Chorus (2009), str. 15
- ↑ 2,0 2,1 2,2 Allis (1994).
- ↑ Schaeffer; idr. (2007).
- ↑ Kloetzer; Iida; Bouzy (2007).
- ↑ Hensgens (2001).
- ↑ Cox (2006).
- ↑ Wu (2011).
- ↑ Haskin (2006).
- ↑ Arts (2010).
Viri uredi
- Allis, Victor (1994). Searching for Solutions in Games and Artificial Intelligence (PDF) (doktorska disertacija). Univerza v Maastrichtu. ISBN 90-900748-8-0.
- Arts, A.F.C. (2010). Competitive Play in Stratego (PDF) (diplomska naloga). Univerza v Maastrichtu.
- Chorus, Pascal (29. junij 2009). Implementing a Computer Player for Abalone using Alpha-Beta and Monte-Carlo Search (PDF) (magistrska disertacija). Univerza v Maastrichtu.
- Cox, Christ-Jan (2006). Analysis and Implementation of the Game Arimaa (PDF) (diplomska naloga). Univerza v Maastrichtu.
- Garcia, Daniel Dante (1990). GAMESMAN : A finite, two-person, perfect-information game generator (PDF) (magistrska disertacija). Univerza Kalifornije, Berkeley.
- Haskin, Brian (2006), A Look at the Arimaa Branching Factor
- Hensgens, P. P. L. M. (2001). A Knowledge-Based Approach of the Game of Amazons (PDF) (diplomska naloga). Univerza v Maastrichtu, Institute for Knowledge and Agent Technology.
- van den Herik, H. J.; Uiterwijk, J. W. H. M.; van Rijswijck, J. (2002), »Games solved: Now and in the future«, Artificial Intelligence, 134: 277–311
- Kloetzer, Julien; Iida, Hiroyuki; Bouzy, Bruno (2007), The Monte-Carlo Approach in Amazons
- Schaeffer, Jonathan; idr. (6. junij 2007), »Checkers is Solved«, Science, 317 (5844): 1518–1522, doi:10.1126/science.1144079, PMID 17641166
- Wu, David Jian Wu (2011), Move Ranking and Evaluation in the Game of Arimaa (PDF)