Project nihon ni ryuugakusei
(日本に留学生)

Starting with October 2016 I am going to Japan for 1 year with my girlfriend. Both of us got granted a student’s exchange year at the same place.

Setting
  • I will attend classes as a math undergraduate.
  • She attends classes as a math graduate student.
  • I just took my first Japanese classes this February.
  • She has more experience with the Japanese language (5 courses).
  • Our studies will be financed by the University of Graz and University of Kōbe. The funds cover the difference in living costs between Austria and Japan (housing will be more expensive in Japan). Thanks to all those institutions!
Schedule until then
  • Find appropriate classes I can attend at Kōbe University and ask for future recognition
  • I will try to finish my first and (coming) second semester in Mathematics. And finish my computer science master’s degree at TU Graz.
  • I will try to get my second course in Japanese during the summer term.
  • I will apply for a summer job for 2 months (July & August).
  • With September things get real. I will no longer live in my flat in Graz.
  • On 3rd of October we will have our first regular day at Kōbe University [math department].
  • I will return to Austria in August 2017 at the earliest (exams take place in July and August in Japan). It seems financially dull [to me] to come back to Austria at any point in time during this year.
Related work until then
  • Suspend participation in local associations (GLT, Aikikai Graz, not sure about LaTeX@Graz)
  • Reduce the amount of physical stuff I have here in Graz, store it somewhere and move out of the flat
  • Lots of planning with her – thanks sweety!
Being in Japan
  • My main focus one year abroad will be on Japanese writing, Japanese language, math and typesetting.
  • Japanese classes will be very appropriate as they are designed for exchange students with various Japanese skills. But math classes will give me a hard time. All appropriate classes for me are in Japanese.
  • I need to do at least 30 ECTS. The usual amount of ECTS per year at universities is 60 ECTS.
  • I will try to attend Aikidō classes there. Getting into a real Dōjō is supposedly difficult. But it should be easy to get into the Kōbe university Aikido club.
  • We will use the awesome train network in Japan to get around.
  • We will keep you informed about information channels, so you can reach us. But we need to organize that in the coming months.

So again: Where is Kōbe? We are close to Ōsaka, to the west (a bit to the south) of Tokyō. It takes us 3 hours with Shinkansen to get to Tokyō. And for those of you who actually cared to read that much, I have that one for you:

The Austrian flag at the Kōbe exchange programme website

Figure 1. The Austrian flag at the Kōbe exchange programme website

This is truly a great opportunity for us!
Thanks for the support we received 🙂

Project nihon ni ryuugakusei
(日本に留学生)

Paper: “Mastering the game of Go with deep neural networks and tree search”

Most recently, a paper “Mastering the game of Go with deep neural networks and tree search” was published in Nature. It describes a neural network architecture which for the first time won against a 2-dan professional Go player (Fan Hui) without handicaps achieving the title of the strongest Go engine existing. Between 5th and 15th of March 2016 a match between the engine – namely AlphaGo – and Lee Se-dol is scheduled. AlphaGo is pushed by Google.

It was difficult to me to follow the formal details lacking experience in machine learning. Here I would just like to cite the most interesting quotes:

[…] These games may be solved by recursively computing the optimal value function in a search tree containing approximately bd possible sequences of moves, where b is the game’s breadth (number of legal moves per position) and d is its depth (game length). In large games, such as chess (b ≈ 35, d ≈ 80) and especially Go (b ≈ 250, d ≈ 150), exhaustive search is infeasible, but the effective search space can be reduced by two general principles. First, […] position evaluation […] Second […] sampling actions from a policy p(a|s) that is a probability distribution over possible moves a in position s.

[…] evaluating positions using a value network, and sampling actions using a policy network.

We trained a 13-layer policy network […] from 30 million positions from the KGS Go Server.

We also tested against the strongest open-source Go program, Pachi.

The final version of AlphaGo used 40 search threads, 48 CPUs, and 8 GPUs. We also implemented a distributed version of AlphaGo that exploited multiple machines, 40 search threads, 1202 CPUs and 176 GPUs. […] The distributed version of AlphaGo was significantly stronger, winning 75% of games against single-machine AlphaGo and 100% of its games against other programs.

A policy p(a|s) is a probability distribution over legal actions a ∈ (s). A value function is the expected outcome if all actions for both players are selected according to policy p, that is, vP(s) = [zt|st = s, at…T ~ p].

Our rollout policy pΠ(a|s) contains less handcrafted knowledge than state-of-the-art Go programs.

Time controls for formal games were 1h main time plus three periods of 30s byoyomi.

The neural network architecture itself is described in the Methods Appendix. The (formal and informal) game results are provided as Data sheet. And in Methods/Evaluation a closing parenthesis is missing in the denominator of the logistic function 😉

Paper: “Mastering the game of Go with deep neural networks and tree search”

I computed M74207281

On 7th of January 2016, GIMPS found Mersenne prime number M74207281. GIMPS is a project combining efforts of a large crowd of volunteers contributing computing power and a university server combining the result – maintained by Curtis Cooper. If a number can be found satisfying the conditions of a Mersenne prime number, the number will be checked with primality tests; according to the article it took 31 days to do so.

M74207281 is specified 2274 207 281-1 and a friend of mine at GoGraz wondered how to compute this number in decimal representation. I suggested square and multiply, but wasn’t sure how long it might take.

So I implemented the exp-by-squaring-iterative algorithm on Wikipedia (didn’t thoroughly check whether it is the most efficient algorithm for this kind of problem):

package main

import (
	"log"
	"math/big"
	"os"
	"strconv"
)

var zero *big.Int
var one *big.Int
var two *big.Int
var hundred *big.Int

func init() {
	// initialize global values
	zero = big.NewInt(0)
	one = big.NewInt(1)
	two = big.NewInt(2)
	hundred = big.NewInt(100)
}

// ExpBySquaringIterative exponentiates by squaring meaning it computes x^n
// in logarithmic time in size of n
func ExpBySquaringIterative(x, n *big.Int) *big.Int {
	switch n.Cmp(zero) {
	case -1:
		x.Div(one, x)
		n.Neg(n)
	case 0:
		c := big.NewInt(1)
		return c
	}

	y := big.NewInt(1)
	for n.Cmp(one) > 0 {
		x2 := big.NewInt(0)
		x2.Set(x)

		nm := big.NewInt(0)
		if n.Bit(0) == 0 {
			x.Mul(x2, x2)
			n.Div(n, two)
		} else {
			y.Mul(x2, y)
			x.Mul(x2, x2)
			nm.Sub(n, one)
			n.Div(nm, two)
		}
	}
	return x.Mul(x, y)
}

func main() {
	if len(os.Args) == 1 {
		log.Println("usage: go run num_2n1.go <exponent>")
		log.Println("  M74207281 is given by exponent 74207281")
		os.Exit(1)
	}

	expstr := os.Args[1]
	exponent, err := strconv.Atoi(expstr)
	if err != nil {
		log.Fatal(err)
	}

	log.Println("TBD   ExpBySquaringIterative")
	result := ExpBySquaringIterative(big.NewInt(2), big.NewInt(int64(exponent)))
	result.Sub(result, one)
	log.Println("DONE  ExpBySquaringIterative")
	log.Println("TBD   computing decimal representation")
	log.Printf("2^%d - 1 = ", exponent)
	log.Println(result)
	log.Println("DONE  computing decimal representation")
}

And how long does it take to compute this number?

Computation of M74207281

Figure 1. Computation of M74207281

Was there anything interesting about it?

  • The decimal representation uses 22.4 MB memory.
  • It took 1 hour 27 minutes to compute the decimal representation. But it only takes 4 seconds to actually compute the number in binary. By far most of the hours are spent on computing the decimal string representation.
  • The builtin function Exp (you need to set m to nil) takes 1 hour 17 minutes; so it takes a little bit less time.
  • For reference, the first digits are 300376418084… and the last digits are …073391086436351 as can be seen on lcns2’s page.
I computed M74207281