Претрага броја доказа
Претрага броја доказа (енгл. Proof-number search) је алгоритам из области теорије игара, пронађен од стране холандског научника Виктора Елиса, а са применом најчешће у проналажењу оптималног потеза или у одређивању крајњег победника игре. Алгоритам је у суштини дизајниран за игре са два могућа исхода(победа и пораз), и функционише без испитивања целокупног бинарног стабла исхода игре.
У овом контексту доказати одређену грану у стаблу значи показати да је исход након те гране победа у корист тренутног играча, слично оповргнути грану значи показати да је исход након ње пораз. Током извршавања чувају се и ажурирају бројеви доказаних и оповргнутих грана и они представљају доње границе за број грана које треба испитати. На тај начин што увек пролазимо кроз доказане (оповргнуте) гране долазимо до ефикасног начина претраге стабла.
Због проблема недостатка меморије приликом решавања проблема већих димензија, развијене су додатне варијанте овог алгоритма као што су PN2 и PDS-PN[1].
Референце[уреди | уреди извор]
- ^ Mark H.M. Winands, Jos W.H.M. Uiterwijk, and H. Jaap van den Herik (2003). „PDS-PN: A New Proof-Number Search Algorithm” (PDF). Lecture Notes in Computer Science.