Mathematics desk
< June 11	<< May \| June \| Jul >>	Current desk >

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is a transcluded archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

June 12

Are there any ways in which Bejeweled is harder than chess or go?

Sagittarian Milky Way (talk) 05:48, 12 June 2016 (UTC)[reply]

@Sagittarian Milky Way: Your question is ill-posed. What do you mean by "harder"? And how are new jewels falling to replace removed ones determined? --Jasper Deng (talk) 07:00, 12 June 2016 (UTC)[reply]

Harder, deeper or more complex in some way. As this popular game is usually seen as less strategic (especially the way most people play it, they are not thinking hard) than chess I wonder if there's some metric where this game beats chess. The replacement gems are random. Making 4 gems in a row replaces them with a gem that explodes a 3x3 hole if matched again (can be 3 in a row), or within the 3x3 hole of another exploding stone. Making intersecting matches makes a stone that destroys the row and column it's in when matched again. Making 5 gems in a row makes a "hypercube" that removes the color of what it's matched with from the visible board (it can only be matched with a single orthogonally adjacent piece). Matching a hypercube with a hypercube removes every visible stone. If what falls into place makes 6+ stones in a row, what replaces it destroys immediately adjacent rows and columns along with its own when matched again. Sagittarian Milky Way (talk) 08:25, 12 June 2016 (UTC)[reply]

I don’t think so, largely because of randomness. Chess and Go are hard because to play well you need to be able to plan well in advance, to understand the consequence of your move. In e.g. Chess you might be looking a dozen or more moves ahead. But in a game like Bejeweled you cannot look reliably any distance ahead because of randomness. Even one move might be too far to plan ahead as the random jewels that fall might form rows that remove jewels that you had been planning to use. Another factor is that you have typically fewer moves available to you, maybe as few as one, compared to the 30 or so of Chess, the hundreds of Go. So by any metric I can think of is is not hard, compared to traditional games.--JohnBlackburne^words_deeds 09:30, 12 June 2016 (UTC)[reply]

Does this mean a computer could easily beat a human if there was a large amount of humans taking it seriously for centuries like chess? What if you could see much further into the gem pipeline than just 8 rows? Eventually that wouldn't help a human much but presumably it'd help a supercomputer that had enough time to analyse. Re: removing stones you were going to use. You could match as high up as possible to ameliorate that. Except I always make a special stone before a higher match, I think that helps more than it hurts. Sagittarian Milky Way (talk) 18:27, 12 June 2016 (UTC)[reply]

In Bejeweled, however, one can still model the game as a (partially observable) Markov decision process. It's really a case of comparing apples to oranges unless you specify your metric.--Jasper Deng (talk) 09:33, 12 June 2016 (UTC)[reply]

How about "difficulty for a computer to beat the best human if as many people as chess were taking it as seriously as chess for as long as chess". Or "how many computations or bytes of memory is needed to reach one checkmate or draw (chess) or one running out of moves (Bejeweled) with perfect play". So it'd store every possible deterministic combination of stones till so far above that it'd almost surely lose before needing to extend the list even if it had perfect information and then find the probabilistically best move and then repeat the process every time it gets new information after each move. Sagittarian Milky Way (talk) 18:27, 12 June 2016 (UTC)[reply]

@Sagittarian Milky Way: You're still not being specific enough; the exact amount of space depends on implementation and algorithm.--Jasper Deng (talk) 18:59, 12 June 2016 (UTC)[reply]

An efficient implementation that's balanced instead of being optimized for space at the expense of speed or vice versa. In a non-quantum computer that's best suited for the task. Bitboards can be used if it helps despite the extra effort to write. The byte is the 8 bit byte people use to talk about space, not the 64 or higher bit byte that modern computers compute with. Sagittarian Milky Way (talk) 19:42, 12 June 2016 (UTC)[reply]

No, a byte is always 8 bits, we use WORD, DWORD, or QWORD as appropriate to denote what 32- and 64-bit computers operate on. It also doesn't answer my question because you have not defined "balanced" or "efficient" (and no, browsing game trees in general requires exponential time and hence I don't think there's a polynomial time method to solve a game exactly).--Jasper Deng (talk) 19:50, 12 June 2016 (UTC)[reply]

I once read something very old that said since the beginning computers would almost always take between 0.1 and 10 seconds to read all their memory (avg. 1 second) (still true?). They said state-of-the-art CPUs don't have enough RAM for full potential (pricy) and end life with programs/RAM so huge the lag irritates humans. Coding for the first prefers low memory for the flops and for the second the reverse. So something designed for a computer that takes 1 second to read its memory. I meant efficient by the standards of what's possible, not by the standards of computational complexity. Sagittarian Milky Way (talk) 23:12, 12 June 2016 (UTC)[reply]