'%3e%3cpath%20d='M21.97,16.783C18.592,14.338%2014.595,14.954%2012,17.1C11.344,16.628%2010.011,15.91%209.895,15.621C9.48,14.59%207.341,14.568%207.01,14.882C6.812,15.07%206.83,15.344%206.553,15.331C4.832,15.252%203.708,15.794%201.993,16.774'%20style='fill:none;fill-rule:nonzero;stroke:%2310b981;stroke-width:1.14px;'/%3e%3c/g%3e%3cg%20transform='matrix(1,0,0,2.04091,-14.1682,-22.4853)'%3e%3cpath%20d='M15.074,18.836L15.074,17.423'%20style='fill:none;stroke:%2310b981;stroke-width:0.62px;stroke-linecap:square;stroke-miterlimit:1.5;'/%3e%3c/g%3e%3cg%20transform='matrix(1,0,0,2.04091,6.00754,-22.5274)'%3e%3cpath%20d='M15.074,18.863L15.074,17.423'%20style='fill:none;stroke:%2310b981;stroke-width:0.62px;stroke-linecap:square;stroke-miterlimit:1.5;'/%3e%3c/g%3e%3cg%20transform='matrix(1,0,0,1.10679,-1,-3.20585)'%3e%3cpath%20d='M2,5.5C5.5,3.5%209.5,4%2012,5.8C14.5,4%2018.5,3.5%2022,5.5L22,16.8C18.5,14.8%2014.5,15.3%2012,17.1C9.5,15.3%205.5,14.8%202,16.8L2,5.5Z'%20style='fill:none;fill-rule:nonzero;stroke:%236ee7b7;stroke-width:1.14px;'/%3e%3c/g%3e%3cg%20transform='matrix(1,0,0,1.026,-1,-2.90714)'%3e%3cpath%20d='M12,5.8L12,17.1'%20style='fill:none;fill-rule:nonzero;stroke:%236ee7b7;stroke-width:1.2px;'/%3e%3c/g%3e%3cg%20transform='matrix(0.868549,0,0,1.12022,1.58071,-2.86274)'%3e%3cpath%20d='M8,15.6L8,19.8L6.5,18.5L5,19.8L5,15.6'%20style='fill:none;fill-rule:nonzero;stroke:%236ee7b7;stroke-width:1.2px;'/%3e%3c/g%3e%3cg%20transform='matrix(1,0,0,1,-1,-3.75633)'%3e%3cpath%20d='M5,9C6.467,8.4%207.967,8.5%209.5,9.3'%20style='fill:none;fill-rule:nonzero;stroke:%236ee7b7;stroke-width:1.2px;'/%3e%3c/g%3e%3cg%20transform='matrix(1,0,0,1,-1,-3.75633)'%3e%3cpath%20d='M5,12C6.333,11.467%208.119,11.635%209.119,12.235'%20style='fill:none;fill-rule:nonzero;stroke:%236ee7b7;stroke-width:1.2px;'/%3e%3c/g%3e%3cg%20transform='matrix(0.988254,-0.152823,0.152823,0.988254,6.85356,-2.53705)'%3e%3cpath%20d='M5,12C6.333,11.467%208.119,11.635%209.119,12.235'%20style='fill:none;fill-rule:nonzero;stroke:%236ee7b7;stroke-width:1.2px;'/%3e%3c/g%3e%3cg%20transform='matrix(1,0,0,1,-1,-3.75633)'%3e%3cpath%20d='M14.5,9.3C16.033,8.5%2017.533,8.4%2019,9'%20style='fill:none;fill-rule:nonzero;stroke:%236ee7b7;stroke-width:1.2px;'/%3e%3c/g%3e%3cg%20transform='matrix(1,0,0,1,-1,2.24367)'%3e%3cpath%20d='M5,9C6.467,8.4%207.967,8.5%209.5,9.3'%20style='fill:none;fill-rule:nonzero;stroke:%236ee7b7;stroke-width:1.2px;'/%3e%3c/g%3e%3cg%20transform='matrix(0.999988,0.00496871,-0.00496871,0.999988,-0.955288,2.16055)'%3e%3cpath%20d='M14.5,9.3C16.033,8.5%2017.533,8.4%2019,9'%20style='fill:none;fill-rule:nonzero;stroke:%236ee7b7;stroke-width:1.2px;'/%3e%3c/g%3e%3c/svg%3e)
Magyarázat
Az iteratív mélyítés először kis határral keres egy , majd fokozatosan nagyobb határokkal megismétli az elemzést. A sakkban a mélységet rendszerint plyban mérik, ahol egy ply az egyik fél egyetlen lépése.
Első pillantásra pazarlónak tűnik, mert a kezdéshez közeli állásokat többször is meglátogatja. A korábbi iterációk azonban értékes információt adnak: egy ideiglenesen legjobbnak tartott lépést, a főváltozatot, vagyis az adott pillanatban legjobbnak ítélt vonalat, eltárolt eredményeket és adatokat a . Ha a következő iteráció előbb vizsgálja meg a biztató választásokat, több ág állhat le korán, ami ellensúlyozza az ismételt munka nagy részét.
Legvilágosabb gyakorlati előnye az időkezelés. Ha az óra egy mélyebb iteráció közben a keresés leállítására kényszeríti a motort, az előző iteráció teljes eredménye még mindig rendelkezésre áll. Nem kell mindent egy esetleg befejezetlenül maradó keresésre feltennie.
Az iteratív mélyítés nem azt jelenti, hogy csak egy kedvelt vonalat hosszabbít meg. Minden iteráció nagyobb határral újra megvizsgálja a kezdőállást, bár szelektív technikák eltérő helyi mélységeket rendelhetnek a fa részeihez. A is kifelé tolja, de nem szünteti meg.
Használat és szövegkörnyezet
A felületek gyakran az aktuális iteráció elért mélységét mutatják, de önmagában egy nagyobb szám nem bizonyítja, hogy két különböző motor összehasonlítható munkát végzett.
Gyakori félreértések
Értelmetlen ismétlés
A korábbi munka lépéssorrendet, főváltozatot és eltárolt keresési információt ad, ezért a következő iteráció valójában nem a semmiből indul.
Mélyítés és szelektív kiterjesztés
Az iteratív mélyítés a teljes határt növeli az egyes menetek között; a kiterjesztés bizonyos vonalakhoz helyi keresést ad.
Források
- 1.Depth-first iterative-deepening: An optimal admissible tree search, Artificial Intelligence / Elsevier
- 2.Iterative Deepening, Chess Programming Wiki
- 3.search.cpp, Stockfish