B* iskalni algoritem

B* iskalni algoritem

Avtor: Sanja Zamida

Učni cilji: predstavitev algoritma

Predstavitev

B* iskalni algoritem je algoritem za določanje najboljšega vozlišča v grafu.

Prvi ga je objavil Hans Berliner leta 1979. Hans Berliner

Algoritem lahko povežemo z določenimi alogritmi kot so:

  • MIN/MAX allgoritem (dva igralca izmenjujeta poteze in oba poskušata izbrati najboljšo potezo oz. maksimizirati svojo vrednost, posledično pa minimizirati nasportnika) več o MIN/MAX algoritmu
  • alfa/beta algoritem (pregleduje tiste poteze oz. dele drevesa, ki vplivajo na končno rešitev) več o alfa/beta

Ločimo dve različici B* algoritma:

  • z nasprotnikom in
  • brez nasprotnika.

Bistvene razlike med njima ni, razlika je le v back up-u (več o tem kasneje). Predstavili bomo oba primera, vendar predstavitev temelji na primeru z nasprotnikom.

Ideja

B* iskalni algoritem lahko najbolje povežemo s šahom.

(http://www2.nauk.si/files/764/šah_2.jpg)

Shranjeno imamo celotno drevo igre. Drevo, v korenu drevesa vsebuje začetno pozicijo, v listih pa se nahajajo končne pozicije. Problem tega drevesa pri šahovski igri je njegova ogromna velikost, zato želimo preiskati samo del drevesa igre. Ta del drevesa imenujemo iskalno drevo. To drevo v korenu vsebuje trenutno pozicijo igre, v listih pa vozlišča, ki zadoščajo določenemu pogoju.

Algoritem na določen način preiskuje iskalno drevo s pomočjo ocenitvene funkcije, na koncu pa poda potezo za nadaljevanje igre. Kot vemo je šah igra med dvema igralcema. Oba imata popoln pregled nad celotno igro (pozicijo in potezami), zato takim igram pravimo tudi igre s polno informacijo. Igra poteka z izmenjavo potez med dvema igralcema. Vsaka poteza pa prinaša določeno prednost oz. slabost za igralca na potezi oz. za nasprotnika.

Gre za odločanje igralca, katero potezo izbrati.

Interval vrednosti pozicije

V nasprotju z algoritimi kot so alfa/beta ali min/max, kjer imamo samo vrednost pozicije, ima pri tem algoritmu vsako vozlišče dve vrednosti oz. nek interval vrednosti pozicije. Prva vrednost predstavlja optimistično vrednost, druga pa pesimistično vrednost. Iščemo najboljše vozlišče oz. najboljši interval, s tem da preiskujemo v globino (1).

(http://www2.nauk.si/files/764/vozlišče_0.jpg)

Igralec lahko izbere eno izmed podanih potez. Na primer na zgornji sliki, če bo igralec izbral potezo ena, potem bo v najboljšem primeru njegova poteza oz. njegov položaj vreden 200, v najslabšem pa 50 ali 300 in 100 ali 250 in 0.

Igralca zanima katero potezo naj izbere, seveda bi rad izbral tako, da bo na koncu zmagal.

  • (1) (Pregled grafa v globino je algoritem, s katerim pregledamo vsa vozlišča danega grafa...pregled v globino)

Kako izbrati najboljše vozlišče?

Najprej izmed podanih vozlišč izberemo tisto, ki ima največjo optimistično vrednost. In če je pesimistična vrednost tega vozlišča večja ali enaka kot optimistična vrednost vseh ostalih vozlišč, potem je to vozlišče zagotovo najboljše. Povedano drugače, tudi v najslabšem primeru bomo imeli več ali enako kot nasprotnik, torej dobili smo potezo za nadaljevanje igre.

Torej, katero vozlišče na spodnji sliki je najboljše ?

(http://www2.nauk.si/files/764/najboljše vozlišče_1.jpg)
vozlišče 1
vozlišče 2
nobeno
vozlišče 3

Pravilno!

Bravo! Optimistična vrednost vozlišča 3 je največja in ob enem je tudi pesimistična vrednost večja od optimističnih vrednosti ostalih vozlišč, torej je to vozlišče res najboljše.

Naprej

Napačno!

Ups, napačen odgovor! Optimistična vrednost mora biti največja izmed vseh vozlišč, prav tako pa mora biti pesimistična vrednost večja od optimističnih vrednosti ostalih vozlišč.

Naprej

Ni najboljšega vozlišča - ŠIRITEV

V primeru da ne moremo izbrati najboljšega vozlišča (ki ga ponavadi res ne moremo), moramo razširiti posamezna vozlišča in dokazati, katero je najboljše.

Pri tem uporabimo eno izmed dveh strategij:

  • PROVEBEST, s pomočjo katere želimo dvigniti pesimistično vrednost vozlišča z najvišjo optimistično vrednostjo, nad optimističnimi vrednostmi preostalih vozlišč
  • DISPROVEREST, s pomočjo katere želimo znižati optimistično vrednost preostalih vozlišč, pod pesimistično vrednostjo vozlišča z največjo optimistično vrednostjo.

Ko določeno vozlišče razširimo s tem dobimo nove intervale vrednosti. Torej pregledujemo poteze v naprej, pri tem upoštevamo kaj bo naredil nasprotnik in tako se lahko odločimo za pravilo potezo oz. vozlišče. Kot posledica širitve, se vrednosti na razširjenem vozlišču spremenijo. Pri primeru z nasprotnikom se spremeni tudi predznak, saj nekaj kar za igralca pomeni najboljše, je za nasprotnika najslabše. Predznaki se spreminjajo tudi pri back up-u (več v primeru).

Kako pa dobimo intervale? Intervale vrednosti pozicije dobimo s pomočjo ocenitvene funkcije, na katere igralec nima vpliva. Na primer pri šahu težko izračunamo končno vrednost pozicije. Če bi hoteli, bi morali iti do konče pozicije nap. šah/mat nato pa po potezah postopoma nazaj do začetne pozicije, drevo bi bilo preveliko. Torej če imamo določeno pozicijo na šahovski deski, različni algoritmi povedo koliko je ta pozicija vredna. Vsi ti algoritmi pa so odvisno od tega, kako je dobra ocenitvena funkcija in če omenjena funkcija ni dovolj dobra, ni nujno da te pripelje do pravilnega rezultata.

Kdaj je potrebno vozlišče razširiti? Ko...

Preveri

Pravilno!

Bravo! Res je, tako je najboljše vozlišče, ko ga najdemo, je algoritem končan. Naprej

Napačno!

Žal, odgovor ni pravilen. Torej premislimo še enkrat. Kakšna mora biti OV? Največja. Od česa mora biti večja PV? Od OV ostalih vozlišč.

Naprej

Primer (z nasprotnikom)

Na kratko

Če želimo poiskati najboljše vozlišče in ga ni med začetnimi vozlišči:

 

izberemo vozlišče z največjo OV

vozlišče razširimo

pogledamo PV, izberemo največjo

naredimo back-up

  • postopek ponovimo

V primeru, da ne moramo izbrati največje PV (vse so enake):

  • ponovimo zgornji postopek ...
  • po narejenem back up-u
  • pogledamo OV
  • izberemo največjo
  • naredimo backup
  • ponovimo zgornji postopek

Še en primer

Dodaten primer

Brez nasprotnika

Algoritem za primer brez nasprotnika je skoraj identičen.

Tudi tukaj poskušamo poiskati najboljše vozlišče:

  • izberemo tistega z največjo OV
  • pogledamo ali ustreza pogoju najbojšega vozlišča
  • če ne, imamo na voljo dve strategiji (PROVEBEST in DISPROVEREST)

Razlika je samo pri backup-u oz. varnostni kopiji, saj tukaj NE menjamo predznaka.

Primer (brez nasprotnika)

Uporaba

O algoritmu B* je zapisanega zelo malo, tudi njegova uporaba ni ravno razširjena. B* iskalni alogiritem se predvsem uporablja pri šahu, kot na primer:

  • za vrednotenje končne točke, z izvedbo iskanj null akcij (1) (Andrew Palay),
  • Maven (Scrabble) je s pomočjo B* ustanovil standard za analizo end-game (2)
  • B* algoritem uporabljen za izračun optimalne strategije za niz kombinatornih iger

ter

  • z njim želijo rešiti igro 8-puzzle
(http://www2.nauk.si/files/764/8puzzle.jpg)

(1) null akcije (več: null akcije)

(2) end-game ali šah mat (več: šah mat)

Strategiji

Poveži!

PROVEBEST
DISPROVEREST
dvig PV najboljšega vozlišča nad OV ostalih vozlišč
znižanje OV ostalih vozlišč pod PV najboljšega vozlišča

Preveri

Pravilno!

Bravo!

Naprej

Napačno!

Žal, ni pravilno! PROVEBEST (dvig PV najboljšega vozlišča nad OV ostalih vozlišč) DISPROVEREST (znižanje OV ostalih vozlišč pod PV najboljšega vozlišča)

Naprej

Back-up

Kaj naredimo pri back up-u oz. varnostni kopiji pri algoritmu z nasprotnikom?

Preveri

Pravilno!

Bravo!

Naprej

Napačno!

Pravilna sta dva odgovora, pri varnostni kopiji:

  • največjo PV zamenjamo z OV in spremenimo predznak ALI
  • največjo OV zamenjamo s PV in spremenimo predznak (slednji back up izvedemo, če v prejšnjem koraku nismo mogli izbrati največje PV)!

Naprej

z/brez nasprotnika

V čem je razlika med algoritmom z in brez nasprotnika?

Preveri

Pravilno!

Bravo! Res je, razlika je samo v menjavni predznaka. Pri primeru brez nasprotnika, ga ne menjamo.

Naprej

Napačno!

Žal, odgovor ni pravilen! Razlika je le v menjavi predznaka! Pri primeru brez nasprotnika, ga ne menjamo.

Naprej

Drevo 1

Podano imamo drevo:

(http://www2.nauk.si/files/764/kviz6.jpg)

Izberi, kaj lahko v danem primeru naredimo!

Preveri

Pravilno!

Bravo!

Naprej

Napačno!

Pravilna, sta dva odgovora, trenutno najboljše je vozlišče 2.

  • Če uporabimo PROVEBEST, razširimo vozlišče 2.
  • Če uporabimo DISPROVEREST, razširimo vozlišče 1 in 3.

Naprej

Drevo 2

Podano imamo drevo:

(http://www2.nauk.si/files/764/kviz7_0.jpg)

Izberi, kaj lahko v danem primeru naredimo!

Preveri

Pravilno!

Bravo!

Naprej

Napačno!

Pravilen je samo en odgovor. Vozlišče 3 je najboljše, saj ima največjo OV in PV večjo ali enako kot so OV vseh ostalih vozlišč.

Naprej

Tabela rezultatov

Zgolj informativna tabela rezultatov in s tem neka ocena, na koliko vprašanj ste odgovorili pravilno in na koliko žal ne.

Literatura

Celotna predstavitev je povezata po:

  • Berliner, "The B* tree search algorithm : a best-first proof procedure" (1978). Computer Science Department.Paper 2462. http://repository.cmu.edu/compsci/2462 (dostopno 24. 01. 2014).
  • Palay, Andrew J., "An experimental analysis of the B* tree search algorithm" (1980). Computer Science Department.Paper 2415. http://repository.cmu.edu/compsci/2415 (dostopno 24. 01. 2014)
  • B*. http://en.wikipedia.org/wiki/B* (dostopno 20.01.2014).
  • B*. http://chessprogramming.wikispaces.com/B* (dostopno 20.01.2014).
  • Hans Berliner. http://en.wikipedia.org/wiki/Hans_Berliner (dostopno 20.01.2014).
  • Alpha–beta pruning. http://en.wikipedia.org/wiki/Alpha%E2%80%93beta_pruning (dostopno 20.01.2014).
  • Minimax. http://en.wikipedia.org/wiki/Minima (dostopno 20.01.2014).
  • A* search algorithm. http://en.wikipedia.org/wiki/A*_search_algorithm (dostopno 20.01.2014).
  • Pregled grafa v globino. http://wiki.fmf.uni-lj.si/wiki/Pregled_grafa_v_globino (dostopno 20.01.2014).
  • Null move. http://en.wikipedia.org/wiki/Null_move (dostopno 20.01.2014).
  • Mat. http://sl.wikipedia.org/wiki/Mat (dostopno 20.01.2014).

Povezave do slik:

  • GBG Software. https://www.google.com/search?q=8-puzzle&source=lnms&tbm=isch&sa=X&ei=OQcnU-jGF8bjywPW3ILYDA&ved=0CAcQ_AUoAQ&biw=1422&bih=735&dpr=0.9#facrc=_&imgdii=_&imgrc=3B4g-gBUVsyrfM%253A%3BCQWHPVgsBWXScM%3Bhttp%253A%252F%252Fgbgsoftware.net%252Fwp-content%252Fuploads%252F2013%252F10%252F8puzzle.png%3Bhttp%253A%252F%252Fgbgsoftware.net%252F%3B332%3B601 (dostopno 18.03.2014).
  • Nastavi Tradiciju. http://www.google.com/imgres?imgurl=http%3A%2F%2Fwww.nastavitradiciju.rs%2Fslike%2Fsahv.jpg&imgrefurl=http%3A%2F%2Fwww.nastavitradiciju.rs%2Fsah.html&h=668&w=1000&tbnid=mJwAeHMtX3q1sM%3A&zoom=1&docid=EmAv2VfI5cKOsM&ei=bCppU5SVEsf9yAPVgoHQCg&tbm=isch&ved=0CG8QMygIMAg&iact=rc&uact=3&dur=421&page=1&start=0&ndsp=1 (dostopno 18.03.2014).
0%
0%