3bv limits

[Tommy]

Actually, to ensure that symmetric boards have the same ZiNi, just calculate it for all equivalent boards and take the minimum. Everything else may well be too expensive.

Does anyone who already has working board statistics grinding code feel motivated to calculate ZiNi from all sides for a couple thousand boards? Would be interesting what the differences are.

[qqwref]

You're pretty much just suggesting my "8-Way ZiNi" idea from at least a year ago. And yeah, it's not affected by changes, but it takes 8 times as long as ZiNi. I think we need something less slow.

[Tommy]

I don't want to take credit for being the first person to think of it - however, I think it makes sense, and I think we should do it.

To clarify, what I am proposing is exactly 8*ZiNi. Since ZiNi is probably only O(n log(n)) in the size of the board (cryslon and I talked about this on IRC, I'm pretty sure about it), this is actually not a lot at all.

[qqwref]

This is at least the second time you've brought up big-oh notation. I think it's completely irrelevant how something grows for large numbers, because people are playing boards of specific sizes. When it comes to timing, the only question is this: when playing boards of a reasonable size (let's say 24x30 at most), will the delay in calculating it, on an older computer, be noticeable for a player? (By the way, I don't like the idea of only checking for limits after a game is played - I think many players would be really unhappy if they finally got an awesome record only to have it not counted by the community because the board is slightly under an admittedly arbitrary line!)

About having a ZiNi-like limit, I think before we decide to do this we need to choose a metric everyone is okay with. IMO the metric must satisfy these criteria:
- It must not depend on the placement/rotation of the board (pure ZiNi fails this)
- It must be the same every time (random ZiNi fails this)
- It must be possible to calculate quickly (optimal solution fails this)
- There should be a good reason to use it over similar metrics, by which I mean that all the choices we make in designing the algorithm should make sense
- It would also be awesome if it was easy to understand what a number means, so that a limit of (say) 90 makes intuitive sense and isn't just a number that pops out of a complex function (OBV fails this)
I am not necessarily against the idea of a 3BV-like limit for flaggers, but I think we really need to be careful about deciding on it. We really don't want to be changing the limit to a new one every year or two, barring amazing theory discoveries. If we're going to choose a metric to use for limits, it should be a choice that is easy to explain.

PS: I guess I should publish my chord-set idea soon! It's very relevant to this kind of discussion. I think the concept is more robust/"clean" than that of ZiNi.

[EWQMinesweeper]

About having a ZiNi-like limit, I think before we decide to do this we need to choose a metric everyone is okay with. IMO the metric must satisfy these criteria:
- It must not depend on the placement/rotation of the board (pure ZiNi fails this)
- It must be the same every time (random ZiNi fails this)
- It must be possible to calculate quickly (optimal solution fails this)
- There should be a good reason to use it over similar metrics, by which I mean that all the choices we make in designing the algorithm should make sense
- It would also be awesome if it was easy to understand what a number means, so that a limit of (say) 90 makes intuitive sense and isn't just a number that pops out of a complex function (OBV fails this)

why?

[qqwref]

The first one: because a metric that is affected by rotation/reflection does a poor job of representing human play - plus, you could have the situation where a board is considered too easy but the reflected board is considered OK, which is unfair.
The second one: because that means the cutoff is random, i.e. whether a given time counts as a record or not may depend on the output of a random-number generator, which is unfair.
The third one: to decrease game lag.
The fourth one: so we don't have constant arguments about changing the metric once it is set in place, also so we can explain the reason for the limit to new players who aren't heavily versed in theory.
The fifth one: so we can explain the reason for the limit to new players who aren't heavily versed in theory.

[EWQMinesweeper]

The first one: because a metric that is affected by rotation/reflection does a poor job of representing human play - plus, you could have the situation where a board is considered too easy but the reflected board is considered OK, which is unfair.

but human play is as well affected by rotation and reflection. just take rectangular nonosweeper boards as an example.

The second one: because that means the cutoff is random, i.e. whether a given time counts as a record or not may depend on the output of a random-number generator, which is unfair.

true.

The third one: to decrease game lag.

it is a very vague criteria. maybe you guys should find some optimal lower/upper bounds for that, which are ok for very slow computers.

The fourth one: so we don't have constant arguments about changing the metric once it is set in place, also so we can explain the reason for the limit to new players who aren't heavily versed in theory.

pretty much means that the current 3bv limits will stay until there is a satisfying solution. hurry up!

The fifth one: so we can explain the reason for the limit to new players who aren't heavily versed in theory.

"because some day, some people somehow decided to set arbitrary limits, without providing any reasons" is not an easily understandable answer?

[Tommy]

The first one: because a metric that is affected by rotation/reflection does a poor job of representing human play - plus, you could have the situation where a board is considered too easy but the reflected board is considered OK, which is unfair.

Agreed. More for reasons of mathematical elegance, though.

The second one: because that means the cutoff is random, i.e. whether a given time counts as a record or not may depend on the output of a random-number generator, which is unfair.

Also agreed. Especially, even worse, there is no guarantee that a given value will ever be reproduced.

The third one: to decrease game lag.

Agreed, but for ZiNi, probably not an issue on a computer that can run nethack.

The fourth one: so we don't have constant arguments about changing the metric once it is set in place, also so we can explain the reason for the limit to new players who aren't heavily versed in theory.

Somewhat agreed.

The metric should be a good approximation of board difficulty, of course. But if you look at what Ronny did, you get perfect criteria: It should be a cutoff that is about as effective as the 3bv limit on int (because that limit has served us well), and probably a round decimal number, because humans tend to grow up with the decimal system.

The fifth one: so we can explain the reason for the limit to new players who aren't heavily versed in theory.

Agreed, but likely not a problem IMHO.

I'd guess that for every metric, there is an idea behind it that makes it work. For 3bv, it is "minimal left-clicks". For ZiNi, it is "approximate minimal clicks". So, what a ZiNi limit of X pretty much means is that it should not take a flagger substantially less that X clicks to finish, much like 3bv. The imperfection of ZiNi is strongly obscured by human solving inefficiency anyway. Also, humans can require slightly more clicks for better path efficiency and be faster anyway.

This is at least the second time you've brought up big-oh notation. I think it's completely irrelevant how something grows for large numbers, because people are playing boards of specific sizes. When it comes to timing, the only question is this: when playing boards of a reasonable size (let's say 24x30 at most), will the delay in calculating it, on an older computer, be noticeable for a player? (By the way, I don't like the idea of only checking for limits after a game is played - I think many players would be really unhappy if they finally got an awesome record only to have it not counted by the community because the board is slightly under an admittedly arbitrary line!)

All I'm saying is, ZiNi isn't actually that much slower than 3bv. If I see actual evidence that a ZiNi implementation is too expensive _even though it is optimized_, I'll start worrying. And it's definitely good for a metric to work well on arbitrary board sizes.

I think that each player should decide whether or not they want to play boards that are "too easy"; ie, clones should provide an option (or be allowed to do either). Also, notice that there is no other way if you don't implement FL and NF modes; boards may be legal for NF that aren't for FL, or even vice versa.

I am not necessarily against the idea of a 3BV-like limit for flaggers, but I think we really need to be careful about deciding on it. We really don't want to be changing the limit to a new one every year or two, barring amazing theory discoveries. If we're going to choose a metric to use for limits, it should be a choice that is easy to explain.

But don't forget the quintessential feature that this metric must have: existence. At some point we should settle for something. I'm not saying right now, but this argument could turn this discussion into a stallfest.

PS: I guess I should publish my chord-set idea soon! It's very relevant to this kind of discussion. I think the concept is more robust/"clean" than that of ZiNi.

By all means! Alternatives are most welcome. Do it now. Especially as I'm very interested in how it differs from ZiNi.