5
You can integrate the PDF to a CDF F(x), then uniformly generate a random number x between 0 and 1 and choose a y such that F(y)=x as your sample. This is more or less difficult, depending on your PDF. Some PDFs have analytical solutions, others need numerical methods. For some distribution Rejection sampling works well, some distributions can be sampled ...
5
The UCT1 algorithm is actually an algorithm for a multi-armed bandit. There is a machine with several arms. At each round you pull one of the arms and get some reward. Your goal is to maximize your total reward. In this algorithm, $t$ is the round number: $t = 1$ in the first round, $t = 2$ in the second round, and so on.
When using UCT1 to perform Monte ...
5
The algorithms you are looking for are also called one-sided-error Monte Carlo algorithms.
The idea is to randomly guess a witness for the input being a YES-instance. If you find one, your answer "YES" is always correct; if you don't find one, you say "NO" even though the correct answer may be "YES" (we want to restrict the likelihood of this event). If the ...
4
This is the idea of probability amplification, in which one improves the probability of correctness of the algorithm by running it multiple times. You are talking about Monte-Carlo algorithms which have one-sided error. Lets take an example (from Wikipedia) having such a similar feature :
The Solovay–Strassen primality test is used to determine whether a
...
4
If you use a fixed seed then Monte Carlo is also repeatable. Monte Carlo sampling has the advantage that the expected number of points inside your figure is proportional to the area, which is not necessarily the case for a grid — you can come up with a contrived figure in which the grid is off by a lot, whereas random points are impossible to "fool" ...
4
Yes, ABC is a specific application of Monte Carlo method. That application is approximating likelihood functions.
Anything that happens in a computer is actually deterministic. However, ABC, like any other MCM, must have a good pseudo-random generator. There is no difference in the amount of randomness required by the methods.
Examples of Monte Carlo ...
4
Monte Carlo simulation is a method for computing a function. Simulated annealing is an optimization heuristic. Other than that, the only common thread behind these two methods is the use of randomness.
In Monte Carlo simulation, we are aiming at computing some quantity $A$ by finding an easily samplable random variable $X$ whose expectation is $A$. We ...
3
Let us compare the efficiency of both methods. The first method generates random points on the unit square $[-1,1]^2$, and checks how many of them lie inside the unit circle – the fraction should be $\pi/4$. If we sample $N$ points, our estimate has roughly normal distribution with mean $\pi/4$ and variance $\pi/4(1-\pi/4)/N$, and so we expect an error of ...
3
In principle, the problem of building an AI where this can never happen seems equivalent to the problem of building an AI that plays perfectly.
More precisely: If the AI can perfectly evaluate the value of each board position, then it is also able to play perfectly even if the adversary plays imperfectly. Conversely, if there is a situation where the AI ...
3
Issues like these are essentially solved in the MCTS itself. The principle of the algorithm is that it tries to make the best pick, rather than guaranteeing it (if done in this randomized fashion rather than a 'pure MCTS' fashion). The trees are built up out of large amounts of collected data, aggretating success rates in the nodes. Nodes that end up being ...
2
First, the algorithm should run forever; since you are going to stop when you have a correct answer. By this way you can guarantee that you never outputs a wrong answer. So, probability of error is zero.
So, the algorithm should be as following:
Algorithm LA
1) for i = 1 to infinity do
2) solMC = MC(n)
3) if solMC is correct
4) return solMC
...
2
OK, I finally fixed this issue, the right thing to do in such non-linear situation is to use simulated annealing. I am implementing a gradient guided simulated annealing, which works pretty efficiently.
Thanks for everyone who gave me suggestions and guidance to the right path!
Have fun (mixed with a lot of frustrations) with modeling!
2
It's a two-dimensional facility location problem. In this case, the optimum location is the centre of gravity (also known as the barycentre or centroid) of the locations of the houses, which is easily calculated from their co-ordinates.
2
The seed is an initial number of the pseudorandom number generator(PRNG) which is in fact fully deterministic. It returns a sequence of numbers that looks random enough for many purposes, but always generates the same sequence for given value.
In order to make simulation non-repeatable (returning always the same value) they advice different initial value ...
2
It doesn't matter what other elements are. We can assume that $k$ elements in $V$ are equal to $x$. Then the probability for a correct answer would be $k/n$ and $1-k/n$ for an incorrect answer. Then after $m$ tries, the probability of failure would be $(1-\frac{k}{n})^m$.
And the probability of success in $m$ tries is the probability of not to be failed in ...
2
Let $\alpha$ be a satisfying assignment. Suppose that it satisfies the terms $\{C_j : j \in J\}$. If you choose $C_i$ in the first step, then the probability that you choose $\alpha$ in the third step is 0 if $i \notin J$ and $2^{-(n-|C_j|)}$ if $i \in J$. Hence the probability of sampling $\alpha$, assuming there are $m$ terms, is
$$
p(\alpha) = \frac{2^{-n}...
2
A Las Vegas algorithm is one which is always correct, but is only efficient in expectation. Given two "opposite" Monte Carlo algorithm, you can create a Las Vegas algorithm by alternating both algorithms (or running them in parallel), halting whenever one of them produces a certain answer.
In the language of complexity theory, this corresponds to the ...
1
Without more details, I think it is important to precise that Pandemic is 2-4 players cooperative game. Players are allowed to discuss about strategy and share any information (even if the rules are ambigous on the possibility to share card in hand information). Moreover to achieve victory efficiently, players have to trade cards which is hard without ...
1
This result is stated in:
Kocsis, L., & Szepesvári, C. (2006, September). Bandit based monte-carlo planning. In European conference on machine learning (pp. 282-293). Springer, Berlin, Heidelberg.
It is the content of Theorems 5 & 6. Sadly there is no detailed proof for theorem 5.
The main reference for this is:
Auer, P., Cesa-Bianchi, N., & ...
1
The value of $C = \sqrt 2$ was shown to ensure the asymptotic optimality when rewards are in the $[0,1]$ range (Kocsis, Szepesvári, 2006).
In many games, that reward range is straightforward: maximum and minimum possible scores can be translated to 0 and 1 (0 could mean a loss and 1 a win).
The accuracy of this squashing seems to have a minimal impact (...
1
You can go with whatever the literature recommends is a reasonable value without knowing any specifics of your problem. Otherwise, it is perfectly possible (and even to be expected) that a good value of $C$ will depend not only on your problem, but on the details of your instances.
In general with all (meta)heuristics, a good choice of parameters comes down ...
1
You can compute the probability that outcome $e$ is the unique plurality answer, when repeating the algorithm $k$ times, as follows:
$$
\sum_{\substack{a+b+c+d+e=k \\ a,b,c,d,e \geq 0 \\ e > a,b,c,d}} \frac{n!}{a!b!c!d!e!} \left(\frac{1}{4}\right)^e \left(\frac{3}{16}\right)^{k-e}.
$$
This can be computed explicitly. When $k = 70$, the probability is ...
1
Using barycentric coordinate and keeping sum of coordinate equal to 1 do not sample a convex polytope uniformly.
import numpy as np
import matplotlib.pyplot as plt
N = 1000000 # Number of samples
V = 5 # Generate points within a V-gon
# generate columns that each sum to 1
s = np.exp(-np.random.uniform(0, 1, size=(V, N)))
s /= s.sum(axis=0)
# generate ...
1
The highlighted line basically says that time $t$ must be the first occurrence of the pair $(S_t, A_t)$ in the complete trajectory from $0$ up to and including $t$. This is why there is "first-visit" in the name of the algorithm; it only runs updates for $(S_t, A_t)$ pairs if $t$ is the first occurrence (first "visit") of a particular state-action pair in a ...
1
Partial expansion is a pruning/reduction strategy. Instead of requiring all children to be explored in selection you could set a threshold like done in "Move Count Pruning" (MCP) based on only expanding the first 10 children only. Usually you call ucb_sample if all children are explored depending on your weights.
Another example could be based on the ...
1
Your vector has n entries. If x is in the vector, then finding it when you pick a random index has probability at least 1/n (higher if there are multiple copies of x).
1
In you implementation you need to separate the game rules from the mcts search algorithm. Mcts does not need an evaluation like minimax. When calling random playouts all you need to do is keep making legal moves till the game ends and mark the playout with an outcome of win/loss.
your game rules need functions like
legal_moves, make_move, undo_move, ...
1
With each rollout the algorithm goes through steps of selection, expansion, simulation, and backpropagation. It does this incrementally one move at a time. 1 selection, 1 expansion, 1 simulation of random playouts them back propagated the values back to root. Next rollout and henceforth depending on ucb weights between exploration and exploitation.
1
Let me give you some basic principles that seem helpful for your problem:
How to estimate an expected value. You want to estimate $\mathbb{E}[Y]$. Here's a standard fact: if you can sample from the distribution of $Y$, then you can estimate $\mathbb{E}[Y]$. Concisely, what you do is sample $n$ values according to the distribution of $Y$, then take their ...
1
The most explored path will be the Nash Equilibrium, because at each step we choose the best move for each player.
The asymmetry happens at each level towards the best move for the current player, thus overall the tree will not grow asymmetrically.
Only top voted, non community-wiki answers of a minimum length are eligible
