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.

Zapletenosti za nekatere igre[uredi | uredi kodo]

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

Sklici[uredi | uredi kodo]

Viri[uredi | uredi kodo]

      . https://project.dke.maastrichtuniversity.nl/games/files/phd/SearchingForSolutions.pdf.