We consider Monte Carlo tree search problem, a variant of Min-Max tree search problem where the score of each leaf is the expectation of some Bernoulli variables and not explicitly given but can be estimated through (random) playouts. The goal of this problem is, given a game tree and an oracle that returns an outcome of a playout, to find a child node of the root which attains an approximate min-max score. This problem arises in two player games such as computer Go. We propose a simple and efficient algorithm for Monte Carlo tree search problem.

Given an integer n-dimensional lattice basis, the random sampling reduction was proven to find a short vector in arithmetic steps with an integer k, which is freely chosen by users. This paper introduces new random sampling reduction using precomputation techniques. The computation cost is almost independent of the lattice dimension number. The new method is therefore especially advantageous to find a short lattice vector in higher dimensions. The arithmetic operation number of our new method is about 20% of the random sampling reduction with 200 dimensions, and with 1000 dimensions it is less than 1% ( 1/130) of that of the random sampling reduction with representative parameter settings under reasonable assumptions.

For large circuits, vector compaction techniques could provide a faster solution for power estimation with reasonable accuracy. Because traditional sampling approach will incur useless transitions between every sampled pattern pairs after they are concatenated into a single sequence for simulation, we proposed a vector compaction method with grouping and single-sequence consecutive sampling technique to solve this problem. However, it is very possible that we cannot find a perfect consecutive sequence without any undesired transitions. In such cases, the compaction ratio of the sequence length may not be improved too much. In this paper, we propose an efficient approach to relax the limitation a little bit such that multiple consecutive sequences are allowed. We also propose an algorithm to reduce the number of sequences instead of setting the number as one to find better solutions for vector compaction problem. As demonstrated in the experimental results, the average compaction ratio and speedup can be significantly improved by using this new approach.

Equivalent-time sampling is a well-known technique to capture repetitive signals at finer time intervals than a sampling clock cycle time and it is widely used to implement waveform measurement with high time resolution. There are three techniques for implementing its time base (i.e., sequential sampling, random sampling and coherent sampling), and they have their respective advantages and disadvantages. In this paper we propose a new coherent sampling system which incorporates a pretrigger and time jitter reduction function for a fluctuating input signal which a random sampling system has, while maintaining the waveform recording efficiency of a conventional coherent sampling system. We also report on a technique for measuring a reference trigger time period accurately which is necessary to implement the proposed sampling system, and show its effectiveness through numerical calculations of its data recording time.

We explain three random sampling techniques that are simple but widely applicable for various problems involving huge data sets. The first technique is an immediate application of large deviation bounds. The second and the third ones are sequential sampling or adaptive sampling techniques. We fix one simple problem and explain these techniques by demonstrating algorithms for this problem and discussing their correctness and efficiency.

We have developed a novel method of numerical synthesis of optical waveguides, which consists of the endless loop of the random sampling of waveguide parameters, numerical analysis and the judgment of calculated result. This loop is repeated until some objective solutions satisfying required characteristics are discovered. When the structural condition is almost unknown and there is no clue to search it, this method is useful for discovering new-type waveguides, and this concept is applicable to any other devices. We applied this method to the search of new waveguide structures having multilayer claddings, and obtained many types of low loss single mode waveguides, including ARROW-type waveguides, waveguide-type polarizers and a very narrow band wavelength filter.