Einträge über Code & Zahlen (Ältere Einträge, Seite 32)

Recht früh habe ich begonnen mit Computern zu beschäftigen, die Physik kam dann auch dazu. Im Physikstudium habe ich mich auf die Schnittmenge spezialisiert, die Computerphysik. Viele Dinge nehme ich nun mit dem Blick eines Naturwissenschaflers und Softwareentwicklers wahr. Entsprechend sind die Artikel in dieser Kategorie über Programmiersprachen, von mir geschriebene oder genutzte Software, Physik, quantitative Untersuchungen von Finanzthemen und weitere Dinge dieser Art.

Meinen Code findet man auf GitHub, meine dummen Fragen auf Stack Overflow. Auf Physics Stack Exchange habe ich auch einige Fragen gestellt und beantwortet.

Meine wissenschaftlichen Artikel aus der Studienzeit findet man auf arXiv und ORCID.


Monte Carlo Tree Search for Railroad Ink

In a recent post I looked at the game “Railroad Ink” and how applying a backtracking algorithm to it. Then I have written another post about refactoring that into a tree search library and also have applied a random walk algorithm to Railroad Ink. Then in yet another post I have implemented Monte Carlo tree search (MCTS) and applied it to Tic-Tac-Toe. This algorithm is now also part of the tree search library and can be applied to Railroad Ink. That is what I am going to do in this post.

With all graph searches, one needs to define what one is looking for. In this game there are many different ways to score points. But I am just looking for networks that connect all twelve exits. The problem that I face is that it is very unlikely for a random walk to find such a configuration. So if I define a “win” just by fully reaching this goal, it likely works as bad as a random walk. I would need to give partial rewards. In the pure MCTS framework one just counts wins and playouts. The ratio gives the success. But when there is a draw, one can give 0.5 win points. So this seems to be an avenue where one can introduce partial rewards. I will take the number of exists in the largest cluster, and divide that by 12. This gives a reward between 0.0 and 1.0 and sounds like a promising idea.

The success metric itself is a graph theoretical one, and one needs a graph search algorithm to find it. The problem is that the mesh of roads and rails doesn't need to span a tree, it can also span a graph with cycles. For this I won't write an algorithm myself but could resort to a proper graph library like igraph. This should then try to figure out the connectivity. Alternatively I can use my backtracking algorithm with the additional provision that I don't step on the same lattice site again. This way I would try out all possible non-intersecting paths, which then becomes a feasible problem again. I can then use the backtracking algorithm that I have already programmed for an earlier blog post.

Weiterlesen…