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 (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.
[uredi] Število dovoljenih položajev in stopnja zapletenosti drevesa igre za nekatere igre
- Connect Four - stopnja 1013
- Checkers - 1018 položajev - stopnja 1031
- reversi - 1028 položajev - stopnja 1058 (8 · 8 deska, 64 polj)
- backgammon - ? (2 · 12 polj)
- šah - 1050 položajev - stopnja 10123 (8 · 8 deska, 64 polj)
- kitajski šah - stopnja 10150
- go - 10170 položajev - stopnja 10397 (19 · 19 deska, 361 polj)
[uredi] Glej tudi
- rešene igre na deski