# Tag Info

Accepted

### What is the difference between Simulated Annealing and Monte-Carlo Simulations?

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....
• 270k
Accepted

### Is there some kind of expected error margin for my Monte Carlo algorithm?

Suppose that you are trying to estimate some quantity $\mu$ by performing some random experiment $X$ with mean $\mu$ and variance $\sigma^2$. In order to obtain a better estimate, you can repeat the ...
• 270k
Accepted

### Generating values from a probability density function

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....
• 5,910
Accepted

### Approximate Bayesian Computation VS Monte Carlo Simulation

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 ...
• 608
Accepted

### Do RP algorithms exist?

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 "...
• 71.1k
Accepted

### UCT1 Algorithm: What does "total number of simulations" mean?

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 ...
• 270k

### How can we get a Las Vegas algorithm from a Monte Carlo one?

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 ...
• 289
Accepted

### How does MCTS handle games with large numbers of poor moves?

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 ...
• 322

### How to find the best exploration parameter in a Monte Carlo tree search?

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: ...
• 1,937

• 270k
Accepted

### Minimizing total distance to a point from a set of points

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 ...
• 80.4k
Accepted

### What is a proper way of solving a multibody nonlinear problem?

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 ...

### Monte Carlo: what is a seed?

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 ...
• 9,325
Accepted

### Monte Carlo algorithm: Element in array

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 ...

### What is the difference between Simulated Annealing and Monte-Carlo Simulations?

Simulated Annealing is closely related to Markov-Chain Montecarlo, and the Metropolis algorithm. The main difference is that MCMC aims to generate samples that respect and underlying distribution, ...
Accepted

### How to estimate how many assignments satisfy a given DNF formula using Monte Carlo?

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 ...
• 270k

### Generate a random magic square on a large field

Here's a decent algorithm that will quickly generate large magic squares. First Step: Establish Rows 1. Put all numbers in a bucket. 2. Loop through the rows, 0 to n. 3. Take out n (where n is the ...
• 21
Accepted

### Monte Carlo Algorithms : Are there any problems where two opposite Monte Carlo algorithms could solve it?

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 ...
• 270k
Accepted

### Pandemic board game - find all possible next 4 actions

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 ...
• 1,730

### UCT (Upper Confidence bounds applied to Trees)

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....
• 620

### Describe a Monte Carlo algorithm for the Triangle Packing problem

Koutis gives an $O^*(2^{3k})$ algorithm for the more general problem of $3$-set $k$-packing in his paper Faster algebraic algorithms for path and packing problems. This was improved by Björklund, ...
• 270k
1 vote

### Pandemic board game - find all possible next 4 actions

You didn't explain how your solution today works, so it's hard to give any concrete pointers. But more generally, in a Monte Carlo solution, you'll take random steps all the way to a terminal state (...
• 111
1 vote

### How to find the best exploration parameter in a Monte Carlo tree search?

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 ...
• 22.1k
1 vote
Accepted

### How to decrease the confidence of a Monte Carlo algorithm in its answer?

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,...
• 270k

Only top scored, non community-wiki answers of a minimum length are eligible