The Chord-Set Approach

Want to calculate something or share your results?
Post Reply
qqwref
Posts: 121
Joined: Thu Sep 23, 2010 4:17 pm

The Chord-Set Approach

Post by qqwref » Wed May 09, 2012 10:01 pm

Eventually I'm going to finish writing up a paper/article describing this in more detail and providing some ideas for how to approach being able to find optimal solutions. However, this description should be enough to let people consider the idea.

Concept
Imagine taking a solution to a board and breaking it down in terms of the moves that were made. There are three types of moves: (1) clicks, to open single squares; (2) flags, to mark mines that we will need for chords; (3) chords, to open multiple squares around an opened square. I realized that the clicks and flags are not actually important to the solution - basically, the way the solution approaches the board can be described entirely in terms of where they used chords. Flags only exist to set up for chords, and clicks only exist to open squares that need to be chorded and to clean up after all the chords are done.

So that gave me the idea of the chord-set. Pretty simply, it's just a list of the squares where a solution plans to use chords. This is useful because, as I'll explain below, it's actually possible to calculate the optimal number of clicks to complete a board, given a particular chord-set. We can calculate near-optimal solutions to boards that do not depend on the board's placement or the details of an algorithm, but are just based on the chord-set you are using. And, the length of the solution is just based on the amount of work we put into optimizing our chord-set.

Calculation
I've been using OL (for "optimal length") to stand for the 'quality' of a chord-set - that is, the number of clicks in the optimal solution using that chord-set. The formula for computing OL is as follows:
- OL = # flags + # chords + # chord setup clicks + # extra clicks
- # flags = number of mines that are adjacent to a square in our chord-set
- # chords = number of squares in our chord-set
- # chord setup clicks = number of connected components of our chord-set (interpreting it as a graph, where the vertices are squares, and two vertices are connected with an edge if the squares are either adjacent or both part of the same opening)
- # extra clicks = number of 3BV remaining after all chords are used

Note that if our chord-set is empty this algorithm basically just calculates the 3BV :) So, in fact, you could see this as a generalization of the idea of 3BV: it generates an optimal solution, not dependent on board placement or random factors, and given a specific set of chords, in one step. Personally, I think this is pretty cool.

Application
Note that the chord-set idea isn't itself a solving algorithm (like ZiNi). This actually gives us a lot of freedom to use it to create solving algorithms that produce solutions of a given quality with various properties. Here are some possible ways to create solutions, not in any real order, but numbered for convenience:
1) Take an existing solution algorithm, and then just get the chord-set from it and find the OL. This can often save a couple of clicks.
2) A GZiNi-like approach: repeatedly add the most useful chord to the chord-set, until every possible extra chord would waste clicks. This would be affected by board orientation since we have to choose chords to add in some order.
3) Like #2, but we add all sufficiently useful chords at once (e.g. all chords with a 'premium' of 4+ in the first step, then all with a 'premium' of 3+, and so on). This would use more clicks but wouldn't be affected by board orientation.
4) Create some kind of heuristic for deciding where to place a chord, then place them all at once or in stages, again trying not to be affected by board orientation.
5) Start with one or more base chord-sets, such as one generated by ZiNi, and then use a hill-climbing or genetic algorithm approach to try to optimize them for the lowest possible OL. This wouldn't be good for a board measure, but is useful for trying to find optimal solutions.

I've managed to implement the OL function in C, although it would be cool to have someone optimize it. The faster this function can get, the more reasonable it is to try to compute optimal solutions for boards, and the faster we can actually compute board measures like the above. I like how the number this formula creates has nothing to do with the order you might actually solve the board in, which means that it's more robust than things like ZiNi, but the task of finding a good chord-set is quite tricky and needs more research.

Any questions? :p
NF player. Best scores 1-10-39.

aradesh
Posts: 90
Joined: Sat Aug 29, 2009 3:37 pm

Re: The Chord-Set Approach

Post by aradesh » Thu May 10, 2012 1:39 pm

Worthwhile post. You haven't done anything except state the obvious once you've set out what you're doing, however it's the sort of obvious that we forget or fail to think of. As a (trainee :P) mathematician, I understand the importance of stating the obvious clearly and succinctly, and in a way which makes it easy to communicate with others.

User avatar
Tommy
Posts: 223
Joined: Mon Dec 01, 2008 9:22 pm
Location: Vienna

Re: The Chord-Set Approach

Post by Tommy » Thu May 10, 2012 2:21 pm

Awesome, I like it! And I agree with aradesh.

I'd be interested in seeing data on how #2 compares with #3.

/me will post again after giving the whole thing some more thought.
Don't anthropomorphize computers - they don't like it.

qqwref
Posts: 121
Joined: Thu Sep 23, 2010 4:17 pm

Re: The Chord-Set Approach

Post by qqwref » Thu May 10, 2012 10:13 pm

Yeah, I agree a lot of this is obvious, which I think is a good thing - it seems to imply that the concept is a natural one, and also that if we do more complicated constructions involving the chord-set the analysis will still be feasable. Plus, we definitely do need to state obvious things in theoretical situations, in case people forget or don't notice them.

By the way, here's the number of clicks we add when we add a new chord c (this is roughly the negative of ZiNi's premium):
Δ OL = Δ flags + Δ chords + Δ chord setup clicks + Δ extra clicks
= (number of mines adjacent to c but no other chord) + (1) + (1 - number of connected components that would be connected to c) - (number of 3BV adjacent to c but no other chord)
NF player. Best scores 1-10-39.

Post Reply