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.

Prve dve izvršitvi za drevo igre križci in krožci

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