Page 3 of 4

Re: Nath-project

Posted: Sat Feb 02, 2019 7:47 am
by nath
unhandyandy wrote:
Fri Feb 01, 2019 5:52 pm
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?
It doesn't. Just skip it.
unhandyandy wrote:
Fri Feb 01, 2019 5:52 pm
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 strongly disagree. Since we can't have a definition of cleanness this can't be a result of a definition. I've seen abstractions, I'd call awfully messy. Did you ever do discrete mathematics? You don't even need to apply it...

Another informal thing I tend to observe is that we can make things at the cost of complexity less dirty. There are quite often unifying concepts that are just more complex. And if I don't see them, it might just be the case due to my limited ability to handle more complexity. Note that complexity isn't any pure category here, since what's complex highly depends on the stuff we take for granted.

We always have to balance different properties of a given solution or abstraction. There is no best solution for a given problem. In fact I there are simple problems I solve in a lot of different ways in my daily live depending on the context. The simple problems are usually some that are known solved and only occur as subproblems. There are a lot of things I factor in. The length of stuff to write, the stuff other people have to read, their backgrounds, the complexity of the solutions, the complexity of the stuff they are not yet familiar with, the ability to isolate technical parts and calculations into specific pages without littering the big picture with them.
This not depended on whether I do math, programming or do virtually anything else. Understanding the audience is usually the hard part.

While we always have to decide which route we go, the observation I wanted to make above, is that people tend to push the dirty or the complexity and not to find a middle ground. The thing that surprises me even more that there so few methods explored to switch viewpoints between different layers of abstraction.
unhandyandy wrote:
Fri Feb 01, 2019 5:52 pm
What's your first language?
I learned java way back then. But I still think that wasn't great. How is that connected to the discussion?
unhandyandy wrote:
Fri Feb 01, 2019 5:52 pm
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.
I claim to have perfect play of tic-tac-toe. We have perfect play of checkers and morris as well.
unhandyandy wrote:
Fri Feb 01, 2019 5:52 pm
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?
Well, to give an extreme example: Walking 50 miles is easier than building a car. I'm not going to fix this metaphor. Not because I couldn't, but because I don't want us to argue about the right one describing the reality. Yet my point stays the same.
That being said: If you enjoy it, it's the right thing to do. There is no reason you have to adapt my passion for Copenhagen. You should never just take the stuff you care for for granted. It's a gift and if you care by all means don't let me sow doubts.
unhandyandy wrote:
Fri Feb 01, 2019 5:52 pm
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. :)
Maybe I'm dumb, but I don't see what retrograde analysis have to do with this. That sounds way more complex.

Regards
nath

Re: Nath-project

Posted: Sat Feb 02, 2019 7:09 pm
by unhandyandy
I strongly disagree. Since we can't have a definition of cleanness this can't be a result of a definition.
Notice I employed the weasel word "almost". ;)

But my point was that mathematical abstractions aren't considered useful unless they simplify the conceptual landscape.
I've seen abstractions, I'd call awfully messy.
Even compared to what the landscape looked like before they were available?
Another informal thing I tend to observe is that we can make things at the cost of complexity less dirty. There are quite often unifying concepts that are just more complex.
I think there's a trade-off of one kind of complexity for another. It's true that occasionally breakthroughs are made that make unexpected connections between branches of math previously thought separate, and that can make life more complicated for researchers in the affected fields.
While we always have to decide which route we go, the observation I wanted to make above, is that people tend to push the dirty or the complexity and not to find a middle ground. The thing that surprises me even more that there so few methods explored to switch viewpoints between different layers of abstraction.
We may have to agree to disagree here. I think problem domains tend to look simpler before you actually start to solve some of the problems in them. A programmer's architectural plan for a system is never equal to all the edge cases, hidden paradoxes, changing goals, unexpected insights, etc. that develop during the course of a project. The software industry is littered with failed attempts to rewrite major projects using the "right" design.

It would be great if there were tools for deeply refactoring an existing project, but we may have to wait for AI to handle that for us. :)
What's your first language?
I learned java way back then. But I still think that wasn't great. How is that connected to the discussion?
I meant natural language. :) German? Your English is better than my Deutsch.
I don't think "perfect" is the right word to use here. Nobody claims that any engine, short of an exhaustive database, plays perfectly.
I claim to have perfect play of tic-tac-toe. We have perfect play of checkers and morris as well.
Touché. :)
I was thinking of chess and go. We do not have it for brandubh yet, so the advice to emulate kind of perfect play is unhelpful. :)
I don't see what retrograde analysis have to do with this. That sounds way more complex.
Isn't that the way the chess endgame tablebases have come about? I think that's also the way checkers was solved. You're right though about tic-tac-toe though, retrograde analysis isn't necessary there. :)

I'm certainly no expert, I've just always assumed that retrograde analysis was useful for the same reason that recursive definitions are useful: explicit solutions are only necessary in the simplest cases, and then solutions to complicated positions can be determined from the stored solutions to simpler ones.

Re: Nath-project

Posted: Sat Feb 02, 2019 10:57 pm
by nath
unhandyandy wrote:
Sat Feb 02, 2019 7:09 pm
Notice I employed the weasel word "almost". ;)
I still strongly disagree with the sentiment.
unhandyandy wrote:
Sat Feb 02, 2019 7:09 pm
But my point was that mathematical abstractions aren't considered useful unless they simplify the conceptual landscape.
They are usually considered useful when they yield results that can be proven or reused. The interesting part about this, that the models we think in and the models we use to prove stuff fundamentally differ. Category theory is a great model to organize ones thoughts, but it doesn't help much with simplifying the proofs.
unhandyandy wrote:
Sat Feb 02, 2019 7:09 pm
I've seen abstractions, I'd call awfully messy.
Even compared to what the landscape looked like before they were available?
Yes, quite a few abstractions are inherently not easy to think about, but have nice properties regarding compatibility with other methods.
unhandyandy wrote:
Sat Feb 02, 2019 7:09 pm
I think there's a trade-off of one kind of complexity for another. It's true that occasionally breakthroughs are made that make unexpected connections between branches of math previously thought separate, and that can make life more complicated for researchers in the affected fields.
Let's take the simplest case: we just unify two different objects that share certain properties and assign a new name. Our model space just become more complex. We know use three term for the thing that previously just had two. Thinking about the new kind of object is complicated, since it can be either of two inherently different objects. Yet we do it a lot, because after we sucked up the model complexity, the representation of a lot of proofs and theorems gets cleaner. We are able to hide huge parts of the complexity of the concrete case by avoiding to think about different distinct cases at some places (which humans seem to be inherently bad at).
Researchers of a specific field don't care that much about the model complexity. More abstraction is surprisingly often not helpful the generate proofs, even when they work in the abstract case.
unhandyandy wrote:
Sat Feb 02, 2019 7:09 pm
We may have to agree to disagree here. I think problem domains tend to look simpler before you actually start to solve some of the problems in them. A programmer's architectural plan for a system is never equal to all the edge cases, hidden paradoxes, changing goals, unexpected insights, etc. that develop during the course of a project. The software industry is littered with failed attempts to rewrite major projects using the "right" design.
You are mixing a lot of different things together here. Architecture is about something totally different than cleanness of code. Architecture barely touches the way code is written. But you are right that architectural problems are much more severe than code problems. You can have an architecture that allow you to easily replace portions of your code without replacing the whole code base. The school claiming that you just have to get the right interfaces apparently never worked on real life projects, but if you enforce the right architectural behavior of the individual part the project lives on even when the code dies.
Architecture is important on a much higher level. It's important for the project not the individual part of the program. The industry is quite often driven by people wanting products. Ignoring that in the architecture is ofc deadly. But letting that drive the architecture is also bad.

Architecture is a separate very complex topic. And even in my hobby project it's often something that happens on accident. But having at least some awareness and restraint is important.
unhandyandy wrote:
Sat Feb 02, 2019 7:09 pm
It would be great if there were tools for deeply refactoring an existing project, but we may have to wait for AI to handle that for us. :)
That has little to do with AI. There are two simple requirements for that. One is architectural to the compiler, since there are a lot of things that can realistically just be done by using special hooks. The second and in my eyes more critical part is the point that there is a limit which kind of abstractions can be easily removed. This has something to do with isolation of the effects of some abstractions.
We have the type theory guys trying to add information that helps dealing with effects. This is usually done to optimize further during compilation. They are also kind of close to some simple concepts used in fol atp. On the other hand we have people that just write code in a manner that computers understand it well - so they essentially need to get a feel about how computers work to read that code.
Ofc we also have to people that just don't care at all how it works...

The issue is that some abstractions do a lot of checking. We are not trained to write it down in a way it can be proven that it's not necessary. The scope of what is doable depends on the representation. And removing that dependency would be equal to solving the halting problem. So the real underlying question is what kind of representations make it easy to remove some common issues with abstraction.

It's not just about performance here. Changing layers of abstraction require that as well (just not regarding opt-code, but regarding source representations). At least reducing abstraction for a given term is equal to that problem. Increasing abstraction is hard, let's not think about that for a moment.
unhandyandy wrote:
Sat Feb 02, 2019 7:09 pm
I meant natural language. :) German? Your English is better than my Deutsch.
Sorry, yeah that's my native language.
I the issue here is not the language itself. I have the problem of chaining way to many thoughts together in a single statement. That issue is not inherit to any specific language (and surfaces in programming languages as well). Yet you might be right, that the understanding penalty of that issue regarding is (trusting linguist research) much higher in English than German. So while the issue isn't language related (in this case) the symptoms are more severe.
unhandyandy wrote:
Sat Feb 02, 2019 7:09 pm
Touché. :)
I was thinking of chess and go. We do not have it for brandubh yet, so the advice to emulate kind of perfect play is unhelpful. :)
I didn't think of that as advice. I just guessed that would be the easiest way to get a machine that plays fast.
unhandyandy wrote:
Sat Feb 02, 2019 7:09 pm
Isn't that the way the chess endgame tablebases have come about? I think that's also the way checkers was solved. You're right though about tic-tac-toe though, retrograde analysis isn't necessary there. :)
The end-game tables is just the position with less than X pieces (depending on which configurations you look at - positions with 7 bishops on the board are less explored) connected in a graph like structure. And sorted by moves to win, capture or pawn move in perfect play (so unless win, capture or pawn move occurs there is at least one child with one less). The only detail of the structure is that we don't save is the edges of the graph (since they can be easily inferred from the position knowing the ruleset) and would account for a huge size (the sole numbers are small). True retrograde analysis would require us to also count predecessors with X+1 pieces.

From my pov checkers seems harder than Brandubh.
unhandyandy wrote:
Sat Feb 02, 2019 7:09 pm
I'm certainly no expert, I've just always assumed that retrograde analysis was useful for the same reason that recursive definitions are useful: explicit solutions are only necessary in the simplest cases, and then solutions to complicated positions can be determined from the stored solutions to simpler ones.
Ofc. Yet searching for all the complex positions that could have been reduced to the simpler one is not that helpful. The point is that in Brandubh there are usually quite few captures. Even less than in other tafl variants and most variants have in common that there are small percentage of black pieces captured. So going up from boards with less pieces isn't that helpful.

In Brandubh quite a lot of moves can be quickly disregarded, since they end quite quickly with an intelligent preordering. I think that is a pretty general pattern for most movement based deterministic two player games with perfect information.

If I'd try to solve Brandubh, I'd forward calculate positions instead of backwards to find a candidate for a variant. If one skips all permutations and rotations, there aren't that many positions.

Re: Nath-project

Posted: Sun Feb 03, 2019 5:37 pm
by unhandyandy
I think we're grabbing the same elephant at different ends. Let's get back to Hnefatafl.
If I'd try to solve Brandubh, I'd forward calculate positions instead of backwards to find a candidate for a variant. If one skips all permutations and rotations, there aren't that many positions.
That's not how the chess endgame DBs were constructed.

https://www.chessprogramming.org/Retrograde_Analysis

According to that page, solving checkers also depended critically on retrograde analysis. But 5x5 Go was solved with a-b search.

http://erikvanderwerf.tengen.nl/5x5/5x5solved.html

But Go on such a small board is particularly simple since (as humans have long understood) with best play white cannot form any safe region. Perhaps brandubh could also be solved by a forward search, but with more than 10^14 possible positions I think retrograde analysis would be much easier.

On the other hand, if all we want is good play (and who here wouldn't settle for that?), then forward search should be adequate to play at a level above any human.

Re: Nath-project

Posted: Sun Feb 03, 2019 11:41 pm
by nath
unhandyandy wrote:
Sun Feb 03, 2019 5:37 pm
I think we're grabbing the same elephant at different ends. Let's get back to Hnefatafl.
I still care about the abstractions. I understand your pov, yet deeply care that people who understand abstractions make them better in every regard possible. I'd just love to get a few mathematicians out of their respective bubbles.
unhandyandy wrote:
Sun Feb 03, 2019 5:37 pm
If I'd try to solve Brandubh, I'd forward calculate positions instead of backwards to find a candidate for a variant. If one skips all permutations and rotations, there aren't that many positions.
That's not how the chess endgame DBs were constructed.

https://www.chessprogramming.org/Retrograde_Analysis
Well the way that's done in chess is from the algorithmic standpoint the same as retrograde analysis until one reaches positions with X pieces. Conceptually the aim is quite different. The simplicity of Brandubh might even allow for that method on modern hardware. After all the state complexity is lower than the of checkers. Yet I don't think it will be the computational fastest method.
unhandyandy wrote:
Sun Feb 03, 2019 5:37 pm
But Go on such a small board is particularly simple since (as humans have long understood) with best play white cannot form any safe region. Perhaps brandubh could also be solved by a forward search, but with more than 10^14 possible positions I think retrograde analysis would be much easier.
Why are you thinking about go? We know it's a totally different kind of problem. Go has a nearly linear flow, but an insane branch factor and a high state complexity.
The question, as I see it, is just how you can reach a solution without going though to many (or even most) of the positions. And reaching the starting position with retrograde analysis requires to get to almost all positions. Most positions in Brandubh can be solved through simple heuristics.
unhandyandy wrote:
Sun Feb 03, 2019 5:37 pm
On the other hand, if all we want is good play (and who here wouldn't settle for that?), then forward search should be adequate to play at a level above any human.
I just don't care the slightest bit about Brandubh, I'm not even sure whether we already have two humans that are able to play a perfect game. Getting perfect play is way easier than understanding all positions.

I don't want to sound indifferent about the techniques, because I'm not. The point for me is that we can apply a lot of techniques to Brandubh, that can't work on sufficiently complex rules on larger boards.

Re: Nath-project

Posted: Mon Feb 04, 2019 5:59 pm
by unhandyandy
I'd just love to get a few mathematicians out of their respective bubbles.
They became mathematicians because they like those bubbles. You have no more chance of that than I have of getting you into Brandubh.
Well the way that's done in chess is from the algorithmic standpoint the same as retrograde analysis until one reaches positions with X pieces.
And that's one reason chess has not been solved. Only games small enough to be susceptible to a nearly exhaustive retrograde analysis can be properly solved. Checkers is just simple enough that retrograde analysis of endgames plus forward analysis from the opening position is enough to get a weak solution. I think brandubh ought to be simple enough to get similar solution. I think we actually agree on this. Maybe I was wrong to think that retrograde analysis alone would work, but it would certainly be an essential component.
Why are you thinking about go? We know it's a totally different kind of problem. Go has a nearly linear flow, but an insane branch factor and a high state complexity.
Well, to the extent that go is more complex than tafl, then the fact that 5x5 go is solvable is cause for optimism. But actually is the branching factor really worse in go than in tafl? In go the number of moves possible from a given position is equal to the number of empty points; in tafl it might be several times higher than that.
I just don't care the slightest bit about Brandubh
Well, de gustibus non est disputandum.

(But as programming problem I don't see how the simplest case of tafl could fail to interest you.)
I'm not even sure whether we already have two humans that are able to play a perfect game.
Of course not. That's not possible for any humans in games much above the level of tic-tac-toe.
Getting perfect play is way easier than understanding all positions.
You'll have to define your use of the word "perfect" in this context. With any standard definition this sentence is opaque to me. If you haven't considered all positions how can you be sure you haven't missed anything important? The whole field of chess problems is based on moves that are wrongly dismissed.
I don't want to sound indifferent about the techniques, because I'm not. The point for me is that we can apply a lot of techniques to Brandubh, that can't work on sufficiently complex rules on larger boards.
They won't work as well on larger boards, but they'd be a start.

Re: Nath-project

Posted: Tue Feb 05, 2019 3:18 am
by nath
unhandyandy wrote:
Mon Feb 04, 2019 5:59 pm
They became mathematicians because they like those bubbles. You have no more chance of that than I have of getting you into Brandubh.
I think in a lot of cases it's actually the other way around. A lot of them get to accustomed to a bubble during their studys and stick with it.
unhandyandy wrote:
Mon Feb 04, 2019 5:59 pm
Well, to the extent that go is more complex than tafl, then the fact that 5x5 go is solvable is cause for optimism. But actually is the branching factor really worse in go than in tafl? In go the number of moves possible from a given position is equal to the number of empty points; in tafl it might be several times higher than that.
If you think about the possible black moves, that might be. For reasonable board size white has just way less moves. Since the branching factor is the geometric average...
unhandyandy wrote:
Mon Feb 04, 2019 5:59 pm
I just don't care the slightest bit about Brandubh
Well, de gustibus non est disputandum.

(But as programming problem I don't see how the simplest case of tafl could fail to interest you.)
My question in the above case exactly was why somebody don't want to deal with a question.
Brandubh is hard enough that one can waste a few weeks on it. But honestly I don't want to deal with Brandubh, because it's to easy that I could feel accomplished if anything comes out. I usually define my action in a wider scope. I relate to something or much rather someone. It's not important whether I've met the somebody. But when I don't see how provide valuable insight into something to somebody, I have no motivation to try something.
The reason I like Copenhagen is because it's hard enough that nobody will have a definitive answer soon, intuitive enough we can sit together at a board play and relate to it, yet in reality we don't understand a thing about the game. Even the grandmasters mainly make judgements in terms of their past experiences about how certain positions played out in the past. If we find something here - whatever it might be - it will prove to increase our understanding and change the actual play of the game.
unhandyandy wrote:
Mon Feb 04, 2019 5:59 pm
I'm not even sure whether we already have two humans that are able to play a perfect game.
Of course not. That's not possible for any humans in games much above the level of tic-tac-toe.
We appear to have that for Morris, which seems to be above tic-tac-toe at the first glance. (While I never played the grandmasters myself to verify that result.)
unhandyandy wrote:
Mon Feb 04, 2019 5:59 pm
Getting perfect play is way easier than understanding all positions.
You'll have to define your use of the word "perfect" in this context. With any standard definition this sentence is opaque to me. If you haven't considered all positions how can you be sure you haven't missed anything important? The whole field of chess problems is based on moves that are wrongly dismissed.
To archive perfect play you just need to understand the starting position perfectly. If your first move in chess is e4 any position with a white pawn on e2 isn't interesting anymore regarding the result. The rules are harder to check in other games, but if you control half of the moves and/or pieces that greatly simplifies the amount of positions that have be searched.
unhandyandy wrote:
Mon Feb 04, 2019 5:59 pm
They won't work as well on larger boards, but they'd be a start.
If you want to try retrograde analysis on Copenhagen go ahead, but I'm fairly sure that not much will come out of it.

All the best
nath

Re: Nath-project

Posted: Tue Feb 05, 2019 9:12 pm
by unhandyandy
If you think about the possible black moves, that might be. For reasonable board size white has just way less moves. Since the branching factor is the geometric average...
I forgot about White! :o

But now that you mention it, the geometric mean might be quite comparable to go. And the branching factor in go decreases linearly as the game progresses.
I don't want to deal with Brandubh, because it's to[o] easy that I could feel accomplished if anything comes out.
Solve it first, then brag about being too smart for it.
I usually define my action in a wider scope. I relate to something or much rather someone.
I was under the impression you're a programming grad student, am I wrong about that?
To archi[e]ve perfect play you just need to understand the starting position perfectly. If your first move in chess is e4 any position with a white pawn on e2 isn't interesting anymore regarding the result. The rules are harder to check in other games, but if you control half of the moves and/or pieces that greatly simplifies the amount of positions that have be searched.
I'm still not getting you. Sure, starting from a fixed position reduces the combinatorial complexity in a way comparable to reducing the number of pieces on the board. But surely you're not claiming that "perfect" play is possible in chess? We don't even know whether e4 or d4 is the ideal opening move.
If you want to try retrograde analysis on Copenhagen go ahead, but I'm fairly sure that not much will come out of it.
You may be right. But it might also be possible to adapt the strategy. For example, many endgame situations are effectively confined to just one quarter of the board. Retrograde analysis would work on those.

Re: Nath-project

Posted: Wed Feb 06, 2019 5:42 am
by nath
unhandyandy wrote:
Tue Feb 05, 2019 9:12 pm
Solve it first, then brag about being too smart for it.
I'm not smart and I never intended to give the impression. I just have the impression you are trying to taunt me. I guess you can't offload that work on to me. :roll:
unhandyandy wrote:
Tue Feb 05, 2019 9:12 pm
I was under the impression you're a programming grad student, am I wrong about that?
I never studied anything related to programming.
unhandyandy wrote:
Tue Feb 05, 2019 9:12 pm
I'm still not getting you. Sure, starting from a fixed position reduces the combinatorial complexity in a way comparable to reducing the number of pieces on the board. But surely you're not claiming that "perfect" play is possible in chess? We don't even know whether e4 or d4 is the ideal opening move.
While it appears that d4 is slightly simpler to understand. Some people conjecture that it might be a draw, we don't have the slightest clue. I just used the most obvious example that came to my mind. I could have talked about hex, since it's purely linear.

Go games get a lower branching factor once you reach a depth where 11x11 Hnefatfl games have already ended. That appears to be the case, yes.
If you want to try retrograde analysis on Copenhagen go ahead, but I'm fairly sure that not much will come out of it.
You may be right. But it might also be possible to adapt the strategy. For example, many endgame situations are effectively confined to just one quarter of the board. Retrograde analysis would work on those.[/quote] Are you talking about edge forts? That might totally be. I was using that technique for edge forts during my games.

I'm pretty sure that these days, still most games are decided in the fight for corners where the game is much more tactical.

Re: Nath-project

Posted: Wed Feb 06, 2019 8:15 pm
by unhandyandy
I'm not smart and I never intended to give the impression. I just have the impression you are trying to taunt me.
Sorry about that, I thought you were saying that solving brandubh was beneath you.

Anyone, you certainly are smart - you're a former hnefatafl world champion!
I never studied anything related to programming.
Well, you sure are much more knowledgeable about it than I am.

Are you a math student?
Are you talking about edge forts? That might totally be. I was using that technique for edge forts during my games.
Yes, you could use retrograde analysis to develop an edge-fort engine.

Didn't the original AlphaGo program also do local tactical analysis separately from global strategic analysis?