Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revision Previous revision
Next revision
Previous revision
en:dydaktyka:ggp:game_tree_1 [2018/01/23 13:06]
msl [Two-moves Lookahead]
en:dydaktyka:ggp:game_tree_1 [2019/01/03 22:00] (current)
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 algorithmit 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''​.
en/dydaktyka/ggp/game_tree_1.1516712801.txt.gz · Last modified: 2018/01/23 13:06 by msl
www.chimeric.de Valid CSS Driven by DokuWiki do yourself a favour and use a real browser - get firefox!! Recent changes RSS feed Valid XHTML 1.0