Difference between revisions of "Markian Hlynka"
GerdIsenberg (talk | contribs) (Created page with "'''Home * People * Markian Hlynka''' FILE:markian.jpg|border|right|thumb|link=http://webdocs.cs.ualberta.ca/~darse/Photos/Friends/ | Markian Hlynka <ref>...") |
GerdIsenberg (talk | contribs) |
||
Line 1: | Line 1: | ||
'''[[Main Page|Home]] * [[People]] * Markian Hlynka''' | '''[[Main Page|Home]] * [[People]] * Markian Hlynka''' | ||
− | [[FILE:markian.jpg|border|right|thumb|link=http://webdocs.cs.ualberta.ca/~darse/Photos/Friends/ | + | [[FILE:markian.jpg|border|right|thumb|link=http://webdocs.cs.ualberta.ca/~darse/Photos/Friends/| Markian Hlynka <ref>[http://webdocs.cs.ualberta.ca/~darse/Photos/Friends/ Photo Gallery: Friends and Peers] by [[Darse Billings]]</ref> ]] |
− | | Markian Hlynka <ref>[http://webdocs.cs.ualberta.ca/~darse/Photos/Friends/ Photo Gallery: Friends and Peers] by [[Darse Billings]]</ref> | ||
− | ]] | ||
'''Markian Hlynka''',<br/> | '''Markian Hlynka''',<br/> | ||
a Canadian computer scientist and systems analyst at [[University of Alberta]]. Along with [[Jonathan Schaeffer]] et al., Markian Hlynka researched and published on [[Search|search]] enhancements and [[Temporal Difference Learning|temporal difference learning]]. | a Canadian computer scientist and systems analyst at [[University of Alberta]]. Along with [[Jonathan Schaeffer]] et al., Markian Hlynka researched and published on [[Search|search]] enhancements and [[Temporal Difference Learning|temporal difference learning]]. | ||
+ | <span id="PreSearching"></span> | ||
+ | =Pre-Search= | ||
+ | <ref>[[Markian Hlynka]], [[Jonathan Schaeffer]] ('''2004'''). ''Pre-Searching''. [[ICGA Journal#27_4|ICGA Journal, Vol. 27, No. 4]]</ref> | ||
+ | ==Abstract== | ||
+ | This paper introduces the idea of pre-searching a position — searching it before [[Alpha-Beta|αβ]] determines that it needs to be searched. Consider the case where an iteration of αβ search comes across a position p that needs to be searched to [[Depth|depth]] d1, and the [[Transposition Table|transposition table]] reveals that p will likely need to be searched later in that iteration to depth d2 greater than d1. Pre-searching involves speculatively searching p to depth d2, even though it has not been demonstrated that search to this depth is needed. If the gamble is successful, then additional accuracy is introduced to the search (using a result with extra search depth d2 − d1). While any search extension scheme is not without some risk, empirical results indicate that the impact on the αβ search tree size is small, but the additional accuracy that is introduced improves program performance. | ||
+ | |||
+ | ==Pseudo Code== | ||
+ | <pre> | ||
+ | // Assumptions: | ||
+ | // * search depth counts down to 0 (leaf node) | ||
+ | // * IDDepth is the iterative deepening search depth | ||
+ | // * searches are to a fixed depth | ||
+ | int AlphaBeta( state, depth, alpha, beta, presearch ) { | ||
+ | if( TerminalNode( state ) || depth == 0 ) | ||
+ | return( Evaluate( state ) ); | ||
+ | |||
+ | save_alpha = alpha; | ||
+ | save_beta = beta; | ||
+ | tt_found = TTLook( state, &tt_depth, &tt_value, &tt_bound, &tt_iteration ); | ||
− | = | + | if( tt_found == TRUE && tt_depth >= depth ) { |
− | < | + | if( tt_bound == LOWER ) alpha = MAX( alpha, tt_score ); |
− | + | if( tt_bound == UPPER ) beta = MIN( beta, tt_score ); | |
+ | if( tt_bound == ACCURATE ) alpha = beta = tt_bound; | ||
+ | if( alpha >= beta ) return( alpha ); | ||
+ | } | ||
+ | // Check for pre-search conditions | ||
+ | if( tt_found && // node is in TT | ||
+ | tt_iteration != IDDepth && // not updated this iteration | ||
+ | // Check that entry has deeper search needs | ||
+ | tt_depth + ( IDDepth - tt_iteration) >= depth ) { | ||
+ | // Found a shallow node | ||
+ | new_depth = tt_depth + ( IDDepth - tt_iteration ); | ||
+ | if( presearchFilter( newdepth, depth, tt_depth, tt_iteration, presearch ) == YES ) { | ||
+ | presearch = TRUE; | ||
+ | depth = new_depth; | ||
+ | } | ||
+ | } | ||
+ | score = -INFINITY; | ||
+ | num_moves = Generate( state, moves[] ); | ||
+ | for( i = 1; i <= num_moves; i++ ) { | ||
+ | result = -AlphaBeta( state.moves[i], depth-1, -beta, -alpha, presearch ); | ||
+ | score = MAX( score, result ); | ||
+ | alpha = MAX( alpha, score ); | ||
+ | if( alpha >= beta ) | ||
+ | break; | ||
+ | } | ||
+ | // Normal TT update, but need to also save IDDepth | ||
+ | TTUpdate( state, score, save_alpha, save_beta, depth, IDDepth ); | ||
+ | return( score ); | ||
+ | } | ||
+ | </pre> | ||
+ | =Fotos= | ||
+ | [[FILE:Olympiad2005Go9x9.JPG|none|border|text-bottom|640px|link=http://www.iis.sinica.edu.tw/Conference/ICGA2005/icga/img/2005_09_04/slides/IMG_0255.html]] | ||
+ | [[10th Computer Olympiad]], [[10th Computer Olympiad#Go9x9|Go 9x9]], [https://en.wikipedia.org/wiki/Taipei Taipei] 2005, [[Shih-Chieh Huang]] and [[Markian Hlynka]] operating<br/>[https://www.game-ai-forum.org/icga-tournaments/program.php?id=98 Go Intellect] and [https://www.game-ai-forum.org/icga-tournaments/program.php?id=104 NeuroGo], [[Fredrik Niemelä]] watching <ref>[http://www.iis.sinica.edu.tw/Conference/ICGA2005/icga/e1.htm CO 10 and ACG 11], Pictures 09/04/2005</ref> | ||
=Selected Publications= | =Selected Publications= | ||
− | <ref>[https://dblp.org/pers | + | <ref>[https://dblp.org/pers/h/Hlynka:Markian.html dblp: Markian Hlynka]</ref> |
− | * [[Jonathan Schaeffer]], [[Markian Hlynka]], [[Vili Jussila]] ('''2001'''). ''Temporal Difference Learning Applied to a High-Performance Game-Playing Program''. [ | + | * [[Jonathan Schaeffer]], [[Markian Hlynka]], [[Vili Jussila]] ('''2001'''). ''[https://www.semanticscholar.org/paper/Temporal-Difference-Learning-Applied-to-a-Program-Schaeffer-Hlynka/85941af287e2158bd201a633cbcc763693652c7f Temporal Difference Learning Applied to a High-Performance Game-Playing Program]''. [[Conferences#IJCAI2001|CGW@IJCAI 2001]] |
* [[Markian Hlynka]], [[Jonathan Schaeffer]] ('''2004'''). ''Pre-Searching''. [[ICGA Journal#27_4|ICGA Journal, Vol. 27, No. 4]], [http://webdocs.cs.ualberta.ca/~jonathan/publications/ai_publications/PreSearch.pdf pdf] | * [[Markian Hlynka]], [[Jonathan Schaeffer]] ('''2004'''). ''Pre-Searching''. [[ICGA Journal#27_4|ICGA Journal, Vol. 27, No. 4]], [http://webdocs.cs.ualberta.ca/~jonathan/publications/ai_publications/PreSearch.pdf pdf] | ||
− | * [[Markian Hlynka]], [[Jonathan Schaeffer]] ('''2005'''). ''[ | + | * [[Markian Hlynka]], [[Jonathan Schaeffer]] ('''2005'''). ''[https://link.springer.com/chapter/10.1007/11922155_3 Automatic Generation of Search Engines]''. [[Advances in Computer Games 11]] |
=External Links= | =External Links= | ||
− | * [https://ist.ualberta.ca/blog/culture/full-circle Markian Hlynka Full Circle | Information Services and Technology UoA] | + | * [https://web.archive.org/web/20180727083721/https://ist.ualberta.ca/blog/culture/full-circle Markian Hlynka Full Circle | Information Services and Technology UoA] ([https://en.wikipedia.org/wiki/Wayback_Machine Wayback Machine], July 2018) |
=References= | =References= | ||
<references /> | <references /> | ||
'''[[People|Up one level]]''' | '''[[People|Up one level]]''' | ||
+ | [[Category:Researcher|Hlynka]] |
Revision as of 11:30, 17 May 2020
Home * People * Markian Hlynka
Markian Hlynka,
a Canadian computer scientist and systems analyst at University of Alberta. Along with Jonathan Schaeffer et al., Markian Hlynka researched and published on search enhancements and temporal difference learning.
Contents
Pre-Search
Abstract
This paper introduces the idea of pre-searching a position — searching it before αβ determines that it needs to be searched. Consider the case where an iteration of αβ search comes across a position p that needs to be searched to depth d1, and the transposition table reveals that p will likely need to be searched later in that iteration to depth d2 greater than d1. Pre-searching involves speculatively searching p to depth d2, even though it has not been demonstrated that search to this depth is needed. If the gamble is successful, then additional accuracy is introduced to the search (using a result with extra search depth d2 − d1). While any search extension scheme is not without some risk, empirical results indicate that the impact on the αβ search tree size is small, but the additional accuracy that is introduced improves program performance.
Pseudo Code
// Assumptions: // * search depth counts down to 0 (leaf node) // * IDDepth is the iterative deepening search depth // * searches are to a fixed depth int AlphaBeta( state, depth, alpha, beta, presearch ) { if( TerminalNode( state ) || depth == 0 ) return( Evaluate( state ) ); save_alpha = alpha; save_beta = beta; tt_found = TTLook( state, &tt_depth, &tt_value, &tt_bound, &tt_iteration ); if( tt_found == TRUE && tt_depth >= depth ) { if( tt_bound == LOWER ) alpha = MAX( alpha, tt_score ); if( tt_bound == UPPER ) beta = MIN( beta, tt_score ); if( tt_bound == ACCURATE ) alpha = beta = tt_bound; if( alpha >= beta ) return( alpha ); } // Check for pre-search conditions if( tt_found && // node is in TT tt_iteration != IDDepth && // not updated this iteration // Check that entry has deeper search needs tt_depth + ( IDDepth - tt_iteration) >= depth ) { // Found a shallow node new_depth = tt_depth + ( IDDepth - tt_iteration ); if( presearchFilter( newdepth, depth, tt_depth, tt_iteration, presearch ) == YES ) { presearch = TRUE; depth = new_depth; } } score = -INFINITY; num_moves = Generate( state, moves[] ); for( i = 1; i <= num_moves; i++ ) { result = -AlphaBeta( state.moves[i], depth-1, -beta, -alpha, presearch ); score = MAX( score, result ); alpha = MAX( alpha, score ); if( alpha >= beta ) break; } // Normal TT update, but need to also save IDDepth TTUpdate( state, score, save_alpha, save_beta, depth, IDDepth ); return( score ); }
Fotos
10th Computer Olympiad, Go 9x9, Taipei 2005, Shih-Chieh Huang and Markian Hlynka operating
Go Intellect and NeuroGo, Fredrik Niemelä watching [3]
Selected Publications
- Jonathan Schaeffer, Markian Hlynka, Vili Jussila (2001). Temporal Difference Learning Applied to a High-Performance Game-Playing Program. CGW@IJCAI 2001
- Markian Hlynka, Jonathan Schaeffer (2004). Pre-Searching. ICGA Journal, Vol. 27, No. 4, pdf
- Markian Hlynka, Jonathan Schaeffer (2005). Automatic Generation of Search Engines. Advances in Computer Games 11
External Links
References
- ↑ Photo Gallery: Friends and Peers by Darse Billings
- ↑ Markian Hlynka, Jonathan Schaeffer (2004). Pre-Searching. ICGA Journal, Vol. 27, No. 4
- ↑ CO 10 and ACG 11, Pictures 09/04/2005
- ↑ dblp: Markian Hlynka