Show HN: Generate guitar tablature using a constraint solver | Hacker News Reader

Show HN: Generate guitar tablature using a constraint solver

github.com

Author here. TablaZinc is a proof-of-concept tablature generator for fretted string instruments -- such as the guitar, bass, mandolin, banjo, etc.

It is a week-end project that I started for two reasons:

* As a software developer, I was looking for an original case study to learn constraint programming.

* As a guitar player whot is not fluent reading sheet music, I was interested in a tool to rapidly convert existing transcriptions of jazz solos into playable guitar tablatures.

TablaZinc is written in the MiniZinc language. https://www.minizinc.org Feedback from advanced users of MiniZinc and experts in constraint programming will be welcome.

Some time ago I transcribed Solfegiato into python script and converted to MIDI notes. Then printed it as TAB where each note is shown on all strings if the fret number is in range. I spent a lot of time choosing strings and fingerings to make it playable. It was plainly obvious that a constraint solver (or wave function collapse) would be a great way to select options for a playing style (alternating vs sweep picking for example). I didn't get that far. Congrats on doing the interesting part!

Jesus, what's going on between -O3 and -O4? This type of a gain warrants investigation. Have you tried profiling both cases?

The authors of the Gecode solver could explain it better than me, but I think that -O3 and -O4 perform a first pass that pre-compute variable bounds and values, which could reduce the exploration space significantly.

That is about right. What happens at -O4 is that for every variable, the upper and lower bounds are tested, and if using the bound as the value for the variable would make the problem unsolvable, then that bound is discarded. For some problems, this can be very useful and reduce the time to find a solution significantly. For other problems, it might not find any value to remove, or the values removed might not help solution times at all. The -O5 level is the same, but instead of just testing boundary values for immediate failure, all values in the domain are tested.

As a side note, while MiniZinc uses Gecode for the optimization this is not actually anything special built-in to Gecode, it is just a usage of the library.

If you’re looking for a more practical algorithm: this problem can be formulated as a shortest path problem on the graph whose vertices are (n, fret, finger, string) tuples. A simple dynamic programming solution is to fill out a distance table whose entry distance[n, fret, finger, string] is the optimal cost of the prefix of the melody ending at note n, which can be computed as 0 if n = 1, or in terms of the entries for note n − 1 if n ≥ 2.

How did you learn this. Math undergrad? Comp sci? Something else?

You would definitely cover some graph and dynamic programming algorithms in a good introductory algorithms course.

This is one of the only huge benefits of formal CS education — those basic algorithm and discrete math courses make some problems trivial.

This example is directly mentioned in MIT Introduction to Algorithms, I would recommend it - https://ocw.mit.edu/courses/electrical-engineering-and-compu...

Check out Coursera's algorithms specialization: https://www.coursera.org/specializations/algorithms

I agree with that and I definitely will try.

As explained in the first comment, one of the motivations for the project was to learn constraint programming. The tablature generator could be a nice example to compare different paradigms and algorithms.

You can also formulate the problem as a dynamic programming problem.

Here's a Java repo I made back in college solving the simpler problem: given a tab, what's the easiest fingering to play it? https://github.com/twschiller/optimal-guitar.

It works by modeling the (1) the difficulty of hand positions, and (2) transitions

Definitely. This could be the next step in my exploration of programming techniques to solve this problem. I will have a look at your implementation.

Pretty cool. It’s nice that computing the good fingerings takes a while, makes my brain feel less ‘out of a job’ that it can do that nearly real-time. Would be good to see some harmony and how the solver would deal with multiple notes at once.

If you’re seriously writing out tabs and need some software, I’ve been using Dorico and it’s pretty damn good. It gives you a medium grade solve and then you hit a few keys to move a note between the strings where it is currently playable.

I think I understand what you mean. A trained guitar player would not need such a tool, and a beginner should probably avoid using it :). My original idea was to explore how I could rapidly get playable tablatures of jazz solos from available sheet music that I still cannot read fluently.

> It’s nice that computing the good fingerings takes a while

Actually, a few tweaks and the use of optimization options allowed to dramatically reduce the execution time for my 20-note example.

> Would be good to see some harmony and how the solver would deal with multiple notes at once.

Yes. I think it would take some effort to adapt the current set of constraints but it should be feasible.

> If you’re seriously writing out tabs and need some software, I’ve been using Dorico and it’s pretty damn good

Thanks for the tip. They don't seem to offer a Linux version though.

Check out Soundslice (https://www.soundslice.com/) for an excellent tab and notation editor. It’s web-based and hence works well on Linux.

I think in one of the algorithm lectures by Eric Demaine he outlines the idea of making a dynamic programming algorithm for good finger positions for chord progressions. Although you have to carefully design your cost function (moving the finger from one place to another is costly)

I did implement the one for normal notes and the extension to chords shouldn't be that difficult but the execution is instantaneous because the sequence is not that long.

edit: https://www.youtube.com/watch?v=tp4_UXaVyx8 this lecture

A story. Many years ago, my guitar teacher set me a challenge to learn the guitar solo to “Time” by Pink Floyd. At one point, he pointed out that what I was playing was much more easily played with a more efficient fingering. I responded by saying “But that’s not the fingering he’s using, take another listen.”

Which is to say: this sounds fun, but the expressivity of a guitar is rarely captured by a MIDI file, which makes it hard to get this “right”.

Yeah, I've seen a lot of bickering over what the "correct" fingering is for some songs that produce the same notes. For example, the repeated two-note riff at 0:17 in Nirvana - Smells Like Teen Spirit [0]. In the top tab for it on UG [1], it's tabbed as:

    E---1
    B-1--
    G----
    D----
    A----
    E----

But there are TONS of people in the comments saying it should be:

    E----
    B---6
    G-5--
    D----
    A----
    E----

Both are going to play C F, but there's so much fighting over which one is correct, and while I know due to the different thickness of the strings, there's going to be a very subtle difference between them, but I bet most untrained ears won't be able to tell, especially without having the two of them played back-to-back.

As a guitar noob, I know I'd be more inclined to play the 1-1 version over the 5-6 version. It's going to be a lot easier to finger.

[0] https://youtu.be/hTWKbfoikeg?t=17

[1] https://tabs.ultimate-guitar.com/tab/nirvana/smells-like-tee...

In my case, it was a lot easier to work out, since you needed to accommodate note-sliding. But there’s a lot the difference in strings as well.

I suspect an experienced guitarist would probably opt for 56, though for the exact same reason: it fits your hand shape. Sometimes what’s easy changes with experience. :)

I'm not experienced, and I'd go with the 11 because I can do it with just one finger.

I need to play more Rocksmith. I want to know how to play, but learning just feels so tedious.

Congratulations! It's a very nice use case!

Heads up: in English, "tablature" is an uncountable noun, it doesn't need to be pluralized.

Ok, we've depluralized it above.

I didn't know that. I will fix the README of the project as well.

Reply on news.ycombinator.com