questerzen

3 ay öncediscuss

The given best-game solution is not optimal: Black can delay mate for another move to give a forced win in 11 ply rather than in 9 ply. Optimal is: N4 n5 N6+ k7 R4 as given, but Black can delay mate with ... n3+, rather than ...k6. The remaining moves are then: K2 n5 N8 k8 R5#. Perhaps your minimax code doesn't include moves-to-mate in the move score?

questerzen

geçen yıldiscuss

Here is an example of a case that backtracking is required where there is only one solution:

      11110
      -----
   11|....0
    2|....0
    0|00000
    0|00000
    0|00000

The sequential constraint solver fails here even though the deduction required is trivial. The first row can only be 10010 or else the 2 in the second row isn't possible.

A more difficult problem is the following:

      11 1 
      11211
      -----
    1|..0..
    2|..0..
   11|.010.
    4|.111.
    0|00000

There are two choices at this point. One option is:

      11 1 
      11211
      -----
    1|..0..
    2|..0..
   11|.010.
    4|01111
    0|00000

And we immediately run into a problem with the 3rd row, 1st col which needs to be both 1 and 0.

The other solves the problem immediately as all remaining squares are immediately specified by a single constraint.

Compared to most sudoku solves, I think this is pretty straightforward (you only need to look ahead one move to one other square). I think this would be fair game to give as a problem.

Of all the games with a unique solution that the sequential solver can't do that I looked at, almost all fell somewhere in the range of difficulty between these two. I didn't find any that require more than one move lookahead.

questerzen

geçen yıldiscuss

I realised the backtracker can stop early as soon as all squares are filled in (doh!). As a result the timings have changed dramatically.

Database generation: 25s; Sequential solver - all 'solvable' problems or abandon: 52s; Backtracking solver - all solutions: 19s; Database Lookup - all solutions: 16s;

Key takeaway is that the backtracker is not only much simpler, its actually much faster (for a computer at least) and almost as fast as looking up the answer in a table.

questerzen

geçen yıldiscuss

My sequential constraint solver (no backtracking) also found 24,976,511 games it could solve without backtracking or using more than one constraint at a time.

To get an idea of the speed difference between solving sequentially vs solving using backtracking, on my 10 year old MacBook Pro running on a single core, solving all 28,781,820 possible distinct games: - sequential solver: ~75s to either solve or abandon each problem - backtracking solver: ~175s (2.3x) to find every solution for every problem

The backtracking solver is unfairly disadvantaged in this comparison as it takes more time to solve the difficult games requiring backtracking and those with multiple solutions - for example the game {1, 1, 1, 1, 1 | 1, 1, 1, 1, 1} has 120 solutions that need to be found, but the sequential solver abandons its attempt after making no progress on its first pass through the constraints.

For the 25,309,575 uniquely determined games only, the gap in performance is a bit narrower: - sequential solver: ~60s - backtracking solver: ~120s (2.0x)

The recursive backtracking solver was a far simpler program to write though!

Incidentally, to generate a database of all possible games took ~35s and finding all solutions for all of the games by looking them up took ~20s in total.

questerzen

geçen yıldiscuss

I calculated that 25,309,575 games have a unique solution. My back-tracking solver correctly finds all answers for all of the 28,781,820 possible distinct games.

questerzen

8 yıl öncediscuss

My experience with Packt has been wholly negative.

To give an example of what to expect, my experience with one particular book on Scientific Python: * most code examples wouldn't run without significant modification, mainly due to missing lines and multiple typos * some of the text was cryptic to the point of absurdity * topic coverage was unstructured, patchy and made no coherent sense overall * the website for the book was broken and I couldn't find any way to feed my corrections back to the author

Clearly Packt put no effort into quality assurance or editing. I would suggest you would be better off waiting for something from a more reliable publisher: such poorly edited books will just waste your time.

questerzen

9 yıl öncediscuss

Funny, I just reread "What do you care what other people think?" yesterday. The parallel of NASA's design process for avionics software to TDD is both striking and revealing. People struggling with TDD could definitely benefit a lot by thinking hard about the examples of the main engine design process and avionics software. Thanks for posting!

questerzen

9 yıl öncediscuss

Other people have also suggested Latin as the most likely base language. A better discussion is provided here: http://www.science20.com/patrick_lockerby/patterns_of_latin_...

questerzen

9 yıl öncediscuss

Growing up around the tech industry in the 1980s, I found the casual racism and sexism of computer engineers difficult to deal with. The behaviour was "excused" by its being an exclusively white male niche, with "geeks" derided by society, excluded from the social core and under-valued as people. As long as this is the defining self-image of people in technology, framed by the US high-school geek vs jock enmity, there is little hope for change. This was not my experience, and it is not a frame that is useful given the dominance of technology in the wider culture. We need as an industry to stop behaving as outsiders and start to accept the responsibilities inherent in leadership. TBBT is one example of the antediluvian attitudes that no longer reflect reality and need to be changed. Cudos to the creator of this video for calling it out.

questerzen

9 yıl öncediscuss

The Black Swan has a good point to make about reliance on over-simplified mathematical models, but Taleb's macho anti-intellectualism is ultimately nihilistic since he denies even the possibility of achieving a deeper mathematical understanding of risk. But what I really have a problem with is that he has created a band of idiot Twitter acolytes who can be counted on to heap brainless abuse at anyone who Taleb chooses to disagree with, which these days seems to be almost everyone with even slightly diverging views to his. He will not attempt reasonable debate, especially when he is faced with superior erudition: in this regard Mary Beard is only the latest of his many victims. The guy is a pure and simple thug.

questerzen

9 yıl öncediscuss

I use Python a great deal, especially for tooling and prototyping and appreciate the fact that programming is fast, easy and focused on the inherent complexity of the problem. Similar positive experiences with Smalltalky and Lispy languages as embedded languages. But I write a lot of performance-critical libraries for programs that need good C/C++ interop and where C++ is pretty much the lingua franca. Swift, D and Go, for example, all have their strong points, and I plan to do more experiments when I have some time ... after this one last C++ project, though!

questerzen

9 yıl öncediscuss

So I hate C++. What I really want is the speed, flexibility, universality and simplicity of C. But I wish structs had destructors, and a way to bind namespaced related functions. Only since I basically now have classes, I should really think about adding inheritance. And I also find prototyping, testing and non-speed critical programming is a pain without a good generic container library. Containers can be implemented fairly elegantly with templates, but then I probably also need some compile-time processing ability. Oh crap, I just ended up at C++ again. And so I persist with C++ as my main language, with a constant voice in the back of my mind saying, "this is just stupid, there must be a better way. Why is there SO g-d* much accidental complexity in this language?". In my view, C++ has probably wasted more programmer hours, and added more sadness and despair to the world (at the very least MY world) than any other technology. But given my language wish list it's very, very hard not to be tempted to fire up c++-mode for just one more hit.

questerzen

9 yıl öncediscuss

I'm constantly surprised by how often I still need to look up file formats, and having a resource like this is a great starting point. Some examples from my recent experience for which using a library would be overkill / more effort: examining a .bmp file to figure out why the alpha channel got dropped during resizing; extracting meta-data (top-left pixel alpha value) from a .png file; fixing a failed library-call attempt to change the aspect ratio of an image; working out the version of an ancient document file so I could find an application to read it. We shouldn't become so dependent on libraries that this kind of simple manipulation forces us to install huge libraries and learn complex APIs for simple tasks, or else we collapse hopelessly into despair. Especially when a simple Python script and a one-page file description can allow us to do the job in a few seconds.

questerzen

9 yıl öncediscuss

It is probably a sign of a good language that the words used most should be similar in frequency to their use in pseudo code. When words like "end" (Ruby), "self" (Python), "import" (Java), "err"/"error" (Go and Node) are over-represented, it's likely a sign that the language is introducing accidental complexity. By this metric Swift looks astonishingly sane.

questerzen

10 yıl öncediscuss

I added division and brackets. This gets every number up to 5397, with only about 400 numbers still missing overall (<5%), but run time goes up to 40 minutes.

Potentiation is a problem though (particularly when combined with brackets) as Python becomes impossibly slow using bignums. (I estimate it will take several days of compute time to test all 250 million possibilities, unless I put some effort into speeding it up significantly.) But at least it would prove definitively whether 10958 is possible.

If the only goal were to search for a solution to 10958 though, it should be fairly straightforward to re-order the search in approximately ascending order of compute cost so that if a simple solution exists it will be found quickly.

questerzen

10 yıl öncediscuss

From the Wikipedia page on the JVM: "[code verification]...allowing the JIT compiler to transform stack accesses into fixed register accesses. Because of this, that the JVM is a stack architecture does not imply a speed penalty for emulation on register-based architectures when using a JIT compiler."

questerzen

10 yıl öncediscuss

I imagine you are right. But there should be plenty of scope for optimising this in the VM itself. Most stack operations are immediately preceded by a push, so hold the top of the stack in a register and the last push in another and you could avoid a high proportion of memory calls in the most common cases. Does anyone know if JVM implementations do this?

questerzen

10 yıl öncediscuss

"The best camera is the one you have with you" is a good adage. For prototyping a language needs to feel effortless so you can deal with the essential complexity of the problem and not hesitate to jump in and experiment.

For implementation, it's whatever tool best fits the job.

C is a good compromise, but it requires real discipline. The CPython and Linux code bases are great examples of how C can be wielded well in practice. But of course C also famously offers unlimited opportunities to make a complete hash of things. I certainly wouldn't recommend it to anyone as their first and only language.

An alternative approach is to be bilingual. For my current project the final code is in C++98 - sometimes there's no good alternative. But I do most of my experimentation, tooling and prototyping in Python. Python's excellent C/C++ interoperability is a huge benefit in this.

I definitely agree with the article that you shouldn't avoid hard things that improve you. But in choosing between ADA and C, the right answer is both and neither.

questerzen

11 yıl öncediscuss

Roger Penrose's Road to Reality makes use of Clifford Algebra and Grassmann Products, so at least some serious physicists are using it seriously.

Even though I had come across it before, I had a real revelation when I read David Hestenes short paper on it (from Bret Victor's website) http://worrydream.com/refs/Hestenes-ReformingTheMathematical... It is indeed beautiful to see how complex geometry and vector fields are connected via GA. I found especially revealing the relationship between electric and magnetic fields. I agree with the article that whatever its absolute merits, it would be a good way to teach new physicists. I have already ordered my copy of "Clifford Algebra to Geometric Calculus".

Whether it is actually more practical to do work in General Relativity or Quantum Mechanics, or indeed Quantum Field Theory etc., I'll have to leave for the experts in those fields. From an outsider's perspective, it is a delight to understand some of the connections between different disciplines in a more intuitive way.

In any case, I would imagine that GA is exceptionally useful for computer graphics and physical simulations.

questerzen

11 yıl öncediscuss

You can tell a lot about a person from his bookshelves and I know this is a guy after my own heart.

He has almost every non-fiction book on my Goodreads list: Books Scientists Should Read Before The Age Of 20. https://www.goodreads.com/list/show/75031.Books_Scientists_S...

Forget Amazon recommendations: this is the basis for my 2016 reading list.

Thanks for those that have worked hard to list the books!

questerzen

Submissions

The virtue of being Stupidly Determined

Monads: A useful tool for the working programmer?

The Adorkable Misogyny of the Big Bang Theory

Neats and scruffies (Wikipedia): AI battle lines

Spotting Irony With Machine Learning (2014) [pdf]

comments