Changes

Jump to: navigation, search

Morph

14,570 bytes added, 11:21, 26 May 2018
Created page with "'''Home * Engines * Morph''' FILE:robert_levinson_morph.jpg|border|right|thumb|link=http://www1.ucsc.edu/oncampus/currents/97-05-05/levinson.photo.htm|[[R..."
'''[[Main Page|Home]] * [[Engines]] * Morph'''

[[FILE:robert_levinson_morph.jpg|border|right|thumb|link=http://www1.ucsc.edu/oncampus/currents/97-05-05/levinson.photo.htm|[[Robert Levinson]] and Morph <ref> [http://www1.ucsc.edu/oncampus/currents/97-05-05/levinson.photo.htm Robert Levinson photo: 05-05-97] by Don Harris, UCSC Photo Services, in [http://www1.ucsc.edu/oncampus/currents/97-05-05/chess.htm "Deep Blue" inspires deep thinking about artificial intelligence by computer scientist] by [http://scicom.ucsc.edu/faculty/ Robert Irion], [http://www1.ucsc.edu/oncampus/currents/97-05-05/index.html CURRENTS, University of California, Santa Cruz], May 5, 1997</ref> ]]

'''Morph''' <ref>''The name "Morph" comes from the [https://en.wikipedia.org/wiki/Greek_language Greek] "morph" meaning [https://en.wikipedia.org/wiki/Form form] and the chess great, [https://en.wikipedia.org/wiki/Paul_Morphy Paul Morphy]'', footnote 1 in [[Robert Levinson]], [[Richard Snyder]] ('''1991'''). ''Adaptive Pattern-Oriented Chess''. Proceedings of the 8th International Workshop on Machine Learning (eds. L. Birnbaum and G. Collins), pp. 85-89. Morgan Kaufmann, San Mateo, CA. Also published in: Proceedings of the Ninth National Conference on Artificial Intelligence AAAI-91, pp. 601-606. AAAI Press, MIT Press, Boston, MA. [http://www.aaai.org/Papers/AAAI/1991/AAAI91-094.pdf pdf]</ref>,<br/>
a research chess program started by [[Robert Levinson]] in 1989 at [[University of California, Santa Cruz]] with the goal to create an autonomous chess learner, knowing only the rules of chess and then evolve from game to game using heuristics derived from [[Learning|machine learning]] algorithms such as [[Pattern Recognition|pattern recognition]], [[Temporal Difference Learning|temporal difference learning]] and [[Neural Networks|neural networks]]. It uses a graph representation of chess positions and [https://en.wikipedia.org/wiki/Pattern-oriented_modeling pattern-oriented] databases in conjunction with [[Minimax|minimax]] [[Search|search]]. Research has been done by dedicated undergraduate volunteers at UCSC, most computer science students with interests in chess and [[Artificial Intelligence]] <ref>[[Daniel Walker]], [[Robert Levinson]] ('''2004'''). ''The MORPH Project in 2004''. [[ICGA Journal#27_4|ICGA Journal, Vol. 27, No. 4]]</ref>.

=Morph's History=
==Morph I/II==
The project began with the goal of developing a chess program that conformed more to [[Cognition|cognitive models]] of human chess playing than conventional chess programs. The key idea was to make the program adaptive and pattern-oriented, limited to searching only one [[Ply|ply]] and to acquiering its own chess knowledge through experience - assisted by a human-designed graph-theoretic representation language for chess patterns.

Morph stores its experience as <pattern, weight> pairs (pws). Morph's pattern are directed graphs where the nodes represent pieces and squares [[King Pattern|sorrounding the king]] and the edges represent ([[X-ray Attacks (Bitboards)|X-ray]]) attacks or defenses. To [[Evaluation|evaluate]] a position, Morph finds which graphs in the database match that position and then combines the weights associated with each graph. At the end of each game, Morph uses [[Temporal Difference Learning|temporal difference learning]] to adjust the weights of the pattern that match each position in the game. In addition, Morph creates new patterns that should enable it to determine more accurately the value of that or similar positions should it occur in the future.

The utility of pattern can be measured by the variance in its sequence of weights, which is maintained incrementally by storing the number of updates and accumulating the absolute value of their weight changes, used to decide whether patterns are deleted. After training and improving in about 3000 to 4000 games against [[GNU Chess]], Morph '''I''' was able to defeat human chess novices while searching just one ply <ref>[[Robert Levinson]], [[John Amenta]] ('''1993'''). ''MORPH, An Experience-Based Adaptive Chess System''. [[ICGA Journal#16_1|ICCA Journal, Vol. 16, No. 1]]</ref> <ref>[[Jonathan Allen]], [[Edward Hamilton]], [[Robert Levinson]] ('''1997'''). ''New Advances in Adaptive Pattern-Oriented Chess''. [[Advances in Computer Chess 8]]</ref>. Morph '''II''' is a generalization of Morph's learning and pattern representation to be applicable to most two-player [[Games|games]] and search problems given the rules of those domains.

==Morph III/IV==
The Morph III architecture allows for any reasonable number of knowledge sources to be used, a concept similar to that of advisors in the ''Hoyle'' system by [[Susan L. Epstein]] <ref>[[Susan L. Epstein]] ('''1992'''). ''[http://onlinelibrary.wiley.com/doi/10.1002/int.4550070606/abstract Prior Knowledge Strengthens Learning to Control Search in Weak Theory Domains]''. [http://eu.wiley.com/WileyCDA/WileyTitle/productCd-INT.html International Journal of Intelligent Systems], Vol. 7, No. 6</ref>. Compared to Morph I which had a bag of pattern, Morph's representation shifted towards learning internal weights. Morph '''III''' and Morph '''IV''' used [https://en.wikipedia.org/wiki/Nearest_neighbor_search nearest neighbor] and [https://en.wikipedia.org/wiki/Decision_tree decision trees] to divide positions into [https://en.wikipedia.org/wiki/Equivalence_class equivalence classes] and query them on-line in logarithmic time. However these approaches require a large amount of training data to achieve reasonable levels of play.

==Morph V==
Latest Morph, as mentioned in 2004 <ref>[[Daniel Walker]], [[Robert Levinson]] ('''2004'''). ''The MORPH Project in 2004''. [[ICGA Journal#27_4|ICGA Journal, Vol. 27, No. 4]]</ref>, uses a unique chess board representation called [[Connectivity#ChessNeighborhood|Chess Neighborhood]] <ref>[[Robert Levinson]], [[Ryan Weber]] ('''2000'''). ''[http://link.springer.com/chapter/10.1007/3-540-45579-5_9 Chess Neighborhoods, Function Combination, and Reinforcement Learning]''. [[CG 2000]], [https://users.soe.ucsc.edu/~levinson/Papers/CNFCRL.pdf pdf]</ref> and uses a [[Neural Networks|regression network]] to learn nonlinear combinations of the individual values of pieces that make up a piece neighborhood to arrive at a single value for the entire neighborhood. A vector of 64 neighborhoods of each square is suited to serve as an input layer of the regression network, whose weights are optimized by [https://en.wikipedia.org/wiki/Gradient_descent gradient descent], along with training positions previously generated using [[Temporal Difference Learning|temporal difference learning]]. At the lower level the expected probability of winning of the neighborhoods are learned and at the top they are combined based on their product and [https://en.wikipedia.org/wiki/Entropy_%28information_theory%29 entropy].
[[FILE:ChessNeighbourhood.jpg|none|border|text-bottom]]
The overall model of the [[Morph]] learner <ref>Image Fig. 5.3 on pg. 13 from [[Robert Levinson]], [[Ryan Weber]] ('''2000'''). ''[http://link.springer.com/chapter/10.1007/3-540-45579-5_9 Chess Neighborhoods, Function Combination, and Reinforcement Learning]''. [[CG 2000]], [https://users.soe.ucsc.edu/~levinson/Papers/CNFCRL.pdf pdf]</ref>

=See also=
* [[Neural Networks#engines|Chess Engines with Neural Networks]]
* [[Learning#Programs|Learning Chess Programs]]
* [[Morphy]]

=Publications=
==1989==
* [[Robert Levinson]] ('''1989'''). ''A Self-Learning, Pattern-Oriented Chess Program''. [[WCCC 1989#Workshop|WCCC 1989 - Workshop on New Directions in Game-Tree Search]]
* [[Robert Levinson]] ('''1989'''). ''A Self-Learning, Pattern-Oriented Chess Program''. [[ICGA Journal#12_4|ICCA Journal, Vol. 12, No. 4]]
==1990 ...==
* [[Robert Levinson]], [[Brian Beach]], [[Richard Snyder]], [[Tal Dayan]], [[Kirack Sohn]] ('''1990'''). ''Adaptive-predictive game-playing programs''. [http://portal.acm.org/citation.cfm?id=902787&jmp=abstract&coll=GUIDE&dl=GUIDE&CFID=78059366&CFTOKEN=89563212#abstract abstract]
* [[Robert Levinson]] ('''1991'''). ''A Self-Organizing Pattern Retrieval System and its Applications''. International Journal of Intelligent Systems, Vol. 6, pp. 717-738. ISSN 0884-8173.
* [[Robert Levinson]], [[Richard Snyder]] ('''1991'''). ''Adaptive Pattern-Oriented Chess''. Proceedings of the 8th International Workshop on Machine Learning (eds. L. Birnbaum and G. Collins), pp. 85-89. Morgan Kaufmann, San Mateo, CA. Also published in: Proceedings of the Ninth National Conference on Artificial Intelligence AAAI-91, pp. 601-606. AAAI Press, MIT Press, Boston, MA. [http://www.aaai.org/Papers/AAAI/1991/AAAI91-094.pdf pdf]
* [[Robert Levinson]], [[John Amenta]] ('''1993'''). ''MORPH, An Experience-Based Adaptive Chess System''. [[ICGA Journal#16_1|ICCA Journal, Vol. 16, No. 1]] <ref>reprinted in [http://www.computerhistory.org/chess/full_record.php?iid=doc-431614f6cc6e9 The 23rd ACM International Computer Chess Championship] from [[The Computer History Museum]], [http://archive.computerhistory.org/projects/chess/related_materials/text/3-1%20and%203-2%20and%203-3%20and%204-3.1993_23rd_ACM_ICCC/1993%20ICCC.062303066.sm.pdf pdf]</ref>
* [[Robert Levinson]], [[Richard Snyder]] ('''1993'''). ''Distance: Toward the Unification of Chess Knowledge''. [[ICGA Journal#16_3|ICCA Journal, Vol. 16, No. 3]] » [[WCCC 1992#Workshop|WCCC 1992 - Workshop]]
* [[Jeffrey Gould]], [[Robert Levinson]] ('''1994'''). ''Experience-Based Adaptive Search''. Machine Learning: A Multi-Strategy Approach (eds. R. Michalski and G. Tecuci), Vol. 4
* [[Robert Levinson]], [[Gil Fuchs]] ('''1994'''). ''A Pattern-Weight Formulation of Search Knowledge''. UCSC-CRL-94-10, [http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.35.1027 CiteSeerX]
* [[Robert Levinson]] ('''1994'''). ''[https://www.soe.ucsc.edu/research/technical-reports/UCSC-CRL-94-22 Morph II: A Universal Agent: Progess Report and Proposal]''. UCSC-CRL-94-22
* [[Robert Levinson]] ('''1996'''). ''[http://onlinelibrary.wiley.com/doi/10.1111/j.1467-8640.1996.tb00257.x/abstract General Game-Playing and Reinforcement Learning]''. [http://dblp.uni-trier.de/db/journals/ci/ci12.html#PellEL96 Computational Intelligence, Vol. 12], No. 1
* [[Jonathan Allen]], [[Edward Hamilton]], [[Robert Levinson]] ('''1997'''). ''New Advances in Adaptive Pattern-Oriented Chess''. [[Advances in Computer Chess 8]]
==2000 ...==
* [[Robert Levinson]], [[Ryan Weber]] ('''2000'''). ''Pattern-Level Temporal Difference-Learning, Data Fusion and Chess''. In Sensor Fusion: Architecture, Algorithms, and Applications IV. Orlando, Florida, April 2000
* [[Robert Levinson]], [[Ryan Weber]] ('''2000'''). ''[http://link.springer.com/chapter/10.1007/3-540-45579-5_9 Chess Neighborhoods, Function Combination, and Reinforcement Learning]''. [[CG 2000]], [https://users.soe.ucsc.edu/~levinson/Papers/CNFCRL.pdf pdf]
* [[Daniel Walker]], [[Robert Levinson]] ('''2004'''). ''The MORPH Project in 2004''. [[ICGA Journal#27_4|ICGA Journal, Vol. 27, No. 4]]

=Forum Posts=
* [https://groups.google.com/d/msg/rec.games.chess.computer/HD_Wk587W7U/4LNWdcyeplEJ Computer learning chess from scratch? Morph?] by John Michael Sauder, [[Computer Chess Forums|rgcc]], April 16, 1996
* [https://www.stmintz.com/ccc/index.php?id=72802 morph(C) on ICC] by Jeff Anderson, [[CCC]], October 11, 1999
: [https://www.stmintz.com/ccc/index.php?id=72897 Re: morph(C) on ICC] by [[Robert Hyatt]], [[CCC]], October 12, 1999
: [https://www.stmintz.com/ccc/index.php?id=73074 morph(C) -- can this really work ?] by [[Georg von Zimmermann]], [[CCC]], October 13, 1999
* [https://www.stmintz.com/ccc/index.php?id=324534 Morph lll] by K. Burcham, [[CCC]], October 29, 2003
* [http://www.talkchess.com/forum/viewtopic.php?start=8&t=19381 Re: learning] by [[Denis Mendoza|Denis P. Mendoza]], [[CCC]], February 03, 2008
: [http://www.talkchess.com/forum/viewtopic.php?topic_view=threads&p=172566 Re: learning] by [[Shivkumar Shivaji]], [[CCC]], February 03, 2008

=External Links=
==Chess Program==
* [http://satirist.org/learn-game/projects/morph.html the Morph project] by [[Jay Scott]]
* [http://www6.chessclub.com/activities/finger.php?handle=morph2 Finger morph2] @ [[Internet Chess Club|ICC]]
* [http://www1.ucsc.edu/oncampus/currents/97-05-05/chess.htm "Deep Blue" inspires deep thinking about artificial intelligence by computer scientist] by [http://scicom.ucsc.edu/faculty/ Robert Irion], [http://www1.ucsc.edu/oncampus/currents/97-05-05/index.html CURRENTS, University of California, Santa Cruz] , May 5, 1997 <ref>[[Robert Levinson]], [[Jeff Wilkinson]] ('''1997'''). ''[https://www.semanticscholar.org/paper/Deep-Blue-is-Still-an-Infant-Levinson-Wilkinson/3ce74263ef7b5d04fdf709b2dd3a519d780ae47f Deep Blue is Still an Infant]''. [[AAAI]] Technical Report WS-97-04</ref> » [[Deep Blue]]
==Misc==
* [https://en.wiktionary.org/wiki/morph morph - Wiktionary]
* [https://en.wiktionary.org/wiki/-morph -morph - Wiktionary]
* [http://membean.com/wrotds/morph-shape Word Root Of The Day: morph | Membean]
* [https://en.wikipedia.org/wiki/Morph Morph from Wikipedia]
* [https://en.wikipedia.org/wiki/Muller's_morphs Muller's morphs from Wikipedia] (amorph, hypomorph, hypermorph, antimorph and neomorph)
* [https://en.wikipedia.org/wiki/Morpheme Morpheme from Wikipedia]
* [https://en.wikipedia.org/wiki/Morphine Morphine from Wikipedia]
* [https://en.wikipedia.org/wiki/Morphing Morphing from Wikipedia]
* [https://en.wikipedia.org/wiki/Morphism Morphism from Wikipedia]
: [https://en.wikipedia.org/wiki/Morphism_of_algebraic_varieties Morphism of algebraic varieties from Wikipedia]
: [https://en.wikipedia.org/wiki/Homomorphism Homomorphism from Wikipedia]
: [https://en.wikipedia.org/wiki/Isomorphism Isomorphism from Wikipedia]
: [https://en.wikipedia.org/wiki/Isomorph Isomorph from Wikipedia]
* [https://en.wikipedia.org/wiki/Morphology Morphology from Wikipedia]
: [https://en.wikipedia.org/wiki/Galaxy_morphological_classification Galaxy morphological classification from Wikipedia]
: [https://en.wikipedia.org/wiki/Mathematical_morphology Mathematical morphology from Wikipedia]
* [https://en.wikipedia.org/wiki/Metamorphosis Metamorphosis from Wikipedia]
* [https://en.wikipedia.org/wiki/Donald_Fagen Donald Fagen] - [https://en.wikipedia.org/wiki/Morph_the_Cat Morph the Cat] (2006), [https://en.wikipedia.org/wiki/YouTube YouTube] Video
: {{#evu:https://www.youtube.com/watch?v=qgfi6pbW-BQ|alignment=left|valignment=top}}

=References=
<references />

'''[[Engines|Up one Level]]'''

Navigation menu