Home| Contact Us| New Journals| Browse Journals| Journal Prices| For Authors|

Print ISSN:
Online ISSN:


  About JIO
  DLINE Portal Home
Home
Aims & Scope
Editorial Board
Current Issue
Next Issue
Previous Issue
Sample Issue
Upcoming Conferences
Self-archiving policy
Alert Services
Be a Reviewer
Publisher
Paper Submission
Subscription
Contact us
 
  How To Order
  Order Online
Price Information
Request for Complimentary
Print Copy
 
  For Authors
  Guidelines for Contributors
Online Submission
Call for Papers
Author Rights
 
 
RELATED JOURNALS
Journal of Digital Information Management (JDIM)
Journal of Multimedia Processing and Technologies (JMPT)
International Journal of Web Application (IJWA)

 

 
Electronic Devices

The Study of the Impact of the Search Algorithms in Board Games
Jorge Hernandez, Karen Daza, Hector Florez
Universidad Distrital Francisco Jose de Caldas Bogota, Colombia
Abstract: Algorithms play a major role in games. The algorithms pass a node in the board games, the heuristic function get involved. Thus we tried to understand the evaluation process where the domain is treated. We in this current work, provided an approach to find the best movement by deploying a game tree, with an implementation for the board game called Othello. To study the desired factors and the best movement is obtained through an in-depth search, according to the designed heuristic. We experimented with two algorithms. The former is Mini-Max and its evolution to Alpha-Beta. The latter is Scout, which presents better performance regarding time. In addition, we present the results, rules, and implementation features.
Keywords: Board Games, Search Algorithms, Scout Algorithm, Artificial Intelligence, Game Tree, Alpha-Beta Pruning The Study of the Impact of the Search Algorithms in Board Games
DOI:https://doi.org/10.6025/ed/2020/9/1/1-12
Full_Text   PDF 960 KB   Download:   366  times
References:

[1] Bentivegna, D.C., Atkeson, C.G. (2002). A framework for learning from observation using primitives. Robot Soccer World Cup. p 263–270. Springer.
[2] Buro, M. (1998). From simple features to sophisticated evaluation functions. In: International Conference on Computers and Games. p 126–145. Springer.
[3] Buro, M. (2002). Improving heuristic mini-max search by supervised learning. Artificial Intelligence, 134(1-2), 85–99 (2002)
[4] Duarte, V.A.R., Julia, R.M.S. (2012). Mp-draughts: Ordering the search tree and refining the game board representation to improve a multi-agent system for draughts. In: 2012 IEEE 24th International Conference on Tools with Artificial Intelligence. volume 1, p. 1120–1125. IEEE.
[5] Geissmann, C. (2015). Learning heuristic functions in classical planning
[6] Iwata, S., Kasai, T. (1994). The othello game on an n× n board is pspace-complete. Theoretical Computer Science, 123 (2), 329–340.
[7] Knuth, D.E., Moore, R.W. (1975). An analysis of alpha-beta pruning. Artificial intelligence, 6 (4), 293–326.
[8] Kuhlmann, G., Stone, P. (2006). Automatic heuristic construction in a complete general game player. AAAI. volume 6, p 1457– 1462.
[9] Liskowski, P., Ja´skowski, W., Krawiec, K. (2018). Learning to play othello with deep neural networks. IEEE Transactions on Games, 10 (4) 354–364.
[10] Mejia-Moncayo, C., Rojas, A.E., Dorado, R. (2017). Manufacturing cell formation with a novel discrete bacterial chemotaxis optimization algorithm. In: Figueroa-Garc´ýa, J.C., L´opez-Santana, E.R., Villa-Ram´ýrez, J.L., Ferro-Escobar, R. (eds.) Applied Computer Sciences in Engineering. p, 579–588. Springer International Publishing, Cham.
[11] Ne¡si´c, N., Schiffel, S. (2016). Heuristic function evaluation framework. In: International Conference on Computers and Games. p 71–80. Springer.
[12] Noe, T. D. (1980). A comparison of the Alpha-Beta and SCOUT algorithms using the game of Kalah. University of California, School of Engineering and Applied Science.
[13] Pearl, J. (1980). Scout: A simple game-searching algorithm with proven optimal proper- ties. AAAI. p 143–145.
[14] Plaat, A., Schaeffer, J., Pijls, W., De Bruin, A. (1996). Exploiting graph properties of game trees. AAAI/IAAI, Volume 1. 12 Electronic Devices Volume 9 Number 1 March 2020 p 234–239.
[15] Saffidine, A., Finnsson, H., Buro, M. (2012). Alpha-beta pruning for games with simultaneous moves. In: Twenty-Sixth AAAI Conference on Artificial Intelligence.
[16] Sanchez, D., Florez, H. (2018). Improving game modeling for the quoridor game state using graph databases. In: International Conference on Information Theoretic Security. p. 333–342. Springer.
[17] Sannidhanam, V., Annamalai, M. (1996). An analysis of heuristics in othello Schaeffer, J., Plaat, A.: New advances in alpha-beta searching. In: ACM Conference on Computer science. p 124–130. Citeseer.
[19] Schiffel, S., Thielscher, M. (2006). Automatic construction of a heuristic search function for general game playing. Department of Computer Science, p. 16–17.
[20] Sephton, N., Cowling, P.I., Powley, E., Slaven, N.H. (2014). Heuristic move pruning in monte carlo tree search for the strategic card game lords of war. In: 2014 IEEE Conference on Computational Intelligence and Games. p. 1–7. IEEE (2014)
[21] Wu, P.h., Liu, P.Y., Hsu, T.s. (2004). An external-memory retrograde analysis algorithm. In: International Conference on Computers and Games. p. 145–160. Springer.


Home | Aim & Scope | Editorial Board | Author Guidelines | Publisher | Subscription | Previous Issue | Contact Us |Upcoming Conferences|Sample Issues|Library Recommendation Form|

 

Copyright © 2011 dline.info