A Few Notes on the Runtime Complexity of Latin Hypercube Sampling

\(
\def\myT{\mathsf{T}} \def\myPhi{\mathbf{\Phi}} \)

Recently, I had to tune several parameters of an simple algorithm (in total 5 parameters). In order to explore the parameter space I decided to use a Latin Hypercube Sampling (LHS) design. Since each design point could be evaluated fairly quickly, a total number of 1000 design points appeared to be reasonable. In R, one could simply use the function optimumLHS from the lhs package. However, when running the function for points, you will notice that the function does not return, even after a few minutes. The problem lies in the runtime complexity of the LHS algorithm.

Read more

Vectorizing Summations and Matrix Identities

\(
\let\vec\mathbf \def\myT{\mathsf{T}} \def\matr#1{\mathbf #1} \def\tp{\mathsf T} \)

In this post we collect various matrix identities and rules which allow to vectorize many operations and simplify expressions.

Read more

The Weighted Linear Least Squares Algorithm

\(
\def\myT{\mathsf{T}} \def\myPhi{\mathbf{\Phi}} \)

In this blog post we are going to take a look at the so called weighted linear least squares estimator, which is very similar to the ordinary linear least squares, but with one slight modification: while the ordinary estimator assumes that the errors of all data points have the same variance (which is typically referred to as homoscedasticity) and therefore assigns the same weight to the errors in the objective function, the weighted counterpart allows us to weight every single error individually. This is especially then interesting in cases, where we are working in a heteroscedastic setting, hence, when the variability in the errors cannot be assumed to be the same.

Read more

This post is the 7th part of a series of 7 articles:

  1. Constructing Agents for Connect-4: Initial Notes
  2. Constructing Agents for Connect-4: Tree Search Algorithms
  3. Constructing Agents for Connect-4: Board Representations
  4. Constructing Agents for Connect-4: Move Ordering
  5. Constructing Agents for Connect-4: Transposition Tables
  6. Constructing Agents for Connect-4: Opening Databases
  7. Constructing Agents for Connect-4: Final Considerations

In this blog post a few additional methods are described which can be used to speed up the tree search for a Connect-4 agent slightly. We begin by looking at how to determine the game theoretical values (true values) of inner nodes of the search tree.

Read more

This post is the 6th part of a series of 7 articles:

  1. Constructing Agents for Connect-4: Initial Notes
  2. Constructing Agents for Connect-4: Tree Search Algorithms
  3. Constructing Agents for Connect-4: Board Representations
  4. Constructing Agents for Connect-4: Move Ordering
  5. Constructing Agents for Connect-4: Transposition Tables
  6. Constructing Agents for Connect-4: Opening Databases
  7. Constructing Agents for Connect-4: Final Considerations

As with many other games, the further course and outcome of a game for Connect-4 is already dependent on the opening phase. For example, the 1st player must place his first stone in the middle column to win the game. In all other cases, only a draw is reached or the game is even lost. For this reason, a strong player must be able to control the opening in order to avoid own mistakes and to be able to punish the opponent’s mistakes immediately. Often, however, it is very difficult to analyze the positions of the opening phase, because a high search depth is necessary to determine the exact game theoretical values.
In order to master the opening phase, many games therefore use opening books, which usually were created with high computing effort. These can typically give the computer program an advantage and save a lot of computing time during the opening phase. For games like Connect-4, there is another advantage: During the course of the game, the state space decreases further and further, so that after leaving the opening book, individual positions can often be correctly evaluated without further assistance and in acceptable time.

Read more