博弈树并行搜索算法

本文分析了博弈树并行搜索算法中的主变量分裂算法的同步开锁问题。     

围棋死活问题的计算机求解

提出了一种基于搜索的围棋死活问题的求解方法，并实现了一个围棋死活问题求解程序SharpSense。对比实验表明，SharpSense的性能明显优于同类程序，对封闭围棋死活问题的解题能力达到了围棋专业棋手的水平。SharpSense还发现了围棋死活问题经典著作《围棋死活大全》中的两个错误。     

双人博弈问题中的蒙特卡洛树搜索算法的改进

蒙特卡洛树搜索(MCTS)是一种针对决策类博弈游戏,运用蒙特卡洛模拟方法进行评估博弈策略的启发式搜索算法。但是,在面对计算机围棋这种复杂的决策过程时,简单的蒙特卡洛树搜索过程往往由于计算量大,收敛速度非常慢。 由于双人博弈游戏中的蒙特卡洛树搜索不能收敛于双人博弈的最佳决策策略,因此提出蒙特卡洛树搜索结合极大极小值算法的改进算法,使得搜索结果不会因为蒙特卡洛方法的随机性而失真。为了进一步提高复杂双人博弈游戏中搜索算法的计算效率,还结合了几种常见的剪枝策略。实验结果说明,所提算法显著改进了蒙特卡洛树搜索的准确性和效率。     

面向多智能体博弈的并行蒙特卡洛树搜索算法研究

蒙特卡洛树搜索算法是一种常用的强化学习算法,博弈过程中动态空间的指数级增长是制约该算法学习效率的因素。基于并行方法对蒙特卡洛树搜索算法进行优化,提出基于胜率估值传递的并行蒙特卡洛树搜索算法。改进后的并行博弈搜索策略框架包含一个主进程和多个子进程,其中子进程用于探索,主进程根据子进程传递的胜率估值数据进行决策。结合多智能体博弈平台Pommerman进行实验验证,与传统的蒙特卡罗树搜索算法相比,并行蒙特卡罗树搜索算法有效提高了资源利用率、博弈胜率及决策效率。     

中国象棋计算机博弈关键技术分析

机器博弈被认为是人工智能领域最具挑战性的研究方向之一．国际象棋的计算机博弈已经有了很长的历史，并且经历了一场波澜壮阔的“搏杀”，“深蓝”计算机的胜利也给人类留下了难以忘怀的记忆．中国象棋计算机博弈的难度绝不亚于国际象棋，不仅涉足学者太少，而且参考资料不多．在国际象棋成熟技术的基础上，结合在中国象棋机器博弈方面的多年实践，总结出一套过程建模、状态表示、着法生成、棋局评估、博弈树搜索、开局库与残局库开发、系统测试与参数优化等核心技术要点，最后提出了当前研究的热点与方向．     

并行计算机博弈系统设计与改进

计算机博弈的核心技术是搜索。本文针对单核条件下的搜索算法、并行条件下的搜索算法两个方面进行了研究。单核搜索算法方面,简单地介绍了博弈单核条件下的选择性搜索思想,本文研究了几种已有的多核条件下博弈并行搜索方法,分析了其优劣,并针对性地提出了改进方案,给出了系统实践的结果,比较了改进方法与原有方法的效果差异。最后,本文探讨了Alpha-Beta并行搜索系统实现中一些特殊的程序设计技巧。     

一种博弈树静态估值算法——ΔFeature状态估值

在考虑下棋操作对棋盘影响的局部性后,提出了棋博弈的Δfeature状态估值算法,通过计算博弈树中相邻结点的特征变化来避免在叶结点上扫描整个棋盘,有效地减少了静态估值的时间开销。若棋子影响的局部范围足够小,还可以考虑将局部范围的所有情况列成表,以查表代替棋形匹配。ΔFeature状态估值算法也可以与其它优化博弈树搜索的方法一同使用,达到更好的效果。     

一种博弈树静态估值算法--△Feature状态估值

在考虑下棋操作对棋盘影响的局部性后,提出了棋博弈的△feature状态估值算法,通过计算博弈树中相邻结点的特征变化来避免在叶结点上扫描整个棋盘,有效地减少了静态估值的时间开销。若棋子影响的局部范围足够小,还可以考虑将局部范围的所有情况列成表,以查表代替棋形匹配。ΔAFeature状态估值算法也可以与其它优化博弈树搜索的方法一同使用,达到更好的效果。     

博弈树启发式搜索的α-β剪枝技术研究

博弈是启发式搜索的一个重要应用领域,博弈的过程可以用一棵博弈搜索树表示,通过对博弈树进行搜索求取问题的解,搜索策略常采用α-β剪枝技术。在深入研究α-β剪枝技术的基础上,提出在扩展未达到规定深度节点时,对扩展出的子节点按照估价函数大小顺序插入到搜索树中,从而在α-β剪枝过程中剪掉更多的分枝,提高搜索效率。     

Using tabu search with ranking candidate list to solve production planning problems with setups

This study considers production planning problems involving multiple products, multiple resources, multiple periods, setup times, and setup costs. It can be formulated as a mixed integer program (MIP). Solving a realistic MIP production planning problem is NP-hard; therefore, we use tabu search methods to solve such a difficult problem. Furthermore, we improve tabu search by a new candidate list strategy, which sorts the neighbor solutions using post-optimization information provided by the final tableau of the linear programming simplex algorithm. A neighbor solution with higher priority in the ranking sequence has a higher probability of being the best neighbor solution of a current solution. According to our experiments, the proposed candidate list strategy tabu search produces a good solution faster than the traditional simple tabu search. This study also suggests that if the evaluation of the entire neighborhood space in a tabu search algorithm takes too much computation and if an efficient and effective heuristic to rank the neighbor solutions can be developed, the speed of tabu search algorithm could be significantly increased by using the proposed candidate list strategy.     

Applying parallel computer systems to solve symmetric tridiagonal eigenvalue problems

A block parallel partitioning method for computing the eigenvalues of symmetric tridiagonal matrix is presented. The algorithm is based on partitioning, in a way that ensures load balance during computation. This method is applicable to both shared memory- and distributed memory-MIMD systems. Compared with other parallel tridiagonal eigenvalue algorithms existing in the literature, the proposed algorithm achieves a higher speedup of O(p) on a parallel computer with p-fold parallelism, which is linear, and the data communication between processors is less than that required for other methods. The results were tested and evaluated on an MIMD machine, and were within 62% to 98% of the predicted performance.     

Co-evolutionary algorithms to solve hierarchized Steiner tree problems in telecommunication networks

This study investigates a hierarchized Steiner tree problem in telecommunication networks. In such networks, users must be connected to capacitated hubs. Additionally, selected hubs must be connected to each other and to extra hubs, if necessary, by considering the latency of the resultant network. A connection between hubs can be considered to be a Steiner tree. This Steiner tree problem is modeled as a bi-level mathematical programming problem that considers two decision levels. In the upper-level, the allocation of users to hubs is performed to minimize the total network connection cost. The lower-level minimizes the user latency concerning the information that flows through the capacitated hubs. Further, two co-evolutionary schemes are developed to solve this bi-level model. The first scheme is an individual–population approach, whereas the second scheme is the traditional population–population approach. The first proposed algorithm exploits the structure of the problem by employing parallel computing in one of the populations. Numerical results depict the effectiveness of the proposed algorithms when the lower-level problem cannot be optimally solved efficiently. Furthermore, the advantages of the proposed schemes over an evolutionary one are exhibited. Finally, the hybridization of both co-evolutionary schemes is implemented to improve the semi-feasible solutions obtained by the second scheme, showing its effectiveness to solve the problem.     

Efficient algorithms to create and maintain balanced and threaded binary search trees

The algorithm proposed by Chang and lyengar to perfectly balance binary search trees has been modified to not only balance but also thread binary search trees. Threads are constructed in the same sequence as normal pointers during the balancing process. No extra workspace is necessary, and the running time is also linear for the modified algorithm. Such produced tree structure has minimal average path length for fast information retrieval, and threads to facilitate more flexible and efficient traversing schemes. Maintenance and manipulation of the data structure are discussed and relevant algorithms given.     

Using multiple objective tabu search and grammars to model and solve multi-objective flexible job shop scheduling problems

A linguistic-based meta-heuristic modeling and solution approach for solving the flexible job shop scheduling problem (FJSSP) is presented in this study. FJSSP is an extension of the classical job-shop scheduling problem. The problem definition is to assign each operation to a machine out of a set of capable machines (the routing problem) and to order the operations on the machines (the sequencing problem), such that predefined performance measures are optimized. In this research, the scope of the problem is widened by taking into account the alternative process plans for each part (process plan selection problem). Probabilistic selection of alternative process plans and machines are also considered. The FJSSP is presented as a grammar and the productions in the grammar are defined as controls (Baykasolu, 2002). Using these controls and Giffler and Thompson's (1960) priority rule-based heuristic along with the multiple objective tabu search algorithm of Baykasolu et al. (1999) FJSSP is solved. This novel approach simplifies the modeling process of the FJSSP and enables usage of existing job shop scheduling algorithms for its fast solution. Instead of scheduling job shops with inflexible algorithms that cannot take into account the flexibility which is available in the job shop, the present algorithm is developed which can take into account the flexibility during scheduling. Such an approach will considerably increase the responsiveness of the job shops.     

Applying genetic algorithms to game search trees

 Computer game playing is an important artificial intelligence research field in that the results can usually be applied to other related fields. One of the key computer-game-playing issues is designing effective search algorithms. Traditional search algorithms incur great temporal and spatial complexities when exploring deeply into search trees to find good next moves. Searches are thus usually not deep enough to derive good playing strategies. In this paper, we focus on one-player game search trees, and propose a genetic-algorithm-based approach to enhancing the speed and accuracy of game tree searches. Experiments show that our algorithm can improve solution accuracy and search speed.     

Coupling genetic algorithm with a grid search method to solve mixed integer nonlinear programming problems

A new hybrid algorithm is being introduced for solving Mixed Integer Nonlinear Programming ( ) problems which arise from study of many real-life engineering problems such as the minimum cost development of oil fields and the optimization of a multiproduct batch plant. This new algorithm employs both the Genetic Algorithm and a modified grid search method interfacing in such a way that the resulting hybrid algorithm is capable of solving many problems efficiently and accurately. Testings indicate that this algorithm is efficient and robust even for some ill-conditioned problems with nonconvex constraints.     

Using Constraint Satisfaction Problem approach to solve human resource allocation problems in cooperative health services

In developing countries, the increasing utilization of health services, due to a great life expectancy, is followed by a reduction in incomes from the public health system and from private insurance companies, to the payment of medical procedures. Beyond this scenery, it is mandatory an effective hospital cost control though the utilization of planning tools.This work is intended to contribute to the reduction of hospital costs, proposing a new tool for planning human resources utilization in hospital plants. Specifically, it is proposed a new tool for human resources allocation in health units. The solution to the allocation problem uses the CSP technique (Constraint Satisfaction Problem) associated with the backtracking search algorithm. With the objective of enhancing the backtracking search algorithm performance a new heuristics is proposed. Through some simulations the performance of the proposed heuristics is compared to the other heuristics previously published in literature: remaining minimum values, forward checking and grade heuristics.Another important contribution of this work is the mathematical modeling of the constraints, that could be unary, multiple, numeric and implicit constraints. In the results it is presented a case study of a human resource allocation in a cooperative health service.Based on the results, it is proposed that for a real allocation problems solution, the best approach is to combine the remaining minimum values heuristics with the grade heuristics, to select the best unit allocation to be filled, and then use the proposed heuristic to select the best physician to the chosen unit allocation. This association shows a satisfactory result for the human resource allocation problem of the case study, with an algorithm convergence time of 46.7 min with no backtracks. The same problem when manually resolved took about more than 50 h.     

Combining the principles of variable neighborhood decomposition search and the fix&optimize heuristic to solve multi-level lot-sizing and scheduling problems

In this paper a new heuristic is proposed to solve general multi-level lot-sizing and scheduling problems. The idea is to cross-fertilize the principles of the meta-heuristic Variable Neighborhood Decomposition Search (VNDS) with those of the MIP-based Fix&Optimize heuristic. This combination will make it possible to solve the kind of problems that typically arise in the consumer goods industry due to sequence-dependent setups and shifting bottlenecks. In order to demonstrate the strength of this procedure, a GLSP variant for multiple production stages is chosen as a representative. With the help of artificial and real-world instances, the quality of the solution as well as the computational performance of the new procedure is tested and compared to a standard MIP-solver.