Searching minimax game trees under memory space constraint

Games such as CHESS, GO and OTHELLO can be represented by minimax game trees. Among various search procedures to solve such game trees,- and SSS^* are perhaps most well known. Although it is proved that SSS^* explores only a subset of the nodes explored by-, - is commonly believed to be faster in real applications, since it requires very little memory space and hence its storage management cost is low. Contrary to this folklore, however, this paper reports, using the OTHELLO game as an example, that SSS^* is much faster than-. It is also demonstrated that SSS^* can be modified to make the required memory space controllable to some extent, while retaining the high efficiency of the original SSS^*.This research was partially supported by the Ministry of Education, Science and Culture of Japan, under a Scientific Grant-in-Aid.     

Effect of Elastic Energy due to Atomic Size Factor on Ordering and Decomposition Behaviour of Binary Solid Solutions

A theory recently developed by the present authors is applied to the study of the effect of elastic energy due to atomic size factor on the transformation behaviour of binary solid solutions. lt is found that elastic interaction energy (EIE), which is a part of the total elastic energy plays a key role in both ordering elastic interaction ordering (EIO) and spinodal decomposition. The present study gives a reasonable explanation to the historical dilemmas, "elastic energy paradox" and "atomic size factor paradox . By solving these confusing problems, the coexistence of ordering (EIO) and decomposition, which has been regarded as impossible by conventional theories. can be well understood. The mechanism is as follows: lowering of elastic energy demands EIO, and such an ordering provides a driving force for spinodal decomposition. Therefore, in alloys with large atomic size factor, spinodal decomposition is preceded and induced by ordering. Ordering and spinodal decomposition are thus closely related processes to each other     

Solving the irregular strip packing problem via guided local search for overlap minimization

The irregular strip-packing problem (ISP) requires a given set of non-convex polygons to be placed without overlap within a rectangular container having a fixed width and a variable length, which is to be minimized. As a core sub-problem to solve ISP, we consider an overlap minimization problem (OMP) whose objective is to place all polygons into a container with given width and length so that the total amount of overlap between polygons is made as small as possible. We propose to use directional penetration depths to measure the amount of overlap between a pair of polygons, and present an efficient algorithm to find a position with the minimum overlap for each polygon when it is translated in a specified direction. Based on this, we develop a local search algorithm for OMP that translates a polygon in horizontal and vertical directions alternately. Then we incorporate it in our algorithm for OMP, which is a variant of the guided local search algorithm. Computational results show that our algorithm improves the best-known values of some well-known benchmark instances.     

Theoretical comparisons of search strategies in branch-and-bound algorithms

Four known search strategies used in branch-and-bound algorithms-heuristic search, depth-first search, best-bound search, and breadth-first search-are theoretically compared from the viewpoint of the performance of the resulting algorithms. Heuristic search includes the other three as special cases. Since heuristic search is determined by a heuristic functionh, we first investigate how the performance of the resulting algorithms depends onh. In particular, we show that heuristic search is stable in the sense that a slight change inh causes only a slight change in its performance. The best and the worst heurstic functions are clarified, and also discussed is how the heuristic functionh should be modified to obtain a branch-and-bound algorithm with an improved performance. Finally, properties and limitations of depth-first search, best-bound search, and breadth-first search viewed as special cases of heuristic search are considered. In particular, it is shown that the stability observed for heuristic search no longer holds for depth-first search.     

Construction of an error map of rotary axes on a five-axis machining center by static R-test

This paper proposes an efficient and automated scheme to calibrate error motions of rotary axes on a five-axis machining center by using the R-test. During a five-axis measurement cycle, the R-test probing system measures the three-dimensional displacement of a sphere attached to the spindle in relative to the machine table. Location errors, defined in ISO 230-7, of rotary axes are the most fundamental error factors in the five-axis kinematics. A larger class of error motions can be modeled as geometric errors that vary depending on the angular position of a rotary axis. The objective of this paper is to present an algorithm to identify not only location errors, but also such position-dependent geometric errors, or “error map,” of rotary axes. Its experimental demonstration is presented.     

Quantitative evaluation of display characteristics of AMOLED displays

Abstract— Understanding the display characteristics of OLEDs is not only of general interest but also of technological importance for expanding the application of OLEDs. The display characteristics of AMOLEDs were quantitatively evaluated and compared with LCD or CRT performance. The fast response time and high contrast ratio, which are attractive characteristics of OLEDs, were also retained under low temperature and bright ambient, respectively. Moreover the luminance and color barely changed with viewing angle at any gray‐scale level. The optical design of OLED diodes is important for the emission characteristics, luminance, and color reproducibility.     

Graft copolymerization of glass fiber and its application

Modified glass fibers, containing unsaturated hydrocarbon surface groups, were prepared by a hydrothermal treatment, with allylglycidylether in excess as reagent. Graft polymerization of the treated glass fiber with styrene and methylmethacrylate was carried out in sealed tubes, under nitrogen, using benzoyl peroxide (BPO) and cumene hydroperoxide (CHPO) as initiators. When BPO was used as the initiator, the grafting efficiency was extremely low, but the graft copolymerization behavior was similar to that of usual organic polymers. With CHPO, both grafting ratio and grafting efficiency were very high. Various properties of composite materials containing grafted glass cloth were studied. Flexural strength, flexural modulus, and interlaminar shear strength increased proportionally to the increase of the grafting ratio; the same values were decreased only in a small extent after the boiling test.     

On the efficiency of cautious schedulers for database concurrency control—Why insist on two-phase locking?

Thecautious scheduler, recently proposed for the concurrency control of database systems, never resorts to abortions or rollbacks for the purpose of concurrency control. The comprehensive performance evaluation study among different cautious schedulers and conventional non-cautious schedulers, however, has not yet been attempted. In this paper, we consider five scheduling algorithms and investigate their performance by means of simulation studies. Two of these algorithms are non-cautious; that is, thetwo-phase locking algorithm (2PL) (the most popular transaction scheduling algorithm in practical systems) and theconflict serializable algorithm (CSR) (a typical scheduling algorithm among those not using a locking mechanism; also calledD-serializable algorithm, conflict preserving serializable algorithm, orWW-serializable algorithm). The others are cautious scheduling algorithms modified from the above2PL andCSR; that is,cautious two-phase locking algorithm (C2PL), exclusive preclaimed two-phase locking algorithm (EP2PL), andcautious conflict serializable algoritm (CCSR). The results demonstrate the superiority of the cautious conflict serializable algorithm over the conventional two-phase locking algorithm, especially in the on-line system environment.This work was supported in part by the Ministry of Education, Science and Culture of Japan under Scientific Research Grant-in-Aid and in part by the Advancd Systems Foundations of British Columbia, Canada.     

Chain packing in graphs

This paper discusses the complexity of packingk-chains (simple paths of lengthk) into an undirected graph; the chains packed must be either vertex-disjoint or edge-disjoint. Linear-time algorithms are given for both problems when the graph is a tree, and for the edge-disjoint packing problem when the graph is general andk = 2. The vertex-disjoint packing problem for general graphs is shown to be NP-complete even when the graph has maximum degree three andk = 2. Similarly the edge-disjoint packing problem is NP-complete even when the graph has maximum degree four andk = 3.     

A Simplified Õ(nm) Time Edge-Splitting Algorithm in Undirected Graphs

Let G=(V,E) be a multigraph which has a designated vertex s ∈ V with an even degree. For two edges e ₁ = (s,u ₁ ) and e ₂ = (s,u ₂ ) , we say that a multigraph G' is obtained from G by splitting e ₁ and e ₂ at s if two edges e ₁ and e ₂ are replaced with a single edge (u ₁ ,u ₂ ) . It is known that all edges incident to s can be split without losing the edge-connectivity of G in V-s . This complete splitting plays an important role in solving many graph connectivity problems. The currently fastest algorithm for a complete splitting [14] runs in O(n(m+n log n) log n) time, where n = |V| and m is the number of pairs of vertices between which G has an edge. Their algorithm is first designed for Eulerian multigraphs, and then extended for general multigraphs. Although the part for Eulerian multigraphs is simple, the rest for general multigraphs is considerably complicated. This paper proposes a much simpler O(n(m+n log n) log n) time algorithm for finding a complete splitting. A new edge-splitting theorem derived from our algorithm is also presented. Received March 13, 1997; revised October 10, 1997.