Drevo igre

Iz Wikipedije, proste enciklopedije
Skoči na: navigacija, iskanje

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 | uredi kodo]

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

Glej tudi[uredi | uredi kodo]