Utvärderingsfunktion

En utvärderingsfunktion , även känd som en heuristisk utvärderingsfunktion eller statisk utvärderingsfunktion , är en funktion som används av spelande datorprogram för att uppskatta värdet eller godheten av en position (vanligtvis vid ett löv eller terminalnod) i ett spelträd. För det mesta är värdet antingen ett reellt tal eller ett kvantiserat heltal , ofta i n -delar av värdet på en spelpjäs, såsom en sten i go eller en bonde i schack, där n kan vara tiondelar, hundradelar eller annat lämpligt bråkdel, men ibland är värdet en matris med tre värden i enhetsintervallet , som representerar vinst-, oavgjort- och förlustprocenten för positionen.

Det finns inga analytiska eller teoretiska modeller för utvärderingsfunktioner för olösta spel, inte heller är sådana funktioner helt ad-hoc. Sammansättningen av utvärderingsfunktioner bestäms empiriskt genom att infoga en kandidatfunktion i en automat och utvärdera dess efterföljande prestanda. Det finns nu en betydande mängd bevis för flera spel som schack, shogi och vad gäller den allmänna sammansättningen av utvärderingsfunktioner för dem.

Spel där speldatorprogram använder utvärderingsfunktioner inkluderar schack , go , shogi (japanskt schack), othello , hex , backgammon och dam . Dessutom, med tillkomsten av program som MuZero , använder datorprogram också utvärderingsfunktioner för att spela videospel, som de från Atari 2600 . Vissa spel som tic-tac-toe är starkt lösta och kräver ingen sökning eller utvärdering eftersom ett diskret lösningsträd är tillgängligt.

Relation till sökning

Ett träd med sådana utvärderingar är vanligtvis en del av en sökalgoritm, till exempel Monte Carlo-trädsökning eller en minimaxalgoritm som alfa–beta-sökning . Värdet antas representera den relativa sannolikheten att vinna om spelträdet utökades från den noden till slutet av spelet. Funktionen tittar bara på den aktuella positionen (dvs. vilka utrymmen bitarna är på och deras relation till varandra) och tar inte hänsyn till positionens historia eller utforskar möjliga förflyttningar framåt från noden (därför statiska). Detta innebär att för dynamiska positioner där taktiska hot finns, kommer utvärderingsfunktionen inte att vara en korrekt bedömning av positionen. Dessa positioner kallas icke- vilande ; de kräver åtminstone en begränsad typ av söktillägg som kallas quiescence search för att lösa hot före utvärdering. Vissa värden som returneras av utvärderingsfunktioner är absoluta snarare än heuristiska, om en vinst, förlust eller oavgjort inträffar vid noden.

Det finns ett intrikat samband mellan sökning och kunskap i utvärderingsfunktionen. Djupare sökning gynnar mindre kortsiktiga taktiska faktorer och mer subtila positionsmotiv med lång horisont i utvärderingen. Det finns också en avvägning mellan effektiviteten av kodad kunskap och beräkningskomplexitet: beräkning av detaljerad kunskap kan ta så mycket tid att prestandan minskar, så approximationer till exakt kunskap är ofta bättre. Eftersom utvärderingsfunktionen beror på det nominella sökdjupet samt de tillägg och minskningar som används i sökningen, finns det ingen generisk eller fristående formulering för en utvärderingsfunktion. En utvärderingsfunktion som fungerar bra i en applikation kommer vanligtvis att behöva justeras om eller tränas om för att fungera effektivt i en annan applikation.

I schack

I schack är utmatningen av en utvärderingsfunktion vanligtvis ett heltal , och enheterna för utvärderingsfunktionen kallas vanligtvis bönder . Termen 'bonde' hänvisar till värdet när spelaren har en bonde mer än motståndaren i en position, som förklaras i Schackpjäsens relativa värde . Heltalet 1 representerar vanligtvis en bråkdel av en bonde, och vanligen använda i datorschack är centipawns , som är en hundradel av en bonde. Större utvärderingar indikerar en materiell obalans eller positionsfördel eller att en vinst av material vanligtvis är nära förestående. Mycket stora utvärderingar kan tyda på att schackmatt är nära förestående. En utvärderingsfunktion kodar också implicit värdet av rätten att flytta, vilket kan variera från en liten bråkdel av en bonde till vinst eller förlust.

Handgjorda utvärderingsfunktioner

Historiskt sett i datorschack är villkoren för en utvärderingsfunktion konstruerade (dvs. handgjorda) av motorutvecklaren, i motsats till upptäckt genom att träna neurala nätverk . Det allmänna tillvägagångssättet för att konstruera handgjorda utvärderingsfunktioner är som en linjär kombination av olika viktade termer som bestäms för att påverka värdet av en position. Alla termer i en handgjord utvärderingsfunktion är dock inte linjära, vissa, som kungsäkerhet och bondstruktur, är olinjära. Varje term kan anses vara sammansatt av första ordningens faktorer (de som bara beror på rummet och varje del av det), andra ordningens faktorer (utrymmet i förhållande till andra rum) och n:te ordningens faktorer (beroende av historien om positionen).

En handgjord utvärderingsfunktion har vanligtvis en materialbalansterm som vanligtvis dominerar utvärderingen. De konventionella värdena som används för material är Queen=9, Rook=5; Riddare eller Biskop=3; Bonde=1; kungen tilldelas ett godtyckligt stort värde, vanligtvis större än det totala värdet av alla andra pjäser. Dessutom har den vanligtvis en uppsättning positionstermer som vanligtvis inte uppgår till mer än värdet av en bonde, men i vissa positioner kan positionstermerna bli mycket större, till exempel när schackmatt är nära förestående. Handgjorda utvärderingsfunktioner innehåller vanligtvis dussintals till hundratals individuella termer.

I praktiken skapas effektiva handgjorda utvärderingsfunktioner inte genom att någonsin utöka listan med utvärderade parametrar, utan genom noggrann justering eller träning av vikterna i förhållande till varandra, av en blygsam uppsättning parametrar såsom de som beskrivs ovan. För detta ändamål används positioner från olika databaser, till exempel från masterspel, motorspel, Lichess -spel eller till och med från självspel, som i förstärkningsinlärning .

Exempel

Ett exempel på handgjord utvärderingsfunktion för schack kan se ut så här:

c ₁ * material + c ₂ * rörlighet + c ₃ * kung säkerhet + c ₄ * mittkontroll + c ₅ * bonde struktur + c ₆ * kung tropism + ...

Var och en av termerna är en vikt multiplicerad med en skillnadsfaktor: värdet av vits material eller positionstermer minus svarts.

Materialtermen erhålls genom att tilldela ett värde i bondenheter till var och en av pjäserna.
Rörlighet är antalet lagliga drag som är tillgängliga för en spelare, eller alternativt summan av antalet utrymmen som attackeras eller försvaras av varje pjäs, inklusive utrymmen upptagna av vänskapsspel eller motståndarpjäser. Effektiv rörlighet, eller antalet "säkra" utrymmen en pjäs kan flytta till, kan också tas med i beräkningen.
Kungssäkerhet är en uppsättning bonusar och straff utvärderade för kungens placering och konfigurationen av bönder och pjäser intill eller framför kungen, och motstående pjäser som bär på utrymmen runt kungen.
Centerkontroll härleds från hur många bönder och pjäser som upptar eller bär på de fyra mittfälten och ibland de 12 fälten i den utökade mitten.
Bondestruktur är en uppsättning straffar och bonusar för olika styrkor och svagheter i bondstruktur, såsom straff för dubbla och isolerade bonde.
King tropism är en bonus för närhet (eller straff för avstånd) av vissa pjäser, särskilt drottningar och riddare, till den motsatta kungen.

Neurala nätverk

Även om neurala nätverk har använts i schackmotorers utvärderingsfunktioner sedan slutet av 1980-talet, blev de inte populära inom datorschack förrän i slutet av 2010-talet, eftersom den hårdvara som behövs för att träna neurala nätverk inte var tillräckligt stark vid den tiden, och snabb träning algoritmer och nätverkstopologi och arkitekturer har inte utvecklats ännu. Ursprungligen bestod neurala nätverksbaserade utvärderingsfunktioner i allmänhet av ett neuralt nätverk för hela utvärderingsfunktionen, med ingångsfunktioner valda från tavlan och vars utdata är ett heltal , normaliserat till centipawn - skalan så att ett värde på 100 är ungefär lika med ett material fördelen med en bonde. Parametrarna i neurala nätverk tränas vanligtvis med hjälp av förstärkningsinlärning eller övervakad inlärning . På senare tid har utvärderingsfunktioner i datorschack börjat använda flera neurala nätverk, med varje neuralt nätverk tränat för en specifik del av utvärderingen, såsom bondstruktur eller slutspel. Detta möjliggör hybridmetoder där en utvärderingsfunktion består av både neurala nätverk och handgjorda termer.

Djupa neurala nätverk har använts, om än sällan , i datorschack efter att Matthew Lais Giraffe 2015 och Deepminds AlphaZero 2017 visade på genomförbarheten av djupa neurala nätverk i utvärderingsfunktioner. Det distribuerade datorprojektet Leela Chess Zero startades kort efter för att försöka replikera resultaten av Deepminds AlphaZero-uppsats. Förutom storleken på nätverken skiljer sig de neurala nätverken som används i AlphaZero och Leela Chess Zero också från de som används i traditionella schackmotorer eftersom de har två utgångar, en för utvärdering (värdehuvudet ) och en för rörelseordning ( policyhuvudet ) ), snarare än bara en utgång för utvärdering. Dessutom, även om det är möjligt att ställa in utdata från värdehuvudet för Leelas neurala nätverk till ett reellt tal för att approximera centipawn-skalan som används i traditionella schackmotorer, är utdata som standard procentsatserna för vinst-drag-förlust, en vektor av tre värden vardera från enhetsintervallet . Eftersom djupa neurala nätverk är mycket stora kräver motorer som använder djupa neurala nätverk i sin utvärderingsfunktion vanligtvis en grafisk bearbetningsenhet för att effektivt kunna beräkna utvärderingsfunktionen.

Styckkvadratbord

En viktig teknik vid utvärdering sedan åtminstone tidigt 1990-tal är användningen av stykkvadrattabeller (även kallade styckevärdetabeller) för utvärdering. Varje bord är en uppsättning av 64 värden som motsvarar kvadraterna på schackbrädet. Den mest grundläggande implementeringen av pjäs-kvadratbord består av separata tabeller för varje typ av pjäs per spelare, vilket i schack resulterar i 12 pjäs-kvadratiska bord totalt. Mer komplexa varianter av stycke-kvadratbord används i datorschack, en av de mest framträdande är king-piece-square-bordet, som används i Stockfish , Komodo Dragon , Ethereal och många andra motorer, där varje bord tar hänsyn till positionen för varje typ av pjäs i förhållande till spelarens kung, snarare än positionen för varje typ av pjäs ensam. Värdena i tabellerna är bonusar/straff för placeringen av varje bit på varje utrymme, och kodar för en sammansättning av många subtila faktorer som är svåra att kvantifiera analytiskt. I handgjorda utvärderingsfunktioner finns det ibland två uppsättningar bord: en för öppnings-/mellanspelet och en för slutspelet; positionerna i mittspelet interpoleras mellan de två.

En vanlig handgjord utvärderingsfunktion som används i datorschack är Piece-Square Table Only , eller förkortat PeSTO , som är en mycket enkel utvärderingsfunktion som består av materialtermer och endast två uppsättningar av pjäsrutabord, en för öppningen och en för slutspel, för de positionella termerna. Ändå kan PeSTO utföra lika bra som många andra handgjorda utvärderingsfunktioner som används i datorschack. PeSTO skapades först av Tomasz Michniewski 2003 under namnet "Simplified Evaluation Function", och det nuvarande namnet introducerades av Ronald Friederich när han implementerade PeSTO i sin motor rofChade.

Ursprungligen utvecklad i datorshogi 2018 av Yu Nasu, den vanligaste utvärderingsfunktionen som används i datorschack idag är det effektivt uppdateringsbara neurala nätverket, eller NNUE för kort, ett gles och grunt neuralt nätverk som bara har tabeller i kvadrat som indata i det neurala nätverket. Faktum är att den mest grundläggande NNUE-arkitekturen helt enkelt är de 12 kvadratiska tabellerna som beskrivs ovan, ett neuralt nätverk med bara ett lager och inga aktiveringsfunktioner . En effektivt uppdateringsbar neural nätverksarkitektur, med king-piece-kvadratiska tabeller som dess indata, portades först till schack i ett Stockfish-derivat som heter Stockfish NNUE, offentligt släppt den 30 maj 2020, och antogs av många andra motorer innan det så småningom införlivades in i den officiella Stockfish-motorn den 6 augusti 2020.

Slutspelstabeller

Schackmotorer använder ofta slutspelstabellbaser i sin utvärderingsfunktion, eftersom det gör att motorn kan spela perfekt i slutspelet.

I Go

Historiskt sett har utvärderingsfunktioner i Go tagit hänsyn till både territoriumkontrollerat, påverkan av stenar, antal fångar och liv och död för grupper i styrelsen. Men moderna gospelande datorprogram använder till stor del djupa neurala nätverk i sina utvärderingsfunktioner, såsom AlphaGo , Leela Zero , Fine Art och KataGo , och ger en vinst/oavgjort/förlustprocent snarare än ett värde i antal stenar.

Se även

Slate, D och Atkin, L., 1983, "Chess 4.5, the Northwestern University Chess Program" i Chess Skill in Man and Machine 2nd Ed., s. 93–100. Springer-Verlag, New York, NY.
Ebeling, Carl, 1987, All the Right Moves: A VLSI Architecture for Chess (ACM Distinguished Dissertation), s. 56–86. MIT Press, Cambridge, MA

externa länkar