This shows you the differences between two versions of the page.
| Both sides previous revision Previous revision Next revision | Previous revision Next revision Both sides next revision | ||
|
en:dydaktyka:ggp:game_tree_1 [2018/01/23 14:06] msl [Two-moves Lookahead] |
en:dydaktyka:ggp:game_tree_1 [2019/01/03 23:00] msl |
||
|---|---|---|---|
| Line 9: | Line 9: | ||
| {{ :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 ===== | ||
| Line 100: | Line 100: | ||
| Please make sure that you understant the algorithm. | Please make sure that you understant 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> | ||
| Line 171: | Line 171: | ||
| - bonus assignments | - bonus assignments | ||
| - 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? | - 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]] | + | - implement the [[https://thimbleby.gitlab.io/algorithm-wiki-site/wiki/minimax_search/|NegaMax algorithm]] |
| Line 179: | Line 179: | ||
| The MiniMax algorithm search all the tree's nodes which is unnecessary. To avoid it we can use so called [[https://en.wikipedia.org/wiki/Alpha%E2%80%93beta_pruning|Alpha-Beta cuts]]. The idea is that MiniMax doesn't have to check nodes, which are known to not have the better result than one we already have. | The MiniMax algorithm search all the tree's nodes which is unnecessary. To avoid it we can use so called [[https://en.wikipedia.org/wiki/Alpha%E2%80%93beta_pruning|Alpha-Beta cuts]]. The idea is that MiniMax doesn't have to check nodes, which are known to not have the better result than one we already have. | ||
| - | Ending of [[https://www.youtube.com/watch?v=Ewh-rF7KSEg|the vidoes]] shows an example of 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%> | + | <WRAP center round tip 60%>[[https://thimbleby.gitlab.io/algorithm-wiki-site/wiki/minimax_search_with_alpha-beta_pruning/|Interactive Visualization of the algorithm]]. |
| - | Interaktywna wizualizacja algorytmu jest [[http://will.thimbleby.net/algorithms/doku.php?id=minimax_search_with_alpha-beta_pruning|dostępna tutaj]]. | + | |
| </WRAP> | </WRAP> | ||
| - | Proszę się upewnić, że rozumieją Państwo działanie cięć Alpha-Beta. Należą one do szerokiej rodziny algorytmów [[https://en.wikipedia.org/wiki/Branch_and_bound|branch and bound]], używanych w szczególności w optymalizacji. | + | Please make sure you understand the algorithm, it belongs to the [[https://en.wikipedia.org/wiki/Branch_and_bound|branch and bound family]], a popular optimization technique. |
| - | ==== Ćwiczenia ==== | + | ==== Assignments ==== |
| - | - Proszę zaimplementować gracza ''SampleAlphaBetaGamer.java'' bazującego na graczu MiniMax z ograniczeniem czasowym. | + | - Implement the ''SampleAlphaBetaGamer.java'' based on the MiniMax player. |
| - | - Proszę przeprowadzić serię pojedynków ''SampleAlphaBetaGamer.java'' vs ''SampleMiniMaxGamer.java'' w warcaby lub podobną grę. Czy po kilku rozgrywkach widać jakąś przewagę nowego bota? | + | - Run several matches ('checkers' or something similar): SampleAlphaBetaGamer.java'' vs ''SampleMiniMaxGamer.java''. |
