Both sides previous revision
Previous revision
Next revision
|
Previous revision
|
en:dydaktyka:ggp:game_tree_1 [2018/01/23 14:12] msl [Ćwiczenia] |
en:dydaktyka:ggp:game_tree_1 [2021/01/12 01:02] (current) msl [MiniMax] |
{{ :pl:dydaktyka:ggp:tic-tac-toe-tree.png?500 | }} | {{ :pl:dydaktyka:ggp:tic-tac-toe-tree.png?500 | }} |
| |
We will use the 'ggp-base' framework, [[en:dydaktyka:ggp:gdl|introduced together with the gdl language]]. | We will use the 'ggp-base' framework, [[en:dydaktyka:ggp:gdl#validation|introduced together with the gdl language]]. |
| |
===== First Legal Move ===== | ===== First Legal Move ===== |
* [[https://www.youtube.com/watch?v=OkP8BAwfO24|a video presenting the algorithm]] | * [[https://www.youtube.com/watch?v=OkP8BAwfO24|a video presenting the algorithm]] |
| |
Please make sure that you understant the algorithm. | Please make sure that you understand the algorithm. |
| |
==== Ćwiczenia ==== | ==== Assignments ==== |
| |
- Create a MiniMax player based on the code below: <code java> | - Create a MiniMax player based on the code below: <code java> |
- test if the MiniMax wins with other bots in 'tic-tac-toe' | - test if the MiniMax wins with other bots in 'tic-tac-toe' |
- the same with 'checkers' | - the same with 'checkers' |
- implement timeout handling | - implement timeout handling (return a random move) |
- test the 'checkers' again | - test the 'checkers' again |
- bonus assignments | - bonus assignment: implement the [[https://thimbleby.gitlab.io/algorithm-wiki-site/wiki/minimax_search/|NegaMax algorithm]] |
- add possibility to cinstraint the search depth (several moves look-ahead) --- it's a classical method to scale the AI power. Why this method may be better than the timeout? | |
- implement the [[http://sandbox.thimbleby.net/algorithms/doku.php?id=minimax_search|NegaMax algorithm]] | |
| |
| |
Ending of [[https://www.youtube.com/watch?v=Ewh-rF7KSEg|the video]] shows an example of the Alpha-Beta pruning. | Ending of [[https://www.youtube.com/watch?v=Ewh-rF7KSEg|the video]] shows an example of the Alpha-Beta pruning. |
| |
<WRAP center round tip 60%>[[http://will.thimbleby.net/algorithms/doku.php?id=minimax_search_with_alpha-beta_pruning|Interactive Visualization of the algorithm]]. | <WRAP center round tip 60%>[[https://thimbleby.gitlab.io/algorithm-wiki-site/wiki/minimax_search_with_alpha-beta_pruning/|Interactive Visualization of the algorithm]]. |
</WRAP> | </WRAP> |
| |