1. NCCU Academic Hub
  2. Publications
  3. College of Informatics
  4. Theses
  5. Item

Publications-Theses

Article View/Open

Publication Export

Google ScholarTM

NCCU Library

Citation Infomation

Related Publications in TAIR

題名 利用棋局紀錄之個人化西洋棋開局推薦
Personalized Chess Opening Recommendation Using Game Records
作者 楊元翰
貢獻者 陳正佳<br>沈錳坤
楊元翰
關鍵詞 西洋棋
開局推薦
推薦系統
風格分析
Chess
Opening recommendation
Recommendation system
Style analysis
日期 2015
上傳時間 2-Nov-2015 14:50:14 (UTC+8)
摘要 在西洋棋中，開局決定了棋局未來發展的基礎，棋手在開局階段局勢的好壞，會直接影響到接下來中局的發展，乃至全局的勝負。隨著西洋棋的演進，棋手們在比賽中進行各式各樣的棋步嘗試，發展出眾多經歷實戰考驗的開局，目前西洋棋的開局多達上千種變化，使得棋手在學習西洋棋的過程中，要花上大量的時間從眾多的西洋棋開局變化中，尋找適合自己的開局鑽研與使用。為幫助棋手在此階段的學習，本論文提出西洋棋開局推薦系統，從大數據協助學習的觀點，利用大量棋手們的開局經驗，對棋手做個人化的開局推薦。此系統以風格、棋力相似的棋手們所選用的開局為推薦基礎，並考量棋手習慣使用的下棋模式，推薦棋手善於發揮自身優勢、易於理解，並且投其所好的開局。為此，此西洋棋開局推薦系統包含風格分析、棋力評估、棋形截取，以及混合式推薦等部分。依據棋手過去的對局記錄，風格分析評估棋手下棋偏好冒險或保守的程度；棋力評估將傳統西洋棋棋力轉成可直觀比較棋手棋力程度差異之量表；棋形截取找出棋手習慣使用的下棋模式。最後，混合式推薦綜合考量上述三項因素，推薦出符合棋手棋風、棋力與下棋習慣模式的開局。
本論文以兩個實驗來評估風格分析與開局推薦系統的效果，在風格分析的實驗中，將風格分析方法評估棋手風格的結果與專家判斷的結果做比較；在開局推薦系統的實驗中，以棋手是否將會在比賽使用系統所推薦的開局來評估推薦效果。實驗結果顯示，風格分析對於世界冠軍棋手的風格評估幾乎與專家的判斷相同；開局推薦系統針對開局所設計的混合式推薦方法，推薦效果優於常見的推薦方法。
The Opening is the fundamental phase of a chess game, and significantly affects the result of a competition. With the evolution of chess, there has been developed thousands of chess openings at present. This makes it difficult and time-consuming for chess players to find and learn the openings suitable for them. For helping players to learn chess in the opening, we provide Opening Recommendation System (OPRS), which considers chess players’ experiences and recommends chess openings that could be understandable and favorite for the players. For personalized recommendation, OPRS analyzes the playing style, translates chess rating, extracts the playing patterns, and then performs hybrid recommendation based on the features obtained.
In the evaluation, the performance of the playing style analysis are demonstrated by comparing with the styles judged by chess experts for world chess championships.
For OPRS, the evaluations are according to the openings the players use in the chess tournaments in the next years. The experiments show that OPRS achieves good accuracies of the playing style analysis and outperforms the competitive methods for chess opening recommendation.
參考文獻 [1] G. Adomavicius, and T. Alexander, “Toward the next generation of recommender systems: A survey of the state-of-the-art and possible extensions,” Knowledge and Data Engineering, IEEE Transactions on, 17(6), 734-749, 2005
[2] L. Alburt, R. Dzindzichashvili, E. Perelshteyn and A. Lawrence, Opening for black, explained: a complete repertoire, Chess Information and Research Centre, 2005.
[3] R. Burke, “Hybrid recommender systems: Survey and experiments,” User modeling and user-adapted interaction, 12(4), 331-370, 2002.
[4] R. Burke, “Hybrid web recommender systems,” The adaptive web, Springer Berlin Heidelberg, 377-408, 2007.
[5] M. Buro, “Toward opening book learning,” ICCA Journal, 22(2), 98-102, 1999
[6] J. R. Capablanca, Chess fundamentals, Harcourt, 1921.
[7] C. Donninger and U. Lorenz, “Innovative opening-book handling, ” Advances in Computer Games, Springer Berlin Heidelberg, 1-10, 2006.
[8] S. L. Epstein, “Learning to play expertly: A tutorial on Hoyle,” Machines that learn to play games, 153-178, 2001.
[9] R. Gemulla, et al. “Large-scale matrix factorization with distributed stochastic gradient descent”, Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining, ACM, 2011.
[10] M. Guid and I. Bratko, “Computer analysis of world chess champions,” ICGA Journal, 29(2), 65-73, 2006.
[11] G.T. Heineman, G. Pollice, and S. Selkow, “Chapter 7:Path Finding in AI”, Algorithms in a Nutshell, Oreilly Media, 213–217, 2008.
[12] Y. Hijikata, I. Kazuhiro, and N. Shogo, “Content-based music filtering system with editable user profile,” Proceedings of the 2006 ACM symposium on Applied computing, ACM, 2006.
[13] D. W. Hosmer Jr and S. Lemeshow, Applied logistic regression, John Wiley & Sons, 2004.
[14] A. Huang, “Similarity measures for text document clustering,” Proceedings of the sixth new zealand computer science research student conference, Christchurch, New Zealand, 2008.
[15] R. M. Hyatt, “Book learning-a methodology to tune an opening book automatically,” ICCA Journal, 22(1), 3-12, 1999.
[16] F. Johannes, “Machine learning in games: A survey, ” Machines that learn to Play Games, 11-59, 2001.
[17] H. W. Kuhn, “The Hungarian method for the assignment problem,” Naval research logistics quarterly, 2(1‐2), 83-97, 1955.
[18] M. Levene and T. Fenner, “A methodology for learning players` styles from game records,” International Journal of Artificial Intelligence and Soft Computing, 2(4), 272-286, 2011.
[19] G. Lolli, Theoretical and practical observations on the game of chess, Printshop of St. Thomas Aquinas, Bologna, 1763.
[20] P. Lops, M. De Gemmis and G. Semeraro, “Content-based recommender systems: State of the art and trends, ” Recommender Systems Handbook, Springer US, 73-105, 2011.
[21] J. L. Myers, A. Well, and R. F. Lorch, Research design and statistical analysis, Routledge, 2010.
[22] D. L. Olson, and D. Delen, Advanced data mining techniques, Springer Science & Business Media, 2008.
[23] B. Pandolfini, Weapons of chess: an omnibus of chess strategies, Simon and Schuster, 1989.
[24] M. J. Pazzani and D. Billsus, “Content-based recommendation systems, ” The adaptive web, Springer Berlin Heidelberg, 325-341, 2007.
[25] D. Rasskin-Gutman, Chess metaphors: artificial intelligence and the human mind, MIT Press, 2009.
[26] P. Resnick, N. Iacovou, M. Suchak, P. Bergstrom and J. Riedl, “GroupLens: an open architecture for collaborative filtering of netnews,” Proceedings of the 1994 ACM Conference on Computer Supported Cooperative Work, ACM, 175-186, 1994.
[27] P. Resnick and H. R. Varian, “Recommender systems,” Communications of the ACM, 40(3), 56-58, 1997.
[28] J. Rowson and G. K. Burgess, Chess for Zebras: Thinking Differently about Black and White, Gambit, 2005.
[29] B. Sarwar, et al, “Item-based collaborative filtering recommendation algorithms, ” Proceedings of the 10th international conference on World Wide Web, ACM, 2001.
[30] J. B. Schafer, D. Frankowski, J. Herlocker and S. Sen, “Collaborative filtering recommender systems,” The adaptive web, Springer Berlin Heidelberg, 291-324, 2007.
[31] J. Speelman, Endgame preparation: advanced analysis of important areas, BT Batsford, 1981.
[32] R. S. Sutton and G. B. Andrew, Reinforcement learning: An introduction, Cambridge: MIT press, 1998.
[33] S. Walczak, “Pattern-based tactical planning,” International Journal of Pattern Recognition and Artificial Intelligence, 6(5), 955-988, 1992.
[34] S. Walczak, “Using inductive inference of past performance to build strategic cognitive adversary models,” PhD thesis, Univ. of Florida, Gainesville, Fla., 1990.
[35] X. Yang, et al, “A survey of collaborative filtering based social recommender systems,” Computer Communications, 1-10, 2014.
[36] N. Zhou, et al, “A hybrid probabilistic model for unified collaborative and content-based image tagging,” Pattern Analysis and Machine Intelligence, IEEE Transactions on, 33(7), 1281-1294, 2011.
[37] Chess Programing Wiki, Material,
https://chessprogramming.wikispaces.com/Material
[38] Chess Programing Wiki, Opening Book,
http://chessprogramming.wikispaces.com/Opening+Book
[39] ChessBase Shop, Big Database 2010, http://shop.chessbase.com/en/products/big_database_2010_dvd
[40] Wikipedia, Chess ,
http://en.wikipedia.org/wiki/Chess
[41] Wikipedia, Chess endgame,
http://en.wikipedia.org/wiki/Chess_endgame
[42] Wikipedia, Chess_middlegame ,
http://en.wikipedia.org/wiki/Chess_middlegame
[43] Wikipedia, Chess opening,
http://en.wikipedia.org/wiki/Chess_opening
[44] Wikipedia, Chess piece relative value,
http://en.wikipedia.org/wiki/Chess_piece_relative_value
[45] Wikipedia, Encyclopaedia of Chess Openings, https://en.wikipedia.org/wiki/Encyclopaedia_of_Chess_Openings
[46] Wikipedia, Elo rating system,
http://en.wikipedia.org/wiki/Elo_rating_system
[47] Wikipedia, Portable Game Notation, https://en.wikipedia.org/wiki/Portable_Game_Notation
描述 碩士
國立政治大學
資訊科學學系
101753012
資料來源 http://thesis.lib.nccu.edu.tw/record/#G0101753012
資料類型 thesis
dc.contributor.advisor 陳正佳<br>沈錳坤zh_TW
dc.contributor.author (Authors) 楊元翰zh_TW
dc.creator (作者) 楊元翰zh_TW
dc.date (日期) 2015en_US
dc.date.accessioned 2-Nov-2015 14:50:14 (UTC+8)-
dc.date.available 2-Nov-2015 14:50:14 (UTC+8)-
dc.date.issued (上傳時間) 2-Nov-2015 14:50:14 (UTC+8)-
dc.identifier (Other Identifiers) G0101753012en_US
dc.identifier.uri (URI) http://nccur.lib.nccu.edu.tw/handle/140.119/79206-
dc.description (描述) 碩士zh_TW
dc.description (描述) 國立政治大學zh_TW
dc.description (描述) 資訊科學學系zh_TW
dc.description (描述) 101753012zh_TW
dc.description.abstract (摘要) 在西洋棋中，開局決定了棋局未來發展的基礎，棋手在開局階段局勢的好壞，會直接影響到接下來中局的發展，乃至全局的勝負。隨著西洋棋的演進，棋手們在比賽中進行各式各樣的棋步嘗試，發展出眾多經歷實戰考驗的開局，目前西洋棋的開局多達上千種變化，使得棋手在學習西洋棋的過程中，要花上大量的時間從眾多的西洋棋開局變化中，尋找適合自己的開局鑽研與使用。為幫助棋手在此階段的學習，本論文提出西洋棋開局推薦系統，從大數據協助學習的觀點，利用大量棋手們的開局經驗，對棋手做個人化的開局推薦。此系統以風格、棋力相似的棋手們所選用的開局為推薦基礎，並考量棋手習慣使用的下棋模式，推薦棋手善於發揮自身優勢、易於理解，並且投其所好的開局。為此，此西洋棋開局推薦系統包含風格分析、棋力評估、棋形截取，以及混合式推薦等部分。依據棋手過去的對局記錄，風格分析評估棋手下棋偏好冒險或保守的程度；棋力評估將傳統西洋棋棋力轉成可直觀比較棋手棋力程度差異之量表；棋形截取找出棋手習慣使用的下棋模式。最後，混合式推薦綜合考量上述三項因素，推薦出符合棋手棋風、棋力與下棋習慣模式的開局。
本論文以兩個實驗來評估風格分析與開局推薦系統的效果，在風格分析的實驗中，將風格分析方法評估棋手風格的結果與專家判斷的結果做比較；在開局推薦系統的實驗中，以棋手是否將會在比賽使用系統所推薦的開局來評估推薦效果。實驗結果顯示，風格分析對於世界冠軍棋手的風格評估幾乎與專家的判斷相同；開局推薦系統針對開局所設計的混合式推薦方法，推薦效果優於常見的推薦方法。		zh_TW
dc.description.abstract (摘要) The Opening is the fundamental phase of a chess game, and significantly affects the result of a competition. With the evolution of chess, there has been developed thousands of chess openings at present. This makes it difficult and time-consuming for chess players to find and learn the openings suitable for them. For helping players to learn chess in the opening, we provide Opening Recommendation System (OPRS), which considers chess players’ experiences and recommends chess openings that could be understandable and favorite for the players. For personalized recommendation, OPRS analyzes the playing style, translates chess rating, extracts the playing patterns, and then performs hybrid recommendation based on the features obtained.
In the evaluation, the performance of the playing style analysis are demonstrated by comparing with the styles judged by chess experts for world chess championships.
For OPRS, the evaluations are according to the openings the players use in the chess tournaments in the next years. The experiments show that OPRS achieves good accuracies of the playing style analysis and outperforms the competitive methods for chess opening recommendation.		en_US
dc.description.tableofcontents 第一章 前言 1
第二章 相關研究 3
2.1 電腦西洋棋歷史 3
2.2開局庫 4
2.3 推薦系統 7
第三章 研究方法與步驟 12
3.1系統架構 12
3.2 棋力評估 13
3.3風格分析 14
3.4棋形擷取 24
3.5開局相似度 28
3.6協同式過濾 30
3.7內容式過濾 34
第四章 實驗 36
4.1資料來源 36
4.2 實驗方法 37
4.3系統環境 41
4.4實驗結果 43
4.5實驗討論 49
4.6實作議題 49
第五章 結論 52
參考文獻 53		zh_TW
dc.format.extent 2175716 bytes-
dc.format.mimetype application/pdf-
dc.source.uri (資料來源) http://thesis.lib.nccu.edu.tw/record/#G0101753012en_US
dc.subject (關鍵詞) 西洋棋zh_TW
dc.subject (關鍵詞) 開局推薦zh_TW
dc.subject (關鍵詞) 推薦系統zh_TW
dc.subject (關鍵詞) 風格分析zh_TW
dc.subject (關鍵詞) Chessen_US
dc.subject (關鍵詞) Opening recommendationen_US
dc.subject (關鍵詞) Recommendation systemen_US
dc.subject (關鍵詞) Style analysisen_US
dc.title (題名) 利用棋局紀錄之個人化西洋棋開局推薦zh_TW
dc.title (題名) Personalized Chess Opening Recommendation Using Game Recordsen_US
dc.type (資料類型) thesisen
dc.relation.reference (參考文獻) [1] G. Adomavicius, and T. Alexander, “Toward the next generation of recommender systems: A survey of the state-of-the-art and possible extensions,” Knowledge and Data Engineering, IEEE Transactions on, 17(6), 734-749, 2005
[2] L. Alburt, R. Dzindzichashvili, E. Perelshteyn and A. Lawrence, Opening for black, explained: a complete repertoire, Chess Information and Research Centre, 2005.
[3] R. Burke, “Hybrid recommender systems: Survey and experiments,” User modeling and user-adapted interaction, 12(4), 331-370, 2002.
[4] R. Burke, “Hybrid web recommender systems,” The adaptive web, Springer Berlin Heidelberg, 377-408, 2007.
[5] M. Buro, “Toward opening book learning,” ICCA Journal, 22(2), 98-102, 1999
[6] J. R. Capablanca, Chess fundamentals, Harcourt, 1921.
[7] C. Donninger and U. Lorenz, “Innovative opening-book handling, ” Advances in Computer Games, Springer Berlin Heidelberg, 1-10, 2006.
[8] S. L. Epstein, “Learning to play expertly: A tutorial on Hoyle,” Machines that learn to play games, 153-178, 2001.
[9] R. Gemulla, et al. “Large-scale matrix factorization with distributed stochastic gradient descent”, Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining, ACM, 2011.
[10] M. Guid and I. Bratko, “Computer analysis of world chess champions,” ICGA Journal, 29(2), 65-73, 2006.
[11] G.T. Heineman, G. Pollice, and S. Selkow, “Chapter 7:Path Finding in AI”, Algorithms in a Nutshell, Oreilly Media, 213–217, 2008.
[12] Y. Hijikata, I. Kazuhiro, and N. Shogo, “Content-based music filtering system with editable user profile,” Proceedings of the 2006 ACM symposium on Applied computing, ACM, 2006.
[13] D. W. Hosmer Jr and S. Lemeshow, Applied logistic regression, John Wiley & Sons, 2004.
[14] A. Huang, “Similarity measures for text document clustering,” Proceedings of the sixth new zealand computer science research student conference, Christchurch, New Zealand, 2008.
[15] R. M. Hyatt, “Book learning-a methodology to tune an opening book automatically,” ICCA Journal, 22(1), 3-12, 1999.
[16] F. Johannes, “Machine learning in games: A survey, ” Machines that learn to Play Games, 11-59, 2001.
[17] H. W. Kuhn, “The Hungarian method for the assignment problem,” Naval research logistics quarterly, 2(1‐2), 83-97, 1955.
[18] M. Levene and T. Fenner, “A methodology for learning players` styles from game records,” International Journal of Artificial Intelligence and Soft Computing, 2(4), 272-286, 2011.
[19] G. Lolli, Theoretical and practical observations on the game of chess, Printshop of St. Thomas Aquinas, Bologna, 1763.
[20] P. Lops, M. De Gemmis and G. Semeraro, “Content-based recommender systems: State of the art and trends, ” Recommender Systems Handbook, Springer US, 73-105, 2011.
[21] J. L. Myers, A. Well, and R. F. Lorch, Research design and statistical analysis, Routledge, 2010.
[22] D. L. Olson, and D. Delen, Advanced data mining techniques, Springer Science & Business Media, 2008.
[23] B. Pandolfini, Weapons of chess: an omnibus of chess strategies, Simon and Schuster, 1989.
[24] M. J. Pazzani and D. Billsus, “Content-based recommendation systems, ” The adaptive web, Springer Berlin Heidelberg, 325-341, 2007.
[25] D. Rasskin-Gutman, Chess metaphors: artificial intelligence and the human mind, MIT Press, 2009.
[26] P. Resnick, N. Iacovou, M. Suchak, P. Bergstrom and J. Riedl, “GroupLens: an open architecture for collaborative filtering of netnews,” Proceedings of the 1994 ACM Conference on Computer Supported Cooperative Work, ACM, 175-186, 1994.
[27] P. Resnick and H. R. Varian, “Recommender systems,” Communications of the ACM, 40(3), 56-58, 1997.
[28] J. Rowson and G. K. Burgess, Chess for Zebras: Thinking Differently about Black and White, Gambit, 2005.
[29] B. Sarwar, et al, “Item-based collaborative filtering recommendation algorithms, ” Proceedings of the 10th international conference on World Wide Web, ACM, 2001.
[30] J. B. Schafer, D. Frankowski, J. Herlocker and S. Sen, “Collaborative filtering recommender systems,” The adaptive web, Springer Berlin Heidelberg, 291-324, 2007.
[31] J. Speelman, Endgame preparation: advanced analysis of important areas, BT Batsford, 1981.
[32] R. S. Sutton and G. B. Andrew, Reinforcement learning: An introduction, Cambridge: MIT press, 1998.
[33] S. Walczak, “Pattern-based tactical planning,” International Journal of Pattern Recognition and Artificial Intelligence, 6(5), 955-988, 1992.
[34] S. Walczak, “Using inductive inference of past performance to build strategic cognitive adversary models,” PhD thesis, Univ. of Florida, Gainesville, Fla., 1990.
[35] X. Yang, et al, “A survey of collaborative filtering based social recommender systems,” Computer Communications, 1-10, 2014.
[36] N. Zhou, et al, “A hybrid probabilistic model for unified collaborative and content-based image tagging,” Pattern Analysis and Machine Intelligence, IEEE Transactions on, 33(7), 1281-1294, 2011.
[37] Chess Programing Wiki, Material,
https://chessprogramming.wikispaces.com/Material
[38] Chess Programing Wiki, Opening Book,
http://chessprogramming.wikispaces.com/Opening+Book
[39] ChessBase Shop, Big Database 2010, http://shop.chessbase.com/en/products/big_database_2010_dvd
[40] Wikipedia, Chess ,
http://en.wikipedia.org/wiki/Chess
[41] Wikipedia, Chess endgame,
http://en.wikipedia.org/wiki/Chess_endgame
[42] Wikipedia, Chess_middlegame ,
http://en.wikipedia.org/wiki/Chess_middlegame
[43] Wikipedia, Chess opening,
http://en.wikipedia.org/wiki/Chess_opening
[44] Wikipedia, Chess piece relative value,
http://en.wikipedia.org/wiki/Chess_piece_relative_value
[45] Wikipedia, Encyclopaedia of Chess Openings, https://en.wikipedia.org/wiki/Encyclopaedia_of_Chess_Openings
[46] Wikipedia, Elo rating system,
http://en.wikipedia.org/wiki/Elo_rating_system
[47] Wikipedia, Portable Game Notation, https://en.wikipedia.org/wiki/Portable_Game_Notation		zh_TW