Nath-project

[nath]

I try to avoid js like the plague.

But I'm still surprised that a language that isn't even fully compiled (yet oo-ish) survived that long (at least in browsers it's a big thing). But I still think it's a rather odd choice for a game engine.

My engine currently get 30 k nodes per second with a single core of my really cheap desktop. But I think it's likely due to the crappy eval function.

I think on Brandubh one might get a away with a crappy eval function, since the board is so small one can brute force a lot. I'm way more interested in Copenhagen Hnefatafl. I'd be happy to implement some C stuff if one wants to work with me, but apparently I just suck at the eval function. Yet a reasonable eval for Copenhagen is likely much different from one for Brandubh.

If you are interested in Copenhagen in the future, it might be interesting to compare notes about the eval function. And good luck with your project!

[unhandyandy]

I try to avoid js like the plague.

Yeah, I get that a lot.
It doesn't bother me because I don't like standard OO and JS has lambda expressions, GC, and is easily extensible.

But I'm still surprised that a language that isn't even fully compiled (yet oo-ish) survived that long (at least in browsers it's a big thing). But I still think it's a rather odd choice for a game engine.

I wanted it to be easy to share. The slowness is exasperating but it does force me to think hard about optimizations.

I think on Brandubh one might get a away with a crappy eval function,

Not in JS. The eval function is crucial to keep the exponential growth manageable.

it might be interesting to compare notes about the eval function.

Mine is open source: https://github.com/unhandyandy/Strategy ... s/Brandubh

The engine.js file contains the eval function. I can annotate it if you're interested in looking at it.

[nath]

Yeah, I get that a lot.
It doesn't bother me because I don't like standard OO and JS has lambda expressions, GC, and is easily extensible.

I think all that gc is a plague. The thing I never really understood is why the refcount nearly died by now, but I guess it's due to the fact that people like conceptually pure things unless they love hardware (which is as ugly as it gets).

What is even more surprising to me is even if one knows the lifecycle of an object, because it can't be spilled outside of a certain scope, it's still suspected to gc...that costs tons of performance. The next problem with gc is the destructor. The concept of a destructor is essential to oo-design, yet at all places where full gc actually matters the destructor can't be properly called.

The way to bind a function in js is conceptually simple and a nice change. But basically not having a compiler is a serious problem for me. And that obviously is even more of a problem once oo principles are employed (and js is oo).

I wanted it to be easy to share. The slowness is exasperating but it does force me to think hard about optimizations.

I think you should prune more aggressively.

The eval function is crucial to keep the exponential growth manageable.

The exponential part is only manageable with agressive pruning. I think that challenge becomes harder on bigger boards.

The engine.js file contains the eval function. I can annotate it if you're interested in looking at it.

I suspect I'll be pretty much Brandubh only, but I'll have a look. I think it should be fine this way.

Regards
nath

[unhandyandy]

I don't disagree with your criticisms of JS, but my background is in pure math, I never developed the patience to deal with low level languages like C; I like highly abstract languages like Mathematica and lisp. The most performant language I use is probably Julia.

The slowness is exasperating but it does force me to think hard about optimizations.

I think you should prune more aggressively.

I should explain that for me pruning and eval are almost the same thing: I prune by taking the moves that lead to the best evals. I'm sure there are better ways to go if you have more cpu power to work with, but I have to get down to no more than 5 possible moves per pli to have decent performance, so the eval is very involved.

[nath]

I'm from a pure math background as well. And I think that's the reason I'm annoyed by this. We kinda have to most abstract way of writing stuff down, but it seems that when it comes to computer we suddenly forget to specify the properties our abstractions should have.

If your goal is being portable js is an understandable choice.

I've noticed that you do alpha-beta. My point was that there're a lot of moves you almost never need to consider. Non-capturing moves that go into the center of the board without influencing king movement sound like reasonable candidates to me. If one thinks a little bit about Brandubh one can probably make better rule than my rule of thumb with no experience of the game.
Another low hanging fruit would be to preorder the moves in a better way. I'm currently thinking target squares, but there is probably a better heuristic regarding the current king position and/or movement, while I'm not qualified to give any specifics since I don't know a thing about Brandubh.

[unhandyandy]

I'm from a pure math background as well. And I think that's the reason I'm annoyed by this. We kinda have to most abstract way of writing stuff down, but it seems that when it comes to computer we suddenly forget to specify the properties our abstractions should have.

Writing for an audience of humans is very different from writing for CPUs.
Those specs the CPUs need usually go without saying in a math paper. That's why Mathematica is so nice: it's as close a programming gets to pure math.

there're a lot of moves you almost never need to consider. Non-capturing moves that go into the center of the board without influencing king movement sound like reasonable candidates to me.

This may be less true in brandubh since there you're immediately in the endgame. It's an interesting idea though, but I worry that there is a broad class of exceptions. For example, in the opening the king is blocked by his own pieces, and it seems reasonable to make some purely strategic moves. But I'm terrible at Copenhagen.

[nath]

Writing for an audience of humans is very different from writing for CPUs.
Those specs the CPUs need usually go without saying in a math paper. That's why Mathematica is so nice: it's as close a programming gets to pure math.

I can conceptually capture what you mean be that.
At the same time I'm always very surprised that we take pride in the fact that we are good in the way we choose abstractions, but don't care about the property whether the compiler can be able to remove the unnecessary abstractions again.
The joke is that we have already noticed that such properties of an abstraction are useful. Take the splitting of exact sequences for instance. We quite often care whether a sort exact sequence does split, but if the splitting isn't natural the result usually isn't really helpful, since we can't remove the abstraction again. The basic question here is whether some operation is compatible with the way functors work.
The question whether a basic abstraction works with compilers is conceptually very similar. I'm not talking about the way down from some opt-code down to machine instructions or low level optimizations like vectoring. We should just let hardware fanatics handle that. I'm talking about the hardware independent mapping from high level abstractions to low level abstractions.

Huge part of what we do is just dumb. The fact that quite often somebody writes crap since he uses subscripts instead of superscript indexes and gets confused is just plain dumb. Our notations aren't even well suited for humans. But I still think we are the ones who can create the best abstractions, since no other field has nearly as much experience with creating abstractions as mathematics.

This may be less true in brandubh since there you're immediately in the endgame. It's an interesting idea though, but I worry that there is a broad class of exceptions. For example, in the opening the king is blocked by his own pieces, and it seems reasonable to make some purely strategic moves. But I'm terrible at Copenhagen.

In the opening the moves are rarely towards the center and white moves increase king mobility. Form that standpoint the heuristic doesn't hurt too much.

I think the best result for Brandubh is probably obtained by creating perfect play and let a cheap js-heuristic mimic that behavior...even though the second part is definitely no fun at all.

If you want to learn Copenhagen tell me, how I can help.

[unhandyandy]

The question whether a basic abstraction works with compilers is conceptually very similar. I'm not talking about the way down from some opt-code down to machine instructions or low level optimizations like vectoring. We should just let hardware fanatics handle that. I'm talking about the hardware independent mapping from high level abstractions to low level abstractions.

But can't you imagine someone working entirely inside pure math saying, "we should just let the programming fanatics handle that"?

I think the best result for Brandubh is probably obtained by creating perfect play and let a cheap js-heuristic mimic that behavior...even though the second part is definitely no fun at all.

You're saying the first part is easy? I agree brandubh should be solvable with present technology and conventional retrograde analysis. But has it actually been done?

If you want to learn Copenhagen tell me, how I can help.

Eventually, yes, but isn't brandubh the right place to start, being considerable less combinatorially complex? Btw, Copenhagen and brandubh aren't really all that different, i.e armed king, two-sided king capture, corner exit.

[nath]

But can't you imagine someone working entirely inside pure math saying, "we should just let the programming fanatics handle that"?

I love pure math myself and I know a lot people working there. It's hard to not notice a lot of people thinking that. It's easy to identify cultural influences that push people to that standpoint. That doesn't make it less weird from my standpoint that so few people care. The underlying observation that surprises me that much is that the people that tend to be the best with abstractions, tend to use their minds for creating abstractions that give rise to some theoretical unification, but not those who care about solutions supply awful messy ones, yet it's hard to argue with a concept, if it works.

I don't know at all, if I'm able to communicate my point.

I think the best result for Brandubh is probably obtained by creating perfect play and let a cheap js-heuristic mimic that behavior...even though the second part is definitely no fun at all.

You're saying the first part is easy? I agree brandubh should be solvable with present technology and conventional retrograde analysis. But has it actually been done?

Not to my knowledge. I can't tell how long I'd need since I never tried since I never cared. But it's doable and straight forward.

Btw: It's much harder to prove that one archived perfect play than to have almost perfect play. It's for quite a lot of games much harder to accurately determine all positions correctly than to find a set of routes that always leads to the best archiveable result (assuming perfect play from the opponent).

I think once somebody has something that plays basically perfect there is probably little motivation that part with some other program.

Eventually, yes, but isn't brandubh the right place to start, being considerable less combinatorially complex? Btw, Copenhagen and brandubh aren't really all that different, i.e armed king, two-sided king capture, corner exit.

Copenhagen is determined by a king that is 4-side capture, making it a very aggressive game. Blocking the king becomes even more complex since the king does anvil. The fact that the king hammers makes the rules simpler, but isn't nearly as important for the balance.

Another pitfall: Even though we humans can easily think of playing the same rules on a bigger board. If you have played Sea Battle tafl on 11x11 and 9x9, you'll understand what I mean. 9x9 seems to be in notable favor for white, but at 11x11 the white player doesn't see jack at all. 11x11 is a walk in the park for black even with the sparse setup.

What's actually at least as important than the question of corner or edge is the question how much the king has to move from it's starting position.

Don't get me wrong - Sea battle tafl 9x9 has a totally different feel to it than Brandubh. But I think in terms of tactis it's more related than either of them is to Copenhagen.

Even if it would really just come down to combinatorical complexity changes, the set of possible solutions change drastically. Just think about go solutions on 11x11 and 19x19 boards. Pruning appear to matter more for non-linear games as well as for games with higher branching factors (which makes sense to me). We need to think about the problem in a way that it becomes less complex. What's complex depends on the board size. Not all approaches scale in the same manner.

If you care about Brandubh, please don't let me stop you. Even though I personally don't really care, the first step isn't trivial.

[unhandyandy]

the people that tend to be the best with abstractions, tend to use their minds for creating abstractions that give rise to some theoretical unification, but not those who care about solutions supply awful messy ones, yet it's hard to argue with a concept, if it works.

I'm having trouble parsing this sentence - does that "not" belong there?

You seem to be observing that abstractions are clean (almost by definition) and concrete solutions to concrete problems are messy. I think anyone familiar with the real world will recognize that.

I don't know at all, if I'm able to communicate my point.

What's your first language?

Btw: It's much harder to prove that one archived perfect play than to have almost perfect play. It's for quite a lot of games much harder to accurately determine all positions correctly than to find a set of routes that always leads to the best archiveable result (assuming perfect play from the opponent).

I don't think "perfect" is the right word to use here. Nobody claims that any engine, short of an exhaustive database, plays perfectly. But even 20 years ago Chess engines were playing well enough to beat 99% of the players. The tafl community could a learn a lot just by having an engine as good as those available in chess a generation ago.

Re: Brandubh v. Copenhagen, I'm sure the differences you mention are real and salient, but surely Brandubh is the place to start with a tafl engine. Shouldn't you always start with the simpler cases before progressing to the harder ones? So much would be learned by actually building a brandubh engine. Even if you don't enjoy playing brandubh, as a programmer isn't that the right place to start?

But it's doable and straight forward.

Maybe, maybe not so straightforward. Have you ever built a retrograde analysis engine, e.g. for chess or checkers? I have not, and I'm intimidated by the prospect. Surely you would learn an awful lot by actually carrying through such a project for brandubh. It would certainly be a service to the tafl community, as we could all then stop playing it.