Drevo igre
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
| 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
- rešene igre na deski
Sklici
Viri
🔥 Top keywords: Glavna stranPosebno:IskanjeFacebookSkrito v rajuPosebno:ZadnjeSpremembeNogometna Liga prvakovSlovenijaSeznam nemških igralcevZodiakMarija AntoanetaKategorija:Slovenski priimkiLjubljanaCarles PuigdemontFreelancerstvoNova24TVSeznam držav članic Evropske unijeYouTubeSeznam mednarodnih klicnih kodReal Madrid Club de FútbolDruga svetovna vojnaSeznam slovenskih slikarjevFrance PrešerenSeznam nemških filozofovDubajSabina KogovšekVolitve poslancev iz Slovenije v Evropski parlament 2024Meta PlatformsNogometRimsko cesarstvoSeznam škotskih fizikovSulejman I.MariborIranMatej ZemljičRadiotelevizija SlovenijaIranske pokrajineHrvaška demokratska skupnostWindows NT 4.0Izrael