This isn't going to be a very smart question. Well I think it can't be because its too easy for it to be novel, but I need to understand it.

I'm thinking of a game like go, which is not solved because of the complexity. But there are smaller versions (ie 3x3 or 4 x 4 boards perhaps) that I am thinking are solvable. So it seems there must be a cusp in between the size of board that is solvable and not solvable.

Chess could have a similiar cusp in that many end game spots are solvable but some situations prior to end game situations are not solvable and so there is a cusp there as well.

So how does this work, it goes from computable in a smaller situation but from a previous move the tree is too big to compute?

From an unsolvable spot, it cannot be that the next correct move is to move into a solvable line (wouldn't this imply the solution is observable?).

I am interested in this cusp and working the game backwards.

My only resolution is that there must be far too many end game possibilities to work backwards in this way. But then on the other hand I think then that categorizing end game spots would be the way to solve a complex game, because it would be far less intensive than brute forcing the entire game.

Am I misunderstanding something? Have I answered my own inquiry?

If I haven't made a clear "question" I think it would be easier to understand if there was an example of this cusp ie 4 x 4 go board is solvable but 5 x 5 is not. I would like to examine that cusp.

You seem to be mixing up "solved", "solvable", and "unsolvable".

Go for a given grid size may be solvable, but the difficulty in coming up with an optimum solution i.e. solving the game, is that the more possible move choices (and possible responses) the larger the problem.

The calculations are simply much much larger. On a 3x3 board, there are far fewer opening moves and responses to consider than on a 4x4 grid and beyond. The size of the game tree grows at a rapid rate.

Unfortunately, your presentation is completely jumbled up and doesn't really present a clear picture of what you have in mind.

The reason Go is "not solved" is because of a lack of computational power and not really "complexity." We understand exactly what we would need to do to solve it. It's just that computers are too slow.

You seem to acknowledge this distinction, but then when you start talking about the "cusp" it starts to go sideways. There is no "cusp" in the sense that you can kind of draw the line where you want. Are you happy to wait 2 days for the computer to determine the right move? What about 2 weeks? 2 years? Or do you want an answer in 2 seconds?

So I think you're misunderstanding a lot. Even something like categorizing "end game spots" is difficult because there's rarely a clear definition for when one enters "end game" (such as in Chess or Backgammon). And so such categorization schemes are hard and you've got a different problem to solve (which has probably been worked on, though it's probably nothing like what you might be thinking).

Ah, now you help me understand. So is there no possibility to create a solution that doesn't involve brute force?

Yes and no.

I believe you cannot verify that you have the optimal play except by brute force for these types of games.

The AIs these days are finding "strong" plays using deep learning, but that's different from "solving" the game. It is often the case that learning algorithms can make some pretty obviously bad decisions if it's put in a situation that it's sufficiently unfamiliar with.

If you really want to learn about this stuff, you might want to aim for this: https://www.udacity.com/course/deep-learning--ud730

I haven't gone through the course myself, so I can't say much about the level of difficulty. If you have no background in machine learning, it could well be over your head. If that's the case, you might want to search for some other machine learning/artificial intelligence courses and work your way up. There's a TON of free material out there, including the lectures from a graduate course in machine learning from Stanford.

Yes thats what I was conflating, but as I understand we do solve simpler games using math rather than brute force. Is that true to say? So I was more thinking if there was a novel approach then we might be able to pass the 'cusp'. But I guess in this sense the 'cusp' is really our computational limitation over time?

Some games have properties that allow easily described and coded strategies to be proven optimal even as the game expands to an arbitrarily large number of choices/positions. Others don't (or aren't believed to), and chess is strongly in that camp for the vast majority of positions (totally blocked positions can be proven drawn without full enumeration to the 50 move rule, etc)

It would depend on what you mean when you say "by math." Take Tic-Tac-Toe. It's a simple game, but in what sense is that one solved "by math" instead of "brute force"? That you can reduce the space of first moves into three equivalent moves (corner, edge, center) instead of nine (four corners, four edges, one center)?

Yes and no. Games like chess have more possible games than particles in the universe, but there are ways to prune the game tree a bit. So if someone comes up with a clever pruning method, it may be possible to reduce the search for optimal plays by an order of magnitude or three. But that still leaves us with very large computational problems.

Lol, yes https://steemit.com/programming/@jok...ing-autohotkey

Right and I suppose there is a limiting the possible ability to prune (ie compress)?

So in regard to go, I'm sure we can solve smaller boards, and if we take the smallest board we can reasonably solve, I suppose the next board size up is significantly bigger. There must be a measure of this. Not sure I could find some quite relevant game theory videos (most specifically on go). I will try.

It's hard to accept that we can't solve these games with mathematical shortcuts and yet humans can still beat computers. Really hard for me to understand. The human has no basis to know they are "correct" other than they win.

In a game like poker, there is really enough empirical evidence, ie for a live player, especially as the field tends toward equilibrium (I realize we are allegedly far from it). I think I will inquire further into go, in order to understand this.

There's probably a way to measure that, but I don't know what it is. But this is also the type of game where knowledge of a sub-game is only sometimes useful. For example, a full knowledge of getting 3 in a row in a 3 by 3 Tic-Tac-Toe board doesn't inform you about the trivial nature of getting 3 in a row in a 4 by 4 Tic-Tac-Toe board.

The computers kill us these days.

The deep learning algorithms are in the same condition.

Modern artificial intelligence learns from playing lots of games and that stands as the empirical evidence. Computers struggle with this because two identical situations (say an open-raise from UTG) can lead to two different decisions based on historical knowledge of the player's tendencies as well as other player dynamics at the table. But computers don't really have a means (yet) of picking up those sorts of details, and so still get crushed in multiway situations.

Right, I think that suggests we could study this evolution of an expanding game.

Bah, I can be terrible with language. By "can" I meant "possible", I am surprised its even possible, for example for a human to win at a game of go. And I found an example but its from a year ago, and I would believe that possibility has changed already.

Yes they simply have a computational advantage. But it's interesting then to consider the limits of that advantage.

That's back to the unbelievable part for me how can a human pick up on these tendencies and not a computer. Do you mean to imply they are social, or cultural? Hex is another game that just seems solvable to me by some sort of reduction/recursion. But I have new questions now to go after.

So games then are that type of problem that you must brute force in a sense. Well this might not be true but the games that are easy or "broken" ie solvable I think evolve. Or we can ask what are the factors of a good game. I think most games evolved through play and rule change and this is how we have these incredibly difficult to solve games that seemingly still have some finiteness to them (I probably don't use the term finiteness in the correct way).

It's all incredibly interesting to me. I need more direction to explore it though. I appreciate the points (from everyone).

I suppose one could try. But it's clear that novel strategies can appear when we expand the game and it's not clear whether those strategies are in any sense predictable from the smaller games.

Look up AlphaGo Zero. It's a Go-playing AI that learned completely independent of human interaction. It learned by simply playing against itself and learning as opposed to being fed positions to watch and learn from.

My suspicion is that humans take mental shortcuts that computers can't. This gives us the ability to make leaps of "intuition" that maybe aren't sufficiently grounded in the data. This both helps and hurts our ability to play games of incomplete information. We're just better at filling in blanks than computers (for now, at least).

And yes, we also have information such as social cues that we can glean information from to help us make decisions.

Anyone ever play tic-tac-toe 5 in a row on graph paper? Play until the paper is full and player with most 5 in a rows wins. It did not seem like an easy game when I played it.


PairTheBoard

https://en.wikipedia.org/wiki/Gomoku Not sure how to ask this properly, but I think it will be understable enough, that seems to suggest the possibility that some games are "hard" math problems, that can be relied on to require brute force?

It means our progression on the strategies run at the cusp of the amount of iterations or game spaces analyzed?