Drevo igre
Iz Wikipedije, proste enciklopedije
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.
Število dovoljenih položajev in stopnja zapletenosti drevesa igre za nekatere igre [uredi]
| igra | št. položajev |
st. zapletenosti |
opombe |
|---|---|---|---|
| križci in krožci | 103 | 105 | deska 3 × 3, 9 polj |
| sim | 103 | 108 | 15 polj |
| štiri v vrsto | 1013 | 1021 | deska 7 × 6, 42 polj |
| angleška dama | 1018 | 1031 | deska 8 × 8, 64 polj |
| reversi | 1028 | 1058 | deska 8 × 8, 64 polj |
| gomoku | 10105 | 1070 | deska 15 × 15, 225 polj |
| backgammon | 1020 | 10144 | 2 × 12 + 4 = 28 polj |
| šah | 1047 | 10123 | deska 8 × 8, 64 polj |
| kitajski šah | 1048 | 10150 | 90 polj |
| šogi | 1071 | 10226 | deska 9 × 9, 81 polj |
| go | 10171 | 10360 | deska 19 × 19, 361 polj |
| arimaa | 1043 | 10402 | deska 8 × 8, 64 polj |
