25,161
edits
Changes
no edit summary
'''[[Main Page|Home]] * [[Search]] * Proof-Number Search'''
[[FILE:Tree Nursery, Paul Klee, 1929, oil on incised gesso on canvas (detail) - Phillips Collection - DSC04897.JPG|border|right|thumb|[[Arts#:Category:Paul Klee|Paul Klee]] - Tree Nursery <ref>[[Arts#:Category:Paul Klee|Paul Klee]] - Tree Nursery, [https://en.wikipedia.org/wiki/The_Phillips_Collection The Phillips Collection], [https://en.wikipedia.org/wiki/Wikimedia_Commons Wikimedia Commons]</ref>]]
'''Proof-Number Search''', (Pn-Search, PnS, PNS)<br/>
a [[Best-First|best-first]] [https://en.wikipedia.org/wiki/And%E2%80%93or_tree and-or tree] search algorithm designed by [[Victor Allis]] for finding the game-theoretical value in game trees <ref>[[Victor Allis]] ('''1994'''). ''Searching for Solutions in Games and Artificial Intelligence''. Ph.D. thesis, [[Maastricht University|University of Limburg]], [http://fragrieu.free.fr/SearchingForSolutions.pdf pdf]</ref> . PNS is based on ideas derived from [[Conspiracy Number Search|conspiracy number search]]. While in cn search the purpose is to continue searching until it is unlikely that the [[Minimax|minimax]] value of the [[Root|root]] will change, PNS aims at '''proving''' the true value of the root <ref>[[Victor Allis]], [[Maarten van der Meulen]], [[Jaap van den Herik]] ('''1994'''). ''[http://www.sciencedirect.com/science/article/pii/0004370294900043 Proof-Number Search]''. [https://en.wikipedia.org/wiki/Artificial_Intelligence_%28journal%29 Artificial Intelligence], Vol. 66, No. 1</ref> .In the fall 2012 issue of the [[ICGA Journal#35_3|ICGA Journal]], about 20 years after its invention, [[Akihiro Kishimoto]], [[Mark Winands]], [[Martin Müller]] and [[Jahn-Takeshi Saito]] wrote a résumé about PNS and its variants and enhancements, considered a tribute to Victor Allis by editor [[Jaap van den Herik]] <ref>[[Akihiro Kishimoto]], [[Mark Winands]], [[Martin Müller]], [[Jahn-Takeshi Saito]] ('''2012'''). ''Game-Tree Search using Proof Numbers: The First Twenty Years''. [[ICGA Journal#35_3|ICGA Journal, Vol. 35, No. 3]]</ref> <ref>[[Jaap van den Herik]] ('''2012'''). ''All is Proof Numbers''. [[ICGA Journal#35_3|ICGA Journal, Vol. 35, No. 3]] (editorial)</ref> .
=Algorithm=
* [[I-Chen Wu]], [[Hung-Hsuan Lin]], [[Ping-Hung Lin]], [[Der-Johng Sun]], [[Yi-Chih Chan]], [[Bo-Ting Chen]] ('''2010'''). ''[http://link.springer.com/chapter/10.1007/978-3-642-17928-0_2 Job-Level Proof-Number Search for Connect6]''. [[CG 2010]]
* [[I-Chen Wu]], [[Ping-Hung Lin]] ('''2010'''). ''Relevance-Zone-Oriented Proof Search for Connect6''. [[IEEE#TOCIAIGAMES|IEEE Transactions on Computational Intelligence and AI in Games]], Vol. 2, No. 3 » [[Connect6]]
* [[Shi-Jim Yen]], [[Jung-Kuei Yang]] ('''2010'''). ''[https://www.semanticscholar.org/paper/Searching-for-Stage-Proof-Number-in-Connect6-Yen-Yang/2de70372893e8773b12391f75d2b964ea7fb6df2 Searching for Stage Proof Number in Connect6]''. [[TAAI 2010]]
* [[Tomoyuki Kaneko]] ('''2010'''). ''Parallel Depth First Proof Number Search''. [http://www.informatik.uni-trier.de/~ley/db/conf/aaai/aaai2010.html#Kaneko10 AAAI 2010]
* [[Abdallah Saffidine]], [[Nicolas Jouandeau]], [[Tristan Cazenave]] ('''2011'''). ''Solving Breakthrough with Race Patterns and Job-Level Proof Number Search''. [[Advances in Computer Games 13]] » [[Breakthrough (Game)]]
* [[Taichi Ishitobi]], [[Aske Plaat]], [[Hiroyuki Iida]], [[Jaap van den Herik]] ('''2015'''). ''Reducing the Seesaw Effect with Deep Proof Number Search''. [[Advances in Computer Games 14]]
* [[Jiaxing Song]] ('''2017'''). ''Deep df-pn and its Efficient Implementations''. [[Advances in Computer Games 15]]
* [[Chao Gao]], [[Martin Müller]], [[Ryan Hayward]] ('''2017'''). ''Focused Depth-first Proof Number Search using Convolutional Neural Networks for the Game of Hex''. [[Conferences#IJCAI2017|IJCAI 2017]]
=Forum Posts=
* [https://en.wikipedia.org/wiki/Mathematical_proof Mathematical proof from Wikipedia]
: [https://en.wikipedia.org/wiki/List_of_mathematical_proofs List of mathematical proofs from Wikipedia]
* [https://en.wikipedia.org/wiki/Automated_theorem_proving Automated theorem proving from Wikipedia]
* [https://en.wikipedia.org/wiki/Combinatorial_proof Combinatorial proof from Wikipedia]
: [https://en.wikipedia.org/wiki/Bijective_proof Bijective proof from Wikipedia]
* [https://en.wikipedia.org/wiki/Method_of_analytic_tableaux Method of analytic tableaux from Wikipedia]
==Misc==
* [[Videos#MarcusMiller:Category:Marcus Miller|Marcus Miller]] & [[Videos#HerbieHancock:Category:Herbie Hancock|Herbie Hancock's]] [[Videos#TheHeadhunters:Category:The Headhunters|Headhunters'05]] - [https://en.wikipedia.org/wiki/Thrust_%28album%29 Actual Proof], Live at [http://tokyo-jazz.com/2005/english/index.html Tokyo Jazz 2005], [https://en.wikipedia.org/wiki/YouTube YouTube] Video: feat.: [[Videos#TerriLyneCarrington:Category:Terri Lyne Carrington|Terri Lyne Carrington]], [[Videos#RoyHargrove:Category:Roy Hargrove|Roy Hargrove]], [http://www.discogs.com/artist/256492-Munyungo-Jackson Munyungo Jackson], [https://en.wikipedia.org/wiki/Lionel_Loueke Lionel Loucke], [https://en.wikipedia.org/wiki/%27Wah_Wah%27_Watson Wah Wah Watson]
: {{#evu:https://www.youtube.com/watch?v=dIWSC2uHXFA|alignment=left|valignment=top}}
* [[:Category:Herbie Hancock|Herbie Hancock]]: [https://en.wikipedia.org/wiki/The_Imagine_Project The Imagine Project] - [https://en.wikipedia.org/wiki/Thrust_%28album%29 Actual Proof], [https://en.wikipedia.org/wiki/Montreux_Jazz_Festival Montreux Jazz Festival], July 16, 2010, [https://en.wikipedia.org/wiki/YouTube YouTube] Video
: feat.: [[:Category:Tal Wilkenfeld|Tal Wilkenfeld]], [[:Category:Greg Phillinganes|Greg Phillinganes]], [[:Category:Vinnie Colaiuta|Vinnie Colaiuta]], [https://en.wikipedia.org/wiki/Lionel_Loueke Lionel Loueke]
: {{#evu:https://www.youtube.com/watch?v=teI2VkEeD3w|alignment=left|valignment=top}}
=References=
'''[[Search|Up one level]]'''
[[Category:Paul Klee]]
[[Category:The Headhunters]]
[[Category:Terri Lyne Carrington]]
[[Category:Herbie Hancock]]
[[Category:Roy Hargrove]]
[[Category:Marcus Miller]]
[[Category:Tal Wilkenfeld]]
[[Category:Greg Phillinganes]]
[[Category:Vinnie Colaiuta]]
