ChessPWS – Algoritmes in computerschaak – In deze presentatie:
ChessPWS – Algoritmes in computerschaak – In deze presentatie:
0 0
pws_slides
slides about chesspwsOn Github diederik-dev / pws_slides
ChessPWS
Algoritmes in computerschaak
Profielwerkstuk van Diederik Loerakker
In deze presentatie:
- Onderwerp
- Onderzoeksvraag
- Planning
- Uitvoering + Theorie
- Resultaten
Onderwerp
Wiskunde + Informatica + Schaken
Onderzoeksvraag:
Kan ik een computerschaakprogramma schrijven dat kan winnen van mijzelf, zijn schrijver?
Spoiler alert:
ja.
Maar hoe?
Planning
Voor 4H en 5V: planning is zeer belangrijk!
Plan van aanpak
Versie 1 Versie 2 Versie 3Begin zomervakantie:
- Onderwerp uitwerken
- Mogelijke deelvragen bedenken
Zomervakantie:
- Werk vooruit!
- Inlezen: onderwerp-achtergrond + bijhorende theorie
Na de zomervakantie:
- Deelvragen + Hypothese opstellen en inleveren
- Onderzoek
- Voortgangs-gesprekjes, testen, etc.
Kerstvakantie:
- PWS afmaken/verbeteren!
Na de kerstvakantie:
- Inleveren
- Presentatie
- Beoordeling
Uitvoering + Theorie
Setup
- Git! Of een ander VCS (Version Control System)
- Bitbucket: deel het PWS onderling (en met de docent)
- Github: deel het PWS met IEDEREEN!
Voor 4H en 5V: Overleaf.comaanrader!
Basis
- Client
- Web server
- Game master
- Move generation
- Move search → kunstmatige intelligentie
- Move evaluation
Theorie
Kunstmatige intelligentie op basis van zoek-algoritmes:
- Minimax
- Alpha-Beta pruning
- Quiescence search
Minimax
Ook in andere 2-speler spellen:
Alpha-Beta pruning
Pruning: het "snoeien" van de search-tree.
descend leftmost first and evaluated 2 and 3 percolate max(2,3) higher up to set β = 3 β-cut in A because its value is at least 5 (which is superior to β = 3) Update of α = 3 at the top node α-cut in B because it is at most 0 (which is inferior to α = 3) α-cut in C because it is at most 2 conclude the best value for the top node is 3.Quiescence search
Het horizon effect kan gevaarlijk zijn: je kan niet zomaar stoppen in een ruil-reeks
Resultaten:
- Inzicht in complexiteit van schaken
- Efficiëntie van de zoekalgoritmes
- ChessPWS: online schaak-engine
Inzicht in complexiteit van schaken
PERFT (PERFormance Test): wat is het aantal nodes op diepte X?
Efficiëntie van de zoekalgoritmes
Move ordering, door ChessPWS, zoekdiepte van 4 ply, zonder quiescence-search.
De Kiwipete opstelling
ChessPWS: online schaak-engine
> open <Voor 4H en 5V:
- Tips
- 'Advanced' tips
Tips
Begin op tijd! Examens zullen anders hinderen! Kies een onderwerp waar je veel mee kan en waar je enthousiast over bent. Gebruik een online tekst-verwerker om samen te schrijven aan het PWS! Maak backups! En houd versies bij. Houd een uitgebreid logboek bij. Houd een bronnenlijst bij.Advanced
Leer en gebruik LaTeX [LahTech], een academische markup-taal. Houd vanaf het begin een bronnenlijst bij met BibTeX, een LaTeX plugin. Schrijf samen (en tegelijk!) aan hetzelfde LaTeX document op overleaf.com Gebruik een VCS, beste keuze: git Gebruik een remote-git-repository om altijd een zeer veilige backup te hebben. (met versie-geschiedenis!) Zie: Bitbucket en GitHub. Publiceer wat je maakt, op GitHub of op een eigen website. Programmeer je eigen presentatie met reveal.jsEinde presentatie.
Zijn er nog vragen?
ChessPWS links:
Speel tegen ChessPWS: chesspws.diederik-dev.me engine-server code: github.com/diederik-dev/chesspws_server client + webserver code: github.com/diederik-dev/chesspws_server
presentatie (deze slides): pws_slides.diederik-dev.me presentatie code: github.com/diederik-dev/pws_slides
Mijn website: diederik-dev.me