report.bib

@article{negascout,
author = {Fishburn, John P.},
title = {An Optimization of Alpha-Beta Search},
year = {1980},
issue_date = {July 1980},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
number = {72},
issn = {0163-5719},
url = {https://doi.org/10.1145/1056447.1056450},
doi = {10.1145/1056447.1056450},
journal = {SIGART Bull.},
month = jul,
pages = {29–31},
numpages = {3}
}
@article{id,
title = {Depth-first iterative-deepening: An optimal admissible tree search},
journal = {Artificial Intelligence},
volume = {27},
number = {1},
pages = {97-109},
year = {1985},
issn = {0004-3702},
doi = {https://doi.org/10.1016/0004-3702(85)90084-0},
url = {https://www.sciencedirect.com/science/article/pii/0004370285900840},
author = {Richard E. Korf},
abstract = {The complexities of various search algorithms are considered in terms of time, space, and cost of solution path. It is known that breadth-first search requires too much space and depth-first search can use too much time and doesn't always find a cheapest path. A depth-first iterative-deepening algorithm is shown to be asymptotically optimal along all three dimensions for exponential tree searches. The algorithm has been used successfully in chess programs, has been effectively combined with bi-directional search, and has been applied to best-first heuristic search as well. This heuristic depth-first iterative-deepening algorithm is the only known algorithm that is capable of finding optimal solutions to randomly generated instances of the Fifteen Puzzle within practical resource limits.}
}
@misc{zobrist,
note={{\tt http://cr.yp.to/\allowbreak bib/\allowbreak entries.html\#\allowbreak 1970/\allowbreak zobrist}. Note: Technical Report 88, Computer Sciences Department, University of Wisconsin},
author={Albert L. Zobrist},
title={{A hashing method with applications for game playing}},
year={1970},
}
@inproceedings{scout,
author = {Pearl, Judea},
title = {Scout: A Simple Game-Searching Algorithm with Proven Optimal Properties},
year = {1980},
publisher = {AAAI Press},
abstract = {This paper describes a new algorithm for searching games which is conceptually simple,
space efficient, and analytically tractable. It possesses optimal asymptotic properties
and may offer practical advantages over α-β for deep searches.},
booktitle = {Proceedings of the First AAAI Conference on Artificial Intelligence},
pages = {143–145},
numpages = {3},
location = {Stanford, California},
series = {AAAI'80}
}
@inproceedings{quiescence,
author = {Harris, Larry R.},
title = {The Heuristic Search and the Game of Chess a Study of Quiescence, Sacrifices, and Plan Oriented Play},
year = {1975},
publisher = {Morgan Kaufmann Publishers Inc.},
address = {San Francisco, CA, USA},
abstract = {This paper describes the results of applying the formal heurisitic search algorithm
to the game of chess, and the impact of this work on the theory of heuristic search.
It is not that the application of the heuristic search can by itself solve the problems
at the heart of the computer chess, but that representing these problems within the
formalism of the heuristic search will further their common solution. A separate search
heuristic is proposed that does offer a common solution to the problems of quiescence,
sacrifices, and plan oriented play.},
booktitle = {Proceedings of the 4th International Joint Conference on Artificial Intelligence - Volume 1},
pages = {334–339},
numpages = {6},
location = {Tblisi, USSR},
series = {IJCAI'75}
}
@inproceedings{heur,
author = {Abdoulaye, Abdel-Hafiz and Houndji, Vinasetan and Ezin, Eugène and Aglin, Gael},
year = {2018},
month = {10},
pages = {},
title = {CARI2018 p265-275}
}
@article{mtdf,
title = {Best-first fixed-depth minimax algorithms},
journal = {Artificial Intelligence},
volume = {87},
number = {1},
pages = {255-293},
year = {1996},
issn = {0004-3702},
doi = {https://doi.org/10.1016/0004-3702(95)00126-3},
url = {https://www.sciencedirect.com/science/article/pii/0004370295001263},
author = {Aske Plaat and Jonathan Schaeffer and Wim Pijls and Arie {de Bruin}},
keywords = {Game-tree search, Minimax search, Alpha-Beta, SSS, Transposition tables, Null-window search, Solution trees},
abstract = {This article has three main contributions to our understanding of minimax search: First, a new formulation for Stockman's SSS∗ algorithm, based on Alpha-Beta, is presented. It solves all the perceived drawbacks of SSS∗, finally transforming it into a practical algorithm. In effect, we show that SSS∗ = Alpha-Beta + transposition tables. The crucial step is the realization that transposition tables contain so-called solution trees, structures that are used in best-first search algorithms like SSS∗. Having created a practical version, we present performance measurements with tournament game-playing programs for three different minimax games, yielding results that contradict a number of publications. Second, based on the insights gained in our attempts at understanding SSS∗, we present a framework that facilitates the construction of several best-first fixed-depth game-tree search algorithms, known and new. The framework is based on depth-first null-window Alpha-Beta search, enhanced with storage to allow for the refining of previous search results. It focuses attention on the essential differences between algorithms. Third, a new instance of this framework is presented. It performs better than algorithms that are currently used in most state-of-the-art game-playing programs. We provide experimental evidence to explain why this new algorithm, MTD(f), performs better than other fixed-depth minimax algorithms.}
}
@article{montecarlo,
author = {Bouzy, Bruno and Helmstetter, B.},
year = {2003},
month = {10},
pages = {},
title = {Monte-Carlo Go Developments},
volume = {135},
isbn = {978-1-4757-4424-8},
journal = {Advances in Computer Games},
doi = {10.1007/978-0-387-35706-5_11}
}