Changes

Jump to: navigation, search

Othello

950 bytes added, 20:59, 14 October 2019
no edit summary
[[FILE:Othello (Reversi) board.jpg|border|right|thumb|Reversi/Othello <ref>[https://en.wikipedia.org/wiki/Reversi Reversi from Wikipedia]</ref> ]]
'''Othello''', <br/>
or differing in not having a defined starting position, '''Reversi''', is a [https://en.wikipedia.org/wiki/Two-player_game two-player] [https://en.wikipedia.org/wiki/Zero-sum_%28game_theory%29 zero-sum] and [https://en.wikipedia.org/wiki/Perfect_information perfect information] [https://en.wikipedia.org/wiki/Abstract_strategy abstract strategy] [https://en.wikipedia.org/wiki/Board_game board game], usually played on a board with 8 rows and 8 columns and a set of light and a dark turnable pieces for each side. The player's goal is to have a majority of their colored pieces showing at the end of the game, turning over as many of their opponent's pieces as possible. The dark player makes the first move from the starting position, alternating with the light player. Each player has to place a piece on the board such that there exists at least one straight (horizontal, vertical, or diagonal) occupied line of opponent pieces between the new piece and another own piece. After placing the piece, the side turns over (flips, captures) all opponent pieces lying on any straight lines between the new piece and any anchoring own pieces.
|}
* [[Jean-Christophe Weill]] elaborated on [[NegaC*]] <ref>[[Jean-Christophe Weill]] ('''1991'''). ''Experiments With the NegaC* Search - An Alternative for Othello Endgame Search.'' Heuristic Programming in Artificial Intelligence 2: the second computer olympiad (eds. [[David Levy]] and [[Don Beal]]), pp. 174-188. Ellis Horwood, Chichester. ISBN 0-13-382615-5, [http://www.recherche.enac.fr/%7Eweill/publications/negac.ps.gz zipped ps] and [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.39.3189&rep=rep1&type=pdf pdf] from [http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.39.3189 CiteSeerX]</ref> and for [[Parallel Search|parallel search]] on [[ABDADA]] <ref>[[Jean-Christophe Weill]] ('''1996'''). ''[http://portal.acm.org/citation.cfm?id=228345 The ABDADA Distributed Minimax Search Algorithm]''. Proceedings of the 1996 ACM Computer Science Conference, pp. 131-138. ACM, New York, N.Y, reprinted [[ICGA Journal#19_1|ICCA Journal, Vol. 19, No. 1]], [http://www.recherche.enac.fr/%7Eweill/publications/acm.ps.gz zipped ps]</ref>.
* [[Michael Buro]] successfully implemented his [[ProbCut]] and [[ProbCut#MPC|Multi-ProbCut]] (MPC) as [[Selectivity|selective]] extension <ref>[[Michael Buro]] ('''1995'''). ''ProbCut: An Effective Selective Extension of the Alpha-Beta Algorithm.'' [[ICGA Journal#18_2|ICCA Journal, Vol. 18, No. 2]], pp. 71-76, [http://www.cs.ualberta.ca/%7Emburo/ps/probcut.pdf pdf]</ref> inside his successful Othello program ''Logistello'' <ref>[http://www.cs.ualberta.ca/%7Emburo/log.html Logistello's Homepage]</ref>, already described in his Ph.D. thesis <ref>[[Michael Buro]] ('''1994'''). ''Techniken für die Bewertung von Spielsituationen anhand von Beispielen.'' Ph.D. Thesis. [[Paderborn University of Paderborn]], Paderborn, Germany. [http://www.cs.ualberta.ca/%7Emburo/ps/mics_dis.pdf pdf] (German)</ref>.
* The ''Asycnhronous Parallel Hierarchical Iterative Deepening'' algorithm, [[APHID]] by [[Mark Brockington]] was applied to Othello as well <ref>[[Mark Brockington]], [[Jonathan Schaeffer]] ('''1996'''). ''The APHID Parallel αβ Search Algorithm''. Technical Report 96-07, Department of Computing Science, [[University of Alberta]], Edmonton, Alberta, Canada. as [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.23.8215&rep=rep1&type=pdf pdf] from [http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.23.8215 CiteSeerX]</ref> <ref>[[Mark Brockington]], [[Jonathan Schaeffer]] ('''1997'''). ''APHID Game-Tree Search''. [[Advances in Computer Chess 8]]</ref> <ref>[http://webdocs.cs.ualberta.ca/~games/aphid/index.html APHID Parallel Game-Tree Search Library]</ref> <ref>[[Mark Brockington]] ('''1998'''). ''Asynchronous Parallel Game-Tree Search''. Ph.D. Thesis, [[University of Alberta]], [http://games.cs.ualberta.ca/articles/mgb_thesis.ps.gz zipped postscript]</ref>.
* In 2011, [[Jean Méhat]] and [[Tristan Cazenave]] implemented [[Monte-Carlo Tree Search]] in parallel [[General Game Playing]], also covering Othello with promising results <ref>[[Jean Méhat]], [[Tristan Cazenave]] ('''2011'''). ''A Parallel General Game Player''. [http://www.kuenstliche-intelligenz.de/ KI Journal], Vol. 25, No. 1, [http://www.lamsade.dauphine.fr/~cazenave/papers/rootparallelggp.pdf pdf]</ref>.
[[FILE:Olympiad2017Othello10x10.jpg|none|border|text-bottom|link=http://icga.org/?page_id=2137]]
[[20th Computer Olympiad#Othello|20th Computer Olympiad, Leiden 2017]], Othello 10x10 winners, [[Shun-Chin Hsu]] (Mothello10, Bronze),<br/>[[Fabien Letouzey]] with [[WCCC 2005]] shirt (Decapus, Gold) and [[Andrew Lin]] (Deep Nikita, Silver) <ref>[http://icga.org/?page_id=2137 Events 2017: Dinner - Photo 24 of 25] by [[Jan Krabbenbos]]</ref>
 
=Othello Programs=
* [[Sanjoy Mahajan#Bill|Bill]] by [[Kai-Fu Lee]] and [[Sanjoy Mahajan]]
=See also=
* [[Donald H. Mitchell]] ('''1984'''). ''Using Features to Evaluate Positions in Experts' and Novices' Othello Games''. Masters thesis, Department of Psychology, [[Northwestern University]], Evanston, IL
==1985 ...==
* [[Kai-Fu Lee]], [[Sanjoy Mahajan]] ('''1986'''). ''[httphttps://repositorykilthub.cmu.edu/cgiarticles/viewcontent.cgi?article=2593&context=compsci BILL_a_table-based_knowledge-intensive_othello_program/6603887/1 BILL: a table-based, knowledge-intensive othello program]''. Technial Report CMU-CS-86-141, [[Carnegie Mellon University]], [https://pdfs.semanticscholar.org/f7ab/15736ecc79452aa4546cf8d7f5aa94d6afa0.pdf pdf] * [[Kai-Fu Lee]] ('''1986'''). ''[httphttps://repositorykilthub.cmu.edu/cgiarticles/viewcontent.cgi?article=2622&context=compsci A_pattern_classification_approach_to_evaluation_function_learning/6591158 A pattern classification approach to evaluation function learning]''. Technial Report CMU-CS-86-173, [[Carnegie Mellon University]]* [[Kai-Fu Lee]], [[Sanjoy Mahajan]] ('''1988'''). ''[httphttps://www.sciencedirect.com/science/article/abs/pii/0004370288900768 A Pattern Classification Approach to Evaluation Function Learning]''. [https://en.wikipedia.org/wiki/Artificial_Intelligence_%28journal%29 Artificial Intelligence], Vol. 36, No. 1
* [[Stuart Russell]], [[Eric Wefald]] ('''1988'''). ''Decision-Theoretic Search Control: General Theory and an Application to Game-Playing.'' Computer Science Division Technical Report 88/435, University of California, Berkeley, CA.
* [[Mathematician#KADeJong|Kenneth A. De Jong]], [[Mathematician#ACSchultz|Alan C. Schultz]] ('''1988'''). ''Using Experience-Based Learning in Game Playing''. Proceedings of the Fifth International Machine Learning Conference, [http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.52.5381 CiteSeerX] » [[Learning]]
* [[Greg M. Gupton]] ('''1989'''). ''Genetic Learning Algorithm Applied to the Game of Othello''. [[1st Computer Olympiad#Workshop|Heuristic Programming in AI 1]]
==1990 ...==
* [[Kai-Fu Lee]], [[Sanjoy Mahajan]] ('''1990'''). ''[httphttps://www.sciencedirect.com/science/article/abs/pii/000437029090068B The Development of a World Class Othello Program]''. [https://en.wikipedia.org/wiki/Artificial_Intelligence_%28journal%29 Artificial Intelligence], Vol. 43, No. 1
* [[Jean-Christophe Weill]] ('''1991'''). ''Experiments With the NegaC* Search - An Alternative for Othello Endgame Search.'' [[2nd Computer Olympiad#Workshop|Heuristic Programming in AI 2]]
* [[Richard Korf]] and [[Max Chickering]] ('''1994'''). ''[http://www.aaai.org/Library/AAAI/1994/aaai94-210.php Best-first minimax search: Othello results].'' Proceedings of the 13th National Conference on Artificial Intelligence (AAAI-94), pp. 1365-1370. AAAI Press, Menlo Park, CA.
* C.K. Wong, K.K. Lo and P.H.W. Leong ('''2004'''). ''[http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=1393254 An FPGA-based Othello Endgame Solver]''. [https://en.wikipedia.org/wiki/Chinese_University_of_Hong_Kong The Chinese University of Hong Kong], [http://www.cse.cuhk.edu.hk/~phwl/mt/public/archives/papers/othello_fpt04.pdf pdf]
==2005 ...==
* [[Simon Lucas]], [[Thomas Philip Runarsson]] ('''2006'''). ''[http://scholar.google.is/citations?view_op=view_citation&hl=en&user=4eWdc_sAAAAJ&citation_for_view=4eWdc_sAAAAJ:qjMakFHDy7sC Temporal Difference Learning versus Co-Evolution for Acquiring Othello Position Evaluation]''. [[IEEE#CIG|IEEE Symposium on Computational Intelligence and GamesCIG 2006]]
* [[Simon Lucas]] ('''2007'''). ''[http://scholar.google.com/citations?view_op=view_citation&hl=de&user=Jz8DDVAAAAAJ&cstart=20&citation_for_view=Jz8DDVAAAAAJ:QIV2ME_5wuYC Learning to play Othello with N-tuple systems]''. [https://www.chatbots.org/journal/australian_journal_of_intelligent_information_processing_systems/ Australian Journal of Intelligent Information Processing Systems], Special Issue on Game Technology, Vol. 9, No. 4
* [[Edward P. Manning]] ('''2007'''). ''[http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=4219046 Temporal Difference Learning of an Othello Evaluation Function for a Small Neural Network with Shared Weights]''. [[IEEE#CIG|IEEE Symposium on Computational Intelligence and AI CIG 2007]]* [[Thomas Philip Runarsson]], [https://dblp.uni-trier.de/pers/hd/j/Jonsson:Egill_Orn Egill Orn Jonsson] ('''2007'''). ''Effect of look-ahead search depth in Gameslearning position evaluation functions for Othello using -greedy exploration''. [[IEEE#CIG|IEEE CIG 2007]]
* [[Pim Nijssen]] ('''2007'''). ''Playing Othello Using Monte Carlo''. Bachelor's Thesis, [[Maastricht University]], [http://www.personeel.unimaas.nl/pim.nijssen/pub/bsc.pdf pdf]
* [[Yasuhiro Osaki]], [[Kazutomo Shibahara]], [[Yasuhiro Tajima]], [[Yoshiyuki Kotani]] ('''2008'''). ''An Othello Evaluation Function Based on Temporal Difference Learning using Probability of Winning''. [http://www.csse.uwa.edu.au/cig08/Proceedings/toc.html CIG'08], [http://www.csse.uwa.edu.au/cig08/Proceedings/papers/8010.pdf pdf]
* [[Shi-Jim Yen]], [[Tsan-Cheng Su]], [[Jr-Chang Chen]], [[Shun-Chin Hsu]] ('''2014'''). ''Solving 6x6 Othello on Volunteer Computing System''. [[Conferences#GPW|GPW-2014]]
* [[Wojciech Jaśkowski]] ('''2014'''). ''Systematic n-Tuple Networks for Othello Position Evaluation''. [[ICGA Journal#37_2|ICGA Journal, Vol. 37, No. 2]]
* [[Thomas Philip Runarsson]], [[Simon Lucas]] ('''2014'''). ''Preference Learning for Move Prediction and Evaluation Function Approximation in Othello''. [[IEEE#CIG|IEEE CIG 2014]]
==2015 ...==
* [[Mohd Nor Akmal Khalid]], [[E. Mei Ang]], [[Umi Kalsom Yusof]], [[Hiroyuki Iida]], [[Taichi Ishitobi]] ('''2015'''). ''[http://link.springer.com/chapter/10.1007%2F978-3-319-27947-3_6 Identifying Critical Positions Based on Conspiracy Numbers]''. [http://link.springer.com/book/10.1007/978-3-319-27947-3 Agents and Artificial Intelligence], [http://dblp.uni-trier.de/db/conf/icaart/icaart2015s.html#KhalidAYII15 ICAART 2015 - Revised Selected Papers]
* [[Shantanu Thakoor]], [[Surag Nair]], [[Megha Jhunjhunwala]] ('''2017'''). ''Learning to Play Othello Without Human Knowledge''. [[Stanford University]], [https://github.com/suragnair/alpha-zero-general/blob/master/pretrained_models/writeup.pdf pdf] » [[AlphaZero]], [[Monte-Carlo Tree Search|MCTS]], [[Deep Learning]] <ref>[https://github.com/suragnair/alpha-zero-general GitHub - suragnair/alpha-zero-general: A clean and simple implementation of a self-play learning algorithm based on AlphaGo Zero (any game, any framework!)]</ref>
* [[Kiminori Matsuzaki]] ('''2018'''). ''Empirical Analysis of PUCT Algorithm with Evaluation Functions of Different Quality''. [[TAAI 2018]] » [[Christopher D. Rosin#PUCT|PUCT]]
* [[Kiminori Matsuzaki]], [[Naoki Kitamura]] ('''2018'''). ''Do evaluation functions really improve Monte-Carlo tree search?'' [[CG 2018]], [[ICGA Journal#40_3|ICGA Journal, Vol. 40, No. 3]]
* [[Nai-Yuan Chang]], [[Chih-Hung Chen]], [[Shun-Shii Lin]], [[Surag Nair]] ('''2018'''). ''[https://dl.acm.org/citation.cfm?id=3278325 The Big Win Strategy on Multi-Value Network: An Improvement over AlphaZero Approach for 6x6 Othello]''. [https://dl.acm.org/citation.cfm?id=3278312 MLMI2018]
* [[Ching-Nung Lin]], [[Fabien Letouzey]], [[Shi-Jim Yen]] ('''2019'''). ''Decapus wins Othello 10 × 10 tournament''. [[ICGA Journal#41_1|ICGA Journal, Vol. 41, No. 1]] » [[21st Computer Olympiad#Othello |21st Computer Olympiad 2018]]
=Forum Posts=
* [http://www.othello.dk/book/index.php/Main_Page The Othello Wiki Book Project]
* [https://www.game-ai-forum.org/icga-tournaments/game.php?id=22 Othello (ICGA Tournaments)]
* [http://satirist.org/learn-game/systems/othello/ The strong learning Othello Programs] from [http://satirist.org/learn-game/ Machine Learning in Games] by [[Jay Scott]]
* [http://www.cs.put.poznan.pl/wjaskowski/othello-league-players Othello Players] by [[Wojciech Jaśkowski]]
* [http://radagast.se/othello/howto.html Writing an Othello program] by [[Gunnar Andersson]]
* [http://forwardcoding.com/projects/othello.html Othello] by [[Gary Linscott]]
* [http://www.aartbik.com/MISC/reversi.html Perft for Reversi/Othello] by [[Aart Bik]] » [[Perft]] <ref>[http://www.othello.dk/book/index.php/Aart_Bik Aart Bik - The Othello Wiki Book Project]</ref>
* [http://www.andreazinno.it/ Andrea Zinno's Home Page] - Entirely dedicated to the Othello game, by [[Andrea Zinno]]
* [http://members.chello.at/theodor.lauppert/games/othello.htm Othello] from [http://members.chello.at/theodor.lauppert/ Theodor Lauppert's] [http://members.chello.at/theodor.lauppert/games/ Game Gallery]
* [http://gamesmuseum.uwaterloo.ca/VirtualExhibits/Whitehill/othello/ Othello (Reversi)] from [http://www.gamesmuseum.uwaterloo.ca/index.htm Elliott Avedon Virtual Museum of Games], [[University of Waterloo]]
* [http://www.beppi.it/public/OthelloMuseum/ The Othello Museum - Home]
* [http://www.pressmangames.com/instructions/instruct_othello.html Pressman Toy Instructions for Othello]
* [http://othello.nu/wofforum/ World Othello Federation]
* [https://en.wikipedia.org/wiki/Othello_%28disambiguation%29 Othello (disambiguation) from Wikipedia]
Retrieved from "https://www.chessprogramming.org/Special:MobileDiff/2502...15013"

Navigation menu