Computers are now superior to humans in turn-based strategy games

[Daniel Shawul]

Are computers stronger than humans in the following game?
https://en.wikipedia.org/wiki/Chess_on_ ... _big_board

Probably not, but mainly because not much effort has gone into writing programs to play this game.

Although the article doesn't mention computers, in the past, a strong human player could win a game in which the game tree grew too quickly, but now Alpha Go has shown that this limitation can be overcome (Go being a game in which humans held out because the game tree grew too quickly for computers).

I am almost certain computers will be superior at this game. An MCTS+NN program often does well with high branching factor games

[jorose]

There is one game, that I am not certain of an approach which would lead to an engine strong enough to beat me. I have some ideas, but hard to say if they are enough to beat strong human chess players that have played the variant for a while.

I am referring to the fog of war variant on chess.com. I have been playing it a bit recently and can wholeheartedly recommend trying it out if you have an account. Here is a video from my favorite streamer, IM Anna Rudolph:

The rules are that you can only see the contents of a square if a piece of yours can move to that square. So in the initial position you can see your half of the board because all your pawns could move two squares forward. After 1.e4 the e pawn could move 1 square forward, so you would gain vision of that square, as well as b5, a6 and h5 due to the bishop f1 and queen d1 respectively. If black then plays d5, then white would gain vision of the d5 square as the e4 pawn could move there potentially. If black instead replies with 1. .... e5, then white would lose vision of the e5 square as his pawn could no longer move there. However, it would be easy to deduce that black must have played 1. ... e5, as no other piece could reach that square and white lost vision of the square.

My experience between facing an experienced and inexperienced player at this variant is night and day. Inexperienced players tend to give out information too readily and don't take advantage of the fog of war very well. Experienced players will often castle to weird positions and are much more cautious in their setups.

The matchmaking on Chess.com is currently suboptimal, but I imagine with the limited number of players it is hard to improve the situation. My solution is to go for quick kills against low rated players (<1500). A very common game (with black) goes 1.d4 c5 2.dxc5 Qa5!? 3. -- Qxe1 0-1. The third white move being any move not preventing queen takes king. The white player cannot see the Qa5 move in the fog of war and a low rated players with white often miss such dangers.

The state space of this game should be identical to regular chess and thus much larger than games like poker. A tree search in the traditional sense is not possible, however, one could try to make kind of a markov tree search or something like that. This is to say it is not completely hopeless as in the case of RTS games. Contrary to games like starcraft or many other computer games, there are no player reaction times involved, this makes it easier for humans and fairer to directly compare humans and AI. I don't think the methods used to solve heads up holdem and other poker domains would work for this problem, due to the much larger state space. I may be misunderstanding the methods used in those papers, as it has been a long while since I read them, so input here would be appreciated. I think humans can utilize transfer learning from regular chess very effectively, but this is difficult for current AI methods, imo.

[towforce]

Are they superior in all two player competitive turn based strategy games or there are turn based strategy games when humans are still superior?

Seduction

Have you spoken to David Levy about this shortcoming of the robots?

[Vinvin]

Computers are now superior to humans in turn-based strategy games(chess, backgammon, go, checkers...).

It's time for real-time strategy games(Red Alert, Football, Basketball, Cossacks...). Computers will soon take over the dominance in this area as well.

I thought they already had?
e.g. https://www.theverge.com/2019/10/30/209 ... Craft%20II.

For SCII the only way they could make humans competitive was to cap APM, so that the machine didn't micro-manage you to death.

Alphastar was capped :

*Agents were capped at a max of 22 agent actions per 5 seconds, where one agent action corresponds to a selection, an ability and a target unit or point, which counts as up to 3 actions towards the in-game APM counter. Moving the camera also counts as an agent action, despite not being counted towards APM.

https://deepmind.com/blog/article/Alpha ... t-learning

[Madeleine Birchfield]

There is one game, that I am not certain of an approach which would lead to an engine strong enough to beat me. I have some ideas, but hard to say if they are enough to beat strong human chess players that have played the variant for a while.

I am referring to the fog of war variant on chess.com. I have been playing it a bit recently and can wholeheartedly recommend trying it out if you have an account. Here is a video from my favorite streamer, IM Anna Rudolph:

The rules are that you can only see the contents of a square if a piece of yours can move to that square. So in the initial position you can see your half of the board because all your pawns could move two squares forward. After 1.e4 the e pawn could move 1 square forward, so you would gain vision of that square, as well as b5, a6 and h5 due to the bishop f1 and queen d1 respectively. If black then plays d5, then white would gain vision of the d5 square as the e4 pawn could move there potentially. If black instead replies with 1. .... e5, then white would lose vision of the e5 square as his pawn could no longer move there. However, it would be easy to deduce that black must have played 1. ... e5, as no other piece could reach that square and white lost vision of the square.

My experience between facing an experienced and inexperienced player at this variant is night and day. Inexperienced players tend to give out information too readily and don't take advantage of the fog of war very well. Experienced players will often castle to weird positions and are much more cautious in their setups.

The matchmaking on Chess.com is currently suboptimal, but I imagine with the limited number of players it is hard to improve the situation. My solution is to go for quick kills against low rated players (<1500). A very common game (with black) goes 1.d4 c5 2.dxc5 Qa5!? 3. -- Qxe1 0-1. The third white move being any move not preventing queen takes king. The white player cannot see the Qa5 move in the fog of war and a low rated players with white often miss such dangers.

The state space of this game should be identical to regular chess and thus much larger than games like poker. A tree search in the traditional sense is not possible, however, one could try to make kind of a markov tree search or something like that. This is to say it is not completely hopeless as in the case of RTS games. Contrary to games like starcraft or many other computer games, there are no player reaction times involved, this makes it easier for humans and fairer to directly compare humans and AI. I don't think the methods used to solve heads up holdem and other poker domains would work for this problem, due to the much larger state space. I may be misunderstanding the methods used in those papers, as it has been a long while since I read them, so input here would be appreciated. I think humans can utilize transfer learning from regular chess very effectively, but this is difficult for current AI methods, imo.

The state space of fog of war chess is larger than that of chess, simply because game ends upon capture of the king rather than on checkmate.

[Emre_1974tr]

It's been about four years since the topic was brought up. How have things been progressing on this matter during this time?

[towforce]

It's been about four years since the topic was brought up. How have things been progressing on this matter during this time?

Computers are demonstrably better than humans at many more things than they were 4 years ago.