Complexity and games

An Alternate Perspective A blog about looking at, and approaching, game design from an uncommonly different perspective. Justin Leingang. Patron Badge for through A "base rule" is an unmodified rule that can't be removed from the system without radically changing the game design. What we can measure, and what I will be looking at here, is the correlation between game complexity and rating. While this correlation is compelling, its existence in itself is insufficient proof of bias.

And the same correlation may or may not also exist in the general population of board game players. That leaves us with 4, game titles. Each dot represents one game title. One way would be to calculate the linear least-squares regression. The R-squared is 0.

And the P-value is 0, which means the probability of such correlation happening by chance is close to 0. We will then calculate the median rating for each bucket. The difference between median ratings in each bucket is roughly consistent with the slope we calculated earlier. We can, however, try to come up with a rating adjustment that takes into account how much harder it is to get rating points for lighter games.

One way to achieve that is to add rating points to the games proportional to the slope of the regression. We also need to choose a level of complexity as standard i. Lebed, F. What organizational leaders should know about the new science of complexity.

Complexity , 6, 14— Launder, A. But to me NP-completeness is not the end but the beginning of the study of a game: it shows that the game is complex enough that we can encode interesting computational problems within it. If a game is in P, it becomes no fun once you learn "the trick" to perfect play, but hardness results imply that there is no such trick to learn: the game is inexhaustible.

And of course NP-completeness or PSPACE-completeness doesn't even rule out the possibility of computing game values exactly; true, it seems to imply that worst-case-exponential algorithms are required, but there is still plenty of interesting work in designing, analyzing, and implementing such algorithms.

There is a curious relationship between computational difficulty and puzzle quality. To me, the best puzzles are NP-complete although some good puzzles are in P, relying on gaps in human intuition rather than on computational complexity for their difficulty. Some puzzles are even harder than NP for instance, sliding block puzzles and Sokoban are PSPACE-complete but to me this means only that the problem can have an annoyingly long sequence of manipulations in its solution.

For two-player games, one encounters a similar phenomenon at a higher level of complexity. However some games are harder, EXPTIME-complete, which to me means that it may sometimes be necessary for a well-played game to go on for a tediously long sequence of moves.

Perhaps some games or puzzles in which the players start with incomplete knowledge of the game or puzzle configuration might lead to other types of completeness e.

MA-completeness or P-completeness for finding the starting move most likely to succeed, but I know of no such results. I primarily list here real games and puzzles, games that were invented to be played, rather than to be analyzed.

So I'm not including some of the more artificial entries in e.