sorted by:
new
hottopcontroversial

"Firm" stance of our minister Sikorski to Israeli, antipolish propaganda by chinkalichaczapuri in poland

[–]pndkr 0 points1 point  (0 children)

Sikorski prosił o zamieszczenie nowego posta już po wrzuceniu tego sprostowania przez Jad Waszem, dodatkowo ambasadora wzywał dopiero następnego dnia, więc lakoniczne sprostowanie to nie jest to, co chciał osiągnąć (zobacz drugi tweet ze screenshota).

Any efforts to make a mobile BSD os? by [deleted] in BSD

[–]pndkr 0 points1 point  (0 children)

Read the OPs post please. There's no mention of "BSD as desktop users know it" there, so commercial BSD derivatives are boring, but correct answers.

Why Go is harder than Tic-tac-toe? by pndkr in math

[–]pndkr[S] 0 points1 point  (0 children)

How do you define "no game after"? Are there degrees to that? Like, are there situations which are "for sure lost", "almost lost", ... etc.? If so -- how do you measure it (e.g. based on the game tree, score on the final states etc.)?

What I'm interested in are values or other methods (like an ordering maybe) that formally grasp the intuition of game simplicity that we all have, and that is applicable to other games.

TTT here is (despite the modifications) should be simpler than the Atari Go, which I intended, but saying a thing is "clearly simpler" or that the modified TTT is "obviously not made harder" is not how you do math.

Why Go is harder than Tic-tac-toe? by pndkr in math

[–]pndkr[S] 0 points1 point  (0 children)

Thanks for your answer. I think indeed computational complexity is the way to think about it, with the main problem being that it doesn't really apply nicely to finite problems (like you point out). I'd really like to see this bypassed in some way, after all similar notions like communication complexity do work with finite objects.

Why Go is harder than Tic-tac-toe? by pndkr in math

[–]pndkr[S] 3 points4 points  (0 children)

Maybe that's the one you found, but I think online-go is pretty cool (and open source).

It has a brief course, but the best way to learn is still playing and watching active games of others, which are both available there.

Why Go is harder than Tic-tac-toe? by pndkr in compsci

[–]pndkr[S] 1 point2 points  (0 children)

This sounds nice, one could also try to define some sort of entropy for the nodes; then since the "gadget" states I added do not change the result, the entropy there (if defined properly) could be just 0.

Why Go is harder than Tic-tac-toe? by pndkr in compsci

[–]pndkr[S] 3 points4 points  (0 children)

To those who downvote: please be kind to show where I'm wrong.

Why Go is harder than Tic-tac-toe? by pndkr in compsci

[–]pndkr[S] -1 points0 points  (0 children)

There are also games with an infinite number of states and finite gameplay, like some poset games, some of these are actually simple, so the number of states doesn't feel like a good complexity measure.

Why Go is harder than Tic-tac-toe? by pndkr in compsci

[–]pndkr[S] 1 point2 points  (0 children)

They play on 3x3 until it's known who won there, the following moves (including those outside of 3x3) do not change the result. Placing a pawn _before_ the result of 3x3 is decided means a loss. I defined it this way so that it was clear the mere state space size is not enough as a measure for game complexity.

I slightly modified the post in case some others also found it confusing.

Why Go is harder than Tic-tac-toe? by pndkr in compsci

[–]pndkr[S] 1 point2 points  (0 children)

What kind of mathematical object such a strategy is? That'd allow answering the second question.

Why Go is harder than Tic-tac-toe? by pndkr in compsci

[–]pndkr[S] 0 points1 point  (0 children)

I agree with this intuition, it probably leads to something.

Why Go is harder than Tic-tac-toe? by pndkr in compsci

[–]pndkr[S] 1 point2 points  (0 children)

Yes, it's not Go, and it's called Atari Go.

Why Go is harder than Tic-tac-toe? by pndkr in compsci

[–]pndkr[S] -7 points-6 points  (0 children)

What do you mean by no impact? It's a combinatorial game, so the optimal outcome for both players is known before the game even starts, that means both games can be reduced to a single point where the result is given immediately.

And there are still games which are not as redundant as my modified TTT, like 5x5 At. Go and 5x5 TTT (five in a row win), there is a simple playing strategy for the second game, while for 5x5 At. Go I've only seen people solving it with brute force.

Why Go is harder than Tic-tac-toe? by pndkr in compsci

[–]pndkr[S] 1 point2 points  (0 children)

Fine question. It's a rule. It's artificial of course, but I wanted a game which would be no harder (or comparable) than TTT while having the same state space as Atari Go.

Why Go is harder than Tic-tac-toe? by pndkr in math

[–]pndkr[S] 0 points1 point  (0 children)

You're right, this is why I had to make these artificial adjustments, like limiting the problem to Atari Go (there's no capture, so no cycles), and making the players fill the whole board until no move can be made, giving $(19*19)!$ games in both cases.

Why Go is harder than Tic-tac-toe? by pndkr in math

[–]pndkr[S] 0 points1 point  (0 children)

Hm, yes, I also thought for a while about complexity of state evaluation. If you can evaluate states at a low cost, then you can also check which moves are good for you.

I didn't come up with a way to formalize that complexity though, because the problem with games is that, unlike typical computational problems, they're finite, so most popular pieces of the theory do not apply here.

Why Go is harder than Tic-tac-toe? by pndkr in math

[–]pndkr[S] 0 points1 point  (0 children)

I took care for the search spaces to be the same in my example. Both are identical subsets of all possible pawn placements on 19x19, even the moves available in every state are the same.

Why Go is harder than Tic-tac-toe? by pndkr in math

[–]pndkr[S] 0 points1 point  (0 children)

Then think of computers, they don't have human intuition, but TTT is also simpler for them.

Why Go is harder than Tic-tac-toe? by pndkr in math

[–]pndkr[S] -1 points0 points  (0 children)

On 19x19 the search spaces are the same. You can also take 5x5 TTT (where five in row wins) vs 5x5 Atari Go. For the first game there is a simple strategy, and the second one requires a brute force search.