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. thumb|right|200px|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
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 sim 103 108 14 15 polj pentomine 1012 1018 10 64 polj štiri v vrsto 1013 1021 36 deska 7 × 6, 42 polj . angleška dama 1018 1031 70 deska 8 × 8, 64 polj . mlin 1010 1050 50 50 polj Lines of Action 1024 1056 63 deska 8 × 8, 64 polj reversi (othello) 1028 1058 58 deska 8 × 8, 64 polj gomoku 10105 1070 30 deska 15 × 15, 225 polj Hex 1057 1098 40 deska 11 × 11, 121 polj šah 1047 10123 80 deska 8 × 8, 64 polj backgammon 1020 10144 50-60 2 × 12 + 4 = 28 polj kitajski šah 1048 10150 95 90 polj Abalone 1024 10154 87 61 polj amazonke 1040 10212 84 deska 10 × 10, 100 polj .. šogi 1071 10226 110 deska 9 × 9, 81 polj go 10171 10360 150 deska 19 × 19, 361 polj arimaa 1043 10402 92 deska 8 × 8, 64 polj ... Stratego 10115 10535 381 deska 10 × 10, 92 polj .
Glej tudi
rešene igre na deski
Sklici
Viri
Kategorija:Matematika