Hacker News Reader

they'll happily enter lines where their pawn structures are shattered...

Makes you wonder if computers will essentially ruin all the novelty of innovating and discovering new tricks/strategies in age-old games. No more will genius' have their moments of brilliance and improvisation that lead to a stunning victory or upset. No more will commentators debate and regal over phenomenal victories in ages past.

With a computer, it's just the optimal play strategy and you were just playing a god who knew the quickest path to terminating your king. When a human runs with non-standard play strategies in almost any game, it's considered brilliant, innovative, game of the century, etc...

Probably. I think it basically proves that any rule structured game without randomness is solvable.

Games like go and chess are necessarily solveable by definition, right? If you mean solveable in our lifetimes, by current technology, that's something else entirely, and much less likely.

Beating human players in go is like finding a good heuristic for an NP-complete problem. Solving 19*19 go is like proving P!=NP, i.e. we don't even have tools that can approach the problem.

Not sure if this is true for Go. I'm not sure, but it seems to me that at some point a problem becomes "too complex" to solve. I.e. Go has about 2.08168199382×10^170 legal positions [1] and the number of atoms in the observable universe is only up to ~4×10^81.

I don't know if there are some theorems, thoughts, philosophies about whether this means it can't be solved, but at least it must be extremely difficult.

[1] https://en.wikipedia.org/wiki/Go_and_mathematics#Legal_posit...

In a theoretical sense, Go is certainly solvable, as we can easily construct a Turing machine that plays out every possible move, and provably terminates (given an appropriate ruleset). Practically, the universe will certainly be expected to terminate first.

There may be other ways to solve the game, but we don't know what they are. Because we know it is theoretically solvable, we cannot rule out a practical approach to solving it by some mathematical magic even if we have no idea what that would look like.

By analogy, we can prove many things about infinitely many integers by mathematical induction, but if we didn't have that technique, such proofs might seem impossible.

While mind-boggling, I'm not sure it's generally meaningful to compare counts of actual things (even atoms) with counts of possible arrangements. The latter are in a world of their own[1].

[1] https://en.m.wikipedia.org/wiki/Orders_of_magnitude_(numbers...

There is a trivial disproof of your claim.

Two players write a turing machine with at most n states with two symbols. The player that produced a terminating turing machine that produces the most 1 symbols on the tape before terminating wins.

The optimal strategy for this game is producing a busy beaver, a feat shown not to be computable.

this comment im making mainly me thinking out loud. It is not insightful:

I was thinking that for a fixed n that doesn't really work, because there are only finitely many options, but I guess if n>~2000 , ZFC cannot show the winning strategy to be the winning strategy? Is that what you meant?

Given any two machines which halt, finding the one that ends with more ones is computable. Assuming at least one of the two machines halts, which one wins can be computed in the limit? By which I mean, if the process is allowed to have a "who is currently winning" (the one that already halted if only one has, the one that halted later if both have, or neither if both haven't) thing, and the limit of that is whatever it eventually never switches from. I guess that works even if neither halt.

Uh... I'm just saying stuff you already know to try to think through it myself.

Edit: I guess the question is then, what exactly do we mean by solvable?

Do we mean that there is an algorithm that outputs an optimal move on every turn? For any n, there is such an algorithm. The one that has the correct move hard-coded. Maybe we mean that there is an algorithm that probably always outputs an optimal move? In this case, well, I suppose it depends on the axiom system. Hm.

Any rule structured game with fixed finite bounds is solvable.

But no one could play because you can't create a Turing machine that provably halts, no?

You can prove that any given Turing machine halts or does not halt, but there's no single algorithm that can prove that for every Turing machine.

The trivial case of a Turing machine that can be proven to halt is one with only one state: halted.

The trivial disproof still doesn't disprove anything about go and/or chess. Both chess and go have rules preventing repetition of moves (three fold repetition, and rule 8, respectively), and have a limited pool of possible future states. Therefore, there is no game of go or chess that does not halt. Thus, "Games like go and chess are necessarily solvable by definition, right?"

Yes but this case requires Turing machines that produce very very large (BB large) outputs and then halt. Is that provable for a specific machine?

Any specific machine can be proved to terminate or not terminate - albeit not always in ZFC. For instance, BB(10) can be computed, just as BB(10000) can, just that the latter cannot be computed in ZFC.

Probably still solvable with randomness. Add a few more layers of convolution networks.

I believe you nailed it yes. Notably, computer games do look reasonably humanlike when they're even,for example when playing another equally strong computer. But once they can outcalculate the opponent this disappears.

Compare this to lines that the humans have memorized after deep analysis, like poisoned pawn Najdorf. The play there certainly doesn't look humanlike either.

I would not describe the moves dfan is talking about as tactical. Rather, they appear to exhibit a very different positional judgment from what humans use/different strategic aims.

What you say sounds plausible, but I do not believe it is backed up by any analysis of the games.

Positional play is nothing more than our human attempt to perform short-circuit evaluation of positions by using heuristics that are easier than calculating non-forced lines precisely to 20+ ply. If you imagine a perfect chess-playing computer, it would have no need of any sort of positional evaluation — literally every move it chooses would be based upon the pure tactical outcome of having evaluated every subsequent move in advance.

When playing against humans, modern engines can accurately evaluate so much deeper than we can that their play is frequently indistinguishable from the purely tactical play of some such perfect computer (at least, once out of the opening, once the number of "good" moves is constrained a bit allowing computers to evaluate to significantly deeper ply).

You say that computers exhibit a different positional judgment, which is true in the "technically correct" sense (their evaluation function is pretty much the literal definition of their positional judgment) but at depths of 25 ply, 30 ply, or even greater, the simple truth is that they are highly willing to enter lines where their king is exposed, they have pawns doubled, they trade away a good bishop and keep their bad bishop, or all of the above (all what we'd consider anti-positional play) just because they can see a concrete outcome (a won piece, a strong attack, etc.) that we can't.

So yeah, by some definition they play positionally. But it's really by a definition that's only perhaps useful to other computers and not us humans; to us, it's significantly closer in practice to what we consider highly tactical play.

dfan is talking about go. What you're saying is accurate about chess, but go programs aren't the same as chess programs.

> Now, they play computer-like moves because "understanding" the position isn't as important as just being able to see 25+ moves ahead.

I don't think you can "see 25+ moves ahead" in Go. The branchout factor is just too big.

Well, stouset is talking about chess, but in Go, Monte Carlo Tree Search plays out all the way to the end of the game; it just does so in a much less exhaustive way, for exactly the reason you mention.

One of the nice things about Go is that branches rejoin quite a bit, mitigating some of the branching factor concerns.

You can prune more effectively. Download a program like Leela and let it analyze some positions. You'll get very deep mainlines just like in chess.

My comment was in a subthread about computers playing chess in a more human-like manner.

if we had unlimited computing power, couldn't we solve any know problem in a way that will ALWAYS outbeat any other way to solve it?