Metal Fatigue <sethb-e+AXbWqSrlAAvxtiuMwx3w@xxxxxxxxxxxxxxxx>:
> >>>>> "MJD" == Mark Jason Dominus
> >>>>> <mjd-ZxR0713JXSrQT0dZR+AlfA@xxxxxxxxxxxxxxxx> writes:
>
> MJD> then the player can never complete any rows, and will lose
> MJD> quickly.
>
> Not true if the board is an even number of columns wide.
>
> * * * * * *
> ************
> * * * * * *
Whoops. Somehow that completely escaped me.
Brett Sanger <swiftone-odjg+bCo0yxg9hUCZPvPmw@xxxxxxxxxxxxxxxx>:
> > One quiz possibility I've had in my ideas file for some time is to
> > write a demonic tetris game that sabotages the tetris player as badly
> > as possible by figuring out which pieces fit the current board
> > configuration the worst and then sending the player those pieces.
>
> As you mentioned, this is the computer trying to make the player not
> win, which in fact is not hard
It's not? Are you sure?
> (nor is it fun).
I think it would be fun. Here's why: I started by thinking about
computer tetris-playing programs. Writing a program to play tetris is
an interesting exercise by itself. But it would probably win a lot.
And how do you adequately test such a program? One way is just to
look at the final score. But if the computer player is sufficiently
good, there might not *be* a final score; it might be able to play
forever.
One way to judge the relative quality of computer tetris players is to
match them up against a series of diabolical tetris games and see
which ones do the best.
This has the added benefit of simultaneously judging the relative
qualitiy of the diabolical tetris games themselves.
> Instead, why not make the computer give the player the most
> interesting piece, where interesting is defined as: 1) completes the
> minimal number of rows (this will never allow a "tetris") (I have
> trouble believing this will ever allow you to complete more than one
> row) 2) It maximizes the "bumps" (changes in height) if placed in
> the position that will complete the most rows.
That's an interesting idea, and I look forward to discovering whether
it works better than the other strategies that are suggested.
> Unfortunately, I see this as being pretty computationally intensive.
Well, that's just part of the challenge.
> (see MIT paper on Tetris bing NP-hard).
The nice thing about most NP-hardness results is that they are of
relatively little practical interest. NP-hardness results are usually
concerned with the worst-case behavior of problems. But the
worst-case behaviors usually appear only in a small fraction of
specially-constructed problem instances. Typical instances of NP-hard
problems are actually easy. For example, it's been known for some
time that almost all instances of 3-SAT (the prototypical NP-hard
problem) and 3-coloring are easy, either because they're
overconstrained (and so a quick search will rule out the possibility
of a solution) or underconstrained (so a quick search is likely to
find one of the many many solutions). Only a very few instances are
right on the boundary of these regions. I would expect almost all
tetris problems to be of the easy variety. (For more complete
details, see "Where the *Really* Hard Problems Are" by CHeeseman,
Kanefsky, and Taylor.)
Moreover, no problem of this type is NP-hard when the size is bounded
in advance. (All such problems are trivially O(1), although this
result is practically even more useless as the result that the problem
is NP hard to begin with.) A computer Tetris player operates on a
fixed-size board. Even if the algorithms it uses are in principle
exponential-time in the size of the board, it may not matter, since
they might work adequately on the board that's actually being used.
Peter Scott <Peter-ZDDqFG7rOwU@xxxxxxxxxxxxxxxx>:
> Even an ordinary tetris game could be demonic through sheer bad luck.
Yes, but perhaps with probability zero.
> Why not turn it around and write an angelic tetris where you send the
> player the *best* piece and deduct points if they don't put it in the
> right place?
See my notes above about using it as a test world for computer tetris
players.
"Wyatt Draggoo" <wyatt-ZfDCUQqI7a9BDgjK7y7TUQ@xxxxxxxxxxxxxxxx>:
> What about having to stick to the original probability curve while
> coming up with the demonic pieces? The program couldn't give all Z pieces,
> because those can only encompass, on average, 1/7th of the playing field.
> However, it could choose inopportune pieces occasionally that still fit.
This was like what I had in mind. What I was hoping that people might
discuss is ways of actually enforcing this condition. It's not clear
to me how you should even state the restriction. Do you want to say
"One piece in every group of seven must be an L," for example? That
would rule out three consecutive L's, which is something that might be
generated at random. The diabolical player should be allowed to send
17 Z's in a row as long as it hasn't sent any Z's for a long time,
shouldn't it?
Dan Schmidt <dfan-Wp14Qwfl6ew@xxxxxxxxxxxxxxxx>:
> Or he could have a 'hand' of N pieces at all times, which gets
> replenished from some source every time he drops a piece.
Maybe with this structure, the diabolic player could save up the Z's
in its hand and then release them all at once.
Abigail <abigail-GOYLEsvzKwE@xxxxxxxxxxxxxxxx>:
>
> Maybe it's just me, but eventually I always lose Tetris not because of
> lack of 'good' bricks, but because of the vertical speed - often in
> combination with hitting the wrong button.
>
> I could imagine several 'demonic' Tetrisses: high falling speed of the
> blocks; rotating a block implies falling; rotating angles are random;
> remapping of keys.
I hope my explanation above about the context of the problem makes it
clear why I wasn't considering these possibilities.
|
