TIG_-_Skripta

Question 1

Cilj istraživanja u oblasti veštačke inteligencije je dizajniranje mašina koje će omogućiti obradu kompleksnih vidova informacija i realizacije sistema za:

Answer 1

• Obradu simboličkih matematičkih operacija
• Prevođenje sa jednog prirodnog jezika na drugi
• Donošenje strateških odluka u vojnim operacijama
• Komponovanje i orkestraciju muzike
• Logičku dedukciju
• Prepoznavanje oblika i automatsku percepciju prostora
• Kompjuterski šah

Ove oblasti predstavljaju ključne primene veštačke inteligencije.

Question 2

Teorija igara predstavlja teoriju o nezavisnom donošenju odluka u organizacijama gde odluke donose dva ili više autonomnih igrača. Šta je osnovna pretpostavka teorije igara?

Answer 2

Apsolutna nezavisnost odluke igrača od uticaja drugih igrača

Ova pretpostavka omogućava analizu različitih strategija i ishoda.

Question 3

Koje su klase igara prema interesima igrača?

Answer 3

• Kooperativne igre
• Nekooperativne igre
• Igre sa kombinovanim motivima

Svaka klasa igara ima specifične karakteristike i strategije.

Question 4

U kooperativnim igrama, igrači imaju zajednički interes. Dobar primer je situacija sa automobilima koji idu jedan drugom u susret. Šta igrači moraju da urade?

Answer 4

Moraju da sarađuju da ne bi došlo do udesa

Ova saradnja je ključna za izbegavanje negativnih ishoda.

Question 5

U nikooperativnim igrama, interesi igrača su potpuno suprotni. Koji je dobar primer za ovu vrstu igre?

Answer 5

Šah

U šahu, svaki igrač teži pobedi, što implicira suprotstavljene interese.

Question 6

Igre sa kombinovanim motivima imaju elemente i kooperativnosti i nekooperativnosti. Dajte primer takve igre.

Answer 6

Odnos sindikata radnika i uprave preduzeća

Ova situacija zahteva saradnju za zajednički profit.

Question 7

Pretpostavka o racionalnom delovanju igrača podrazumeva da igrač:

Answer 7

Poštuje sopstveni interes i racionalno bira najbolje nastavke

Ova pretpostavka je ključna za modeliranje strategija u teoriji igara.

Question 8

Šta predstavlja rezultat igre u teoriji igara?

Answer 8

Stranje koje je nastalo delovanjem strateških odluka i poteza svih igrača

Rezultat može varirati u zavisnosti od strategija koje igrači primenjuju.

Question 9

Definišite strategiju igre za svakog igrača.

Answer 9

Konstantni plan delovanja kroz ceo tok igre

Strategija uključuje predviđanje odgovora na moguće eventualnosti.

Question 10

Igra sa potpunim informacijama podrazumeva da igrač zna sve moguće strategije drugih igrača. Kako se klasifikuje igra sa nekompletnim informacijama?

Answer 10

Igra sa nekompletnim informacijama

U ovoj igri, igrač poznaje samo pravila i prioritete drugih igrača.

Question 11

Koja je definicija funkcije isplativosti?

Answer 11

Numerički opis značajnosti nekog ishoda za igrača

Funkcija isplativosti pomaže u evaluaciji strategija.

Question 12

Šah je igra sa perfektnim informacijama i nultim sumiranjem. Šta to znači?

Answer 12

Suma svih ishoda za sve igrače je nula

U šahu, dobitak jednog igrača je gubitak drugog.

Question 13

Osnovna minimaks teorema definiše postupak nalaženja najboljeg nastavka za igrača A. Koje su varijable u ovoj teoremi?

Answer 13

V - vrednost igre, A - matrica isplativosti, X,Y – matrica rešenja

Ova teorema je ključna za analizu strategija u nultim sumama.

Question 14

Pojam kombinatorne eksplozije se javlja u teoriji igara kada:

Answer 14

Broj čvorova u stablu raste eksponencijalno

Ovaj problem se javlja zbog velikog broja mogućih poteza.

Question 15

Metoda heurističkog sečenja stabla odlučivanja se zasniva na:

Answer 15

Sužavanju liste varijanti koje razmatraju šahisti

Ova metoda omogućava efikasnije pretraživanje mogućih poteza.

Question 16

Koja je osnovna razlika između heurističkog i numeričkog sečenja stabla odlučivanja?

Answer 16

• Heurističko sečenje: zasniva se na stabilnoj heuristici
• Numeričko sečenje: maksimalno ubrzava sve funkcije

Obe metode imaju svoje prednosti i mane u analizi igara.

Question 17

Ograničavanje ekspanzije stabla može dovesti do:

Answer 17

Horizontskog efekta

Ograničavanje dubine može uzrokovati nestabilnost u evaluaciji.

Question 18

Šta je horizontski efekat u šahu?

Answer 18

Negativni efekat koji se javlja kada se direktno ograniči dubina stabla

Ovaj efekat dovodi do velike nestabilnosti u evaluaciji na nivou terminalnih čvorova.

Question 19

Koji je prvi pokušaj konstruisanja automata izveo nemački inženjer Baron Wolfgang von Kempelen?

Answer 19

Mašina «turčin»

U mašini je bio sakriven neki šahovski majstor koji je razmišljao o potezima.

Question 20

Ko je napisao prvi šahovski program 1950. godine?

Answer 20

Alan Tjuring

Tjuring je takođe postulirao Tjuringov test.

Question 21

Ko je napisao prvi šahovski program koji igra šah primenjujući sva pravila igre?

Answer 21

Alan Kotok

Program je radio na kompjuteru IBM 7090.

Question 22

Koji je prvi kompjuter koji je postigao majstorski rejting?

Answer 22

BELLE

BELLE je postigao rejting od 2203 u oktobru 1983.

Question 23

U kojoj godini je održano prvo kompjutersko prvenstvo u Nju Jorku?

Answer 23

1970

Prvo mesto zauzeo je program Chess 3.0.

Question 24

Koji je prvi mikrokompjuter koji je pobedio šahovskog majstora u turnirskim uslovima?

Answer 24

BELLE

BELLE je postao prvi kompjuter koji je postigao majstorski rejting.

Question 25

U kojoj godini je program **HITECH** dostigao rejting od 2530?

Answer 25

1985 ## Footnote To je prvi program koji je dostigao rejting preko 2400.

Question 26

Ko je prvi velemajstor koji je izgubio od kompjutera 1977. godine?

Answer 26

Michael Stean ## Footnote Izgubio je u brzopoteznoj partiji.

Question 27

U kojoj godini **mikrokompjuter** prvi put pobeđuje u partiji protiv velikih kompjutera?

Answer 27

1984 ## Footnote Ovo se desilo na turniru u Kanadi.

Question 28

Koji program je pobedio Gari Kasparova u meču od 6 partija u **New York-u** 1997. godine?

Answer 28

IBM Deep Blue ## Footnote Ovo je prvi put da je kompjuter pobedio šahovskog šampiona u klasičnom šahu.

Question 29

Koji standard omogućava pamćenje šahovske pozicije i pratećih informacija u jedinstvenom ASCII nizu?

Answer 29

FEN ## Footnote FEN standard poseduje elemente za predstavljanje figura i praznih polja.

Question 30

Koje su osnovne strukture šahovskog programa?

Answer 30

* Stablo igre * Terminalni čvorovi * Algoritam za traženje ## Footnote Ove strukture su ostale u upotrebi do danas.

Question 31

Šta predstavlja **stablo igre** u šahovskom programu?

Answer 31

Dinamički formirano stablo prilikom razvoja početne pozicije ## Footnote Koristi poseban stek ili unutrašnji programski stek.

Question 32

Koji su procesi prilikom rada sa stablima odlučivanja?

Answer 32

* Analitički proces * Sintetički proces ## Footnote Analitički proces se odnosi na ekspanziju stabla, dok sintetički generiše najbolji potez.

Question 33

Šta su **terminalni čvorovi**?

Answer 33

Tačke u kojima se završava razvoj stabla ## Footnote Pridružuju im se numeričke vrednosti dobijene evaluacijom.

Question 34

Koja je razlika između **minimaks** i **NegaMax** procedura?

Answer 34

NegaMax koristi pozitivne vrednosti za povoljnije pozicije bez obzira na boju ## Footnote Minimaks dodeljuje pozitivne vrednosti belom i negativne crnom.

Question 35

Kako se definiše **šahovska tabla**?

Answer 35

Matrica dimenzija 8x8 elemenata ## Footnote Na svakom polju mogu se pozicionirati 13 različitih entiteta.

Question 36

Šta je **evaluaciona funkcija**?

Answer 36

Matematička aditivna funkcija koja sumira materijalne i pozicione aspekte ## Footnote Dodeljuje numeričku vrednost trenutnoj šahovskoj poziciji.

Question 37

Koje su vrste **generatora poteza**?

Answer 37

* Selektivni generator poteza * Inkrementalni generator poteza * Generator kompletne liste ## Footnote Svaka vrsta ima svoje specifične metode generisanja poteza.

Question 38

Šta je **algoritam za traženje**?

Answer 38

Implementira rekurzivnu proceduru za ekspanziju stabla ## Footnote Obrada terminalnih čvorova i rekurzivno maksimiziranje evaluacionih vrednosti.

Question 39

Koji je **najjednostavniji i najpouzdaniji mod rada** generatora poteza?

Answer 39

liste ## Footnote Omogućava primenu nekih drugih metoda za sečenje stabla, kao što je ETC (Enhanced Transposition Cutoff).

Question 40

Šta je **evaluaciona funkcija**?

Answer 40

Matematička aditivna funkcija koja sumira materijalne i pozicione aspekte trenutne šahovske pozicije ## Footnote Dodeljuje numeričku vrednost poziciji i predstavlja integral svih parametara.

Question 41

U kojem formatu se obično izvršava evaluaciona funkcija?

Answer 41

16-bitni format ## Footnote Numeričke vrednosti pozicije kreću se u rasponu –32768 do +32767.

Question 42

Šta se dešava sa ekstremnim vrednostima u evaluacionoj funkciji?

Answer 42

Koriste se za evaluaciju matova ## Footnote Vrednosti veće od 30000 ili manje od -30000.

Question 43

Šta podrazumeva pojam **simetrične evaluacione funkcije**?

Answer 43

Potpunu simetriju izračunavanja materijalnih i pozicionih aspekata figura ## Footnote Ne daje prednost belom igraču jer igra prvi.

Question 44

Kako se računa **materijalna ravnoteža** cele pozicije?

Answer 44

MEval = SUMA (Bi-Ci) Vi ## Footnote Bi su vrednosti belih figura, Ci su vrednosti crnih figura.

Question 45

U kojoj poziciji je materijalna evaluacija 0?

Answer 45

U početnoj šahovskoj poziciji ## Footnote Kada je broj figura isti za belog i crnog.

Question 46

Kada se materijalna evaluacija ne uzima u obzir?

Answer 46

U završnici kada figura nije matirajuća ## Footnote Na primer, skakač ili lovac.

Question 47

Šta je **contempt faktor**?

Answer 47

Faktor koji se uvodi da bi se izbeglo ponavljanje poteza ili remi varijante ## Footnote Ne evaluira remi sa 0.00, već sa malom negativnom vrednošću.

Question 48

Zašto je **centralizacija figura** važna?

Answer 48

Omogućava kontrolu nad većim brojem polja i razvija maksimalnu snagu figura ## Footnote Centralizovane figure dobijaju bonus u evaluaciji.

Question 49

Koja su osnovna pravila za **razvoj figura** u otvaranju?

Answer 49

* Razvoj centraliznih pešaka * Razvoj lakih figura (lovaca i skakača) * Rokada kralja * Postavljanje topova na strateški važne vertikale * Razvoj dame ## Footnote Ova pravila obezbeđuju skladan i harmoničan razvoj figura.

Question 50

Šta se smatra **promotivnim pešacima**?

Answer 50

Pešaci čije napredovanje do izvodnog polja ne može biti sprečeno ## Footnote Njihovo prisustvo je pozicioni plus za stranu koja ih poseduje.

Question 51

Šta su **duplirani pešaci**?

Answer 51

Dva pešaka iste strane na istoj vertikali ## Footnote Stvaraju defekt pešačke strukture i umanjuju vrednost evaluacije.

Question 52

Kako se definišu **izolovani pešaci**?

Answer 52

Pešaci koji na susednim vertikalama nemaju pešake svoje boje ## Footnote Postojanje izolovanih pešaka je pozicioni minus.

Question 53

Koja je **osnovna ideja** u implementaciji ALFA-BETA algoritma?

Answer 53

Korišćenje postojećih numeričkih rezultata za odsecanje podstabala ## Footnote Uvođenje dve vrednosti ALFA i BETA umesto jedne.

Question 54

Šta predstavlja vrednost promenjive **ALFA**?

Answer 54

Najbolju vrednost nastavka za stranu koja je na potezu ## Footnote Ako se otkrije bolji nastavak, ALFA se ažurira.

Question 55

Šta se dešava kada nova vrednost za ALFA postane veća ili jednaka BETA?

Answer 55

Ostale nastavke iz tog čvora ne moramo razmatrati ## Footnote Ne mogu uticati na promenu odluke na višim nivoima.

Question 56

Šta je **PVS procedura**?

Answer 56

Efikasnija varijanta ALFA-BETA algoritma ## Footnote Koristi se kada je uređivanje liste poteza blizu perfektnog.

Question 57

U čemu se sastoji **glavna varijanta** u kontekstu pozicionog vrednovanja?

Answer 57

Formiranje glavne varijante u što je kraćem mogućem vremenskom intervalu ## Footnote Omogućava supstituciju klasičnog rekurzivnog poziva sa intervalom (ALFA,BETA) efikasnijom varijantom.

Question 58

Šta predstavlja **PVS poziv**?

Answer 58

Analogna klasičnom pozivu, ali sa maksimalno suženim intervalom (ALFA,ALFA+1) ## Footnote Koristi se za sondiranje podstabla i određivanje promene ALFA ili BETA granice.

Question 59

Koliko je efikasnost **PVS procedure** prema nekim autorima?

Answer 59

Oko 10% ## Footnote To znači da PVS u proseku obrađuje 90% stabla koje obrađuje klasični ALFA-BETA algoritam.

Question 60

Osnovna ideja **null-move algoritma** proističe iz pretpostavke da strana koja je na potezu može da napravi _______.

Answer 60

pomak u evaluaciji ## Footnote Postavlja se pitanje da li protivnička strana može da napravi pomak u svojoj evaluaciji ako joj strana koja je na potezu ustupi potez.

Question 61

Kada se primenjuje **Alfa-Beta algoritam**?

Answer 61

Kada se null-move tehnika ne može primeniti ## Footnote Stepen redukcije kod null-move tehnike je standardno R=2.

Question 62

Šta je **quiescence procedura**?

Answer 62

Koristi se za rešavanje problema horizontskog efekta ## Footnote U svakom čvoru se obavlja evaluacija i koristi heuristički generator za određivanje liste poteza.

Question 63

Koje poteze quiescence procedura najčešće razmatra?

Answer 63

* Uzimanje protivničkih figura (capture) * Neki šahovi * Promocije ## Footnote Ovi potezi predstavljaju izvor nestabilnosti pozicije.

Question 64

Šta je **MVV/LVA tehnika**?

Answer 64

Tehnika za grubo sortiranje liste poteza prema očekivanom materijalnom dobitku ## Footnote Uvek potez koji uzima protivnički damu ima veću vrednost od poteza koji uzima protivničkog pešaka.

Question 65

Šta predstavlja **transpoziciona tabela**?

Answer 65

Konačnu memorijsku hash tabelu koja pamti informacije o čvorovima koji su već ispitani ## Footnote Omogućava korišćenje informacija u kasnijim fazama pretrage.

Question 66

Šta je **Etc - Enhanced Transposition Cutoff** tehnika?

Answer 66

Tehnika koja omogućava da se ne obrađuju nastavci iz čvora N ako su vrednosti ALFA i BETA za poziciju A dovoljne za izazivanje sečenja ## Footnote Pozicija A je već obrađena u nekom delu stabla.

Question 67

Koje su prednosti **history heuristike**?

Answer 67

* Smanjenje vremena potrebnog za rad generatorske funkcije * Poboljšanje redosleda poteza ## Footnote U kombinaciji sa transpozicionom tabelom pruža najbolje mogućnosti za optimalno uređenje liste poteza.

Question 68

Šta je **futility heuristika**?

Answer 68

Tehnika koja se koristi kada u poziciji ne postoje potezi koji daju šah protivničkom kralju ## Footnote U tom slučaju, ako je statička evaluacija manja od ALFA, ne ulazi se u quiescence proceduru.

Question 69

Koje su najčešće korišćene tehnike **ekstenzije stabla**?

Answer 69

* Izlaz iz pozicije u kojoj je kralj u šahu * Dolazak pešaka na 7 odnosno 2 red * Potez koji izaziva direktnu pretnju matiranju * Razmena figura na poslednjem nivou * Jedinstveni odgovor na potez ## Footnote Ove tehnike se koriste za povećanje dubine stabla kada je osnovna dubina nedovoljna.

Question 70

Šta je **Zobrist ključ**?

Answer 70

Transformacija pozicije na šahovskoj tabli u 64 bitnu reč korišćenjem XOR operacija ## Footnote Efikasna i brza transformacija koja minimizira greške u pozicijama.

Question 71

Šta je **Zobrist** transformacija?

Answer 71

Efikasna i brza transformacija pozicije u 64-bitnu reč korišćenjem XOR operacija ## Footnote Zobrist koristi višedimenzionalnu matricu za predstavljanje figura i njihovih pozicija.

Question 72

Koliko bita je potrebno za definiciju tipa figure, boje i koordinata u Zobrist sistemu?

Answer 72

* Tip figure: 3 bita * Boja: 1 bit * X koordinata: 3 bita * Y koordinata: 3 bita ## Footnote Ukupno: 3 + 1 + 3 + 3 = 10 bita.

Question 73

Koji su **standardni metodi paralelizacije** u šahovskim programima?

Answer 73

Deljenje stabla po vertikali na broj procesora ## Footnote Veći broj procesora može uzrokovati probleme sa raspodelom poslova i prenosom podataka.

Question 74

Šta je **distribuirana paralelizacija**?

Answer 74

Rešenje problema raspodele poslova u višeprocesnim sistemima ## Footnote Algoritam dinamički menja i alocira delove stabla na raznim procesorima.

Question 75

Šta su **transpozicione baze**?

Answer 75

Baze koje pamte vrednosti prethodno izračunatih pozicija ## Footnote Omogućavaju asocijativnu vezu između pozicija i vrednosti, štedeći vreme proračuna.

Question 76

Šta sadrže **transpozicione baze otvaranja**?

Answer 76

* Pozicije iz otvaranja * Njihove evaluacije * Ključne poteze ## Footnote Ne koriste Zobrist ključeve; svaka pozicija se pamti u originalnom obliku.

Question 77

Šta su **baze završnica (EGTB)**?

Answer 77

Baze koje sadrže informacije za sve moguće pozicije sa određenim brojem figura ## Footnote Dinamički se pristupa tokom obrade stabla.

Question 78

Koje su **vrste baza završnica**?

Answer 78

* DTM (Distance to Mate) * DTC (Distance to Conversion) ## Footnote DTM baze računaju najmanji broj poteza do mata, dok DTC baze računaju do konverzije.

Question 79

Koji su primeri baza tipa DTM?

Answer 79

* Edwards * Nalimov ## Footnote Nalimov baze čuvaju podatke u kompresovanoj formi za realno vreme.

Question 80

Šta je **princip vertikalne i oktalne pozicione simetrije**?

Answer 80

Koristi se za kompresiju podataka u bazi ## Footnote Simetrične pozicije se mogu predstaviti jednim slogom, smanjujući veličinu baze.

Question 81

Kako se kompresuju baze završnica kada nema pešaka?

Answer 81

Primena oktalne simetrije ## Footnote Može se pronaći još 7 oktalno simetričnih pozicija sa identičnom evaluacijom.

Question 82

Šta je **Nalimov baza**?

Answer 82

Baza koja pamti udaljenost od mata u kompresovanoj formi ## Footnote Omogućava korišćenje u realnom vremenu bez gubitaka u performansama.

Question 83

Kako funkcionišu **Enax baze**?

Answer 83

* Evaluacija dobitka direktno iz baze (stanje 0) * Razmatranje čvorova na sledećem nivou (stanje 1) ## Footnote U slučaju da nema pozicija sa vrednošću 1, osnovna pozicija je izgubljena.