Hatris AI

Discuss technical or other issues relating to programming the Nintendo Entertainment System, Famicom, or compatible systems. See the NESdev wiki for more information.

Moderator: Moderators

Post Reply
User avatar
zeroone
Posts: 939
Joined: Mon Dec 29, 2014 1:46 pm
Location: New York, NY
Contact:

Hatris AI

Post by zeroone »

I'm back with another AI. This one took a while to crack. It was more difficult than I anticipated.
User avatar
RogerBidon
Posts: 44
Joined: Wed Dec 28, 2016 7:16 am

Re: Hatris AI

Post by RogerBidon »

Hey great reading, thanks.

I wonder what would happen if the AI only evaluated the current hats pair for placement consideration, without care to the next-pair. Would it be largely detrimental to the number of spawns before gameover or not? From pure feeling, it seems that what is immediatly good is also good in the long run, the evaluation function already takes care of strategy by aiming at homogemeous piles.

Conversely, what would be the effect of searching farther than the next pair? It could be possible to verify all possibilities some turns in advance, but it is exponantial. Maybe some smart guessing of what would be the worst pair to handle may allow to handle just that for some turns after the "current next-pair". Simply simulating the deterministic PRNG can also predict series of pairs perfectly, but can be argued as cheating.
User avatar
zeroone
Posts: 939
Joined: Mon Dec 29, 2014 1:46 pm
Location: New York, NY
Contact:

Re: Hatris AI

Post by zeroone »

Thanks for checking it out.
RogerBidon wrote:I wonder what would happen if the AI only evaluated the current hats pair for placement consideration, without care to the next-pair. Would it be largely detrimental to the number of spawns before gameover or not? From pure feeling, it seems that what is immediatly good is also good in the long run, the evaluation function already takes care of strategy by aiming at homogemeous piles.
Committing to a placement too early using only what is immediately good ignores the best overall solution. The quantitative different is actually quite considerable: an entire order of magnitude. This is the primary why most sequential puzzle games expose one or more next pieces to the player. From my own experience of playing Tetris for too many years, I've learned to always think in terms of pairs, not just the currently falling piece. Still, it is always possible that some significant piece exists just beyond that horizon that would effect the current placement had the information been accessible. The evaluation function is only a default, general strategy; it's the best guess after taking into account all of the available information. It's good at dealing with average cases, but it can't compete with specific knowledge.
RogerBidon wrote:Conversely, what would be the effect of searching farther than the next pair? It could be possible to verify all possibilities some turns in advance, but it is exponantial. Maybe some smart guessing of what would be the worst pair to handle may allow to handle just that for some turns after the "current next-pair". Simply simulating the deterministic PRNG can also predict series of pairs perfectly, but can be argued as cheating.
In the case of Hatris, check out the description of the PRNG in the article. By measuring the number of frames in between spawns, it's actually tied to the behavior of the player. There is no way to programmatically generate more of the sequence.

Of course, the plug-in could always just replace the PRNG with one of it's own, providing it with full knowledge of the entire sequence. Every next pair that it took into account would improve the placement of the current pair, albeit with diminishing return (the distant future has only a minuscule effect on the present). It should also be noted that while some sequences would enable the game to go on indefinitely, the vast majority of sequences lead to Game Over regardless of placements chosen; however, if the full sequence were known, then in principle, it is possible to search for the optimal placements that would push Game Over out as far as it could possibly go.

The evaluation function's job is to essentially ask if the playfield can readily accommodate whatever is to come next regardless of whatever that may be. It could actually try all 36 possible hat pairs to find out. Or, it could evaluate a sampling of short randomly generated sequences to see the outcomes and average them together. But, as mentioned above, whatever it does, it is really only providing an average answer. It's the best guest when there is nothing else to go on.
Last edited by zeroone on Tue Aug 08, 2017 11:03 am, edited 1 time in total.
tepples
Posts: 22705
Joined: Sun Sep 19, 2004 11:12 pm
Location: NE Indiana, USA (NTSC)
Contact:

Re: Hatris AI

Post by tepples »

Do these AIs you make require the (comparatively) massive processing power of a modern PC? Or could they practically run on the unused cycles of a 1.8 MHz 6502 CPU?
User avatar
zeroone
Posts: 939
Joined: Mon Dec 29, 2014 1:46 pm
Location: New York, NY
Contact:

Re: Hatris AI

Post by zeroone »

tepples wrote:Do these AIs you make require the (comparatively) massive processing power of a modern PC? Or could they practically run on the unused cycles of a 1.8 MHz 6502 CPU?
Well, first off, the AIs that I make are written in Java and I'm testing on a Win7 box built ~10 years ago. And, they are written as plug-ins for my Java-based emulator, which requires such a box to function at all.

But, almost 20 years, back in college, I took a course on microprocessors and I used that opportunity to implement a very similar algorithm for a 1.8 MHz Z80. It consumed the entire CPU and it took a few seconds to yield each result, but it worked.

It's very unlikely that the full algorithm could be made to operate in unused 6502 cycles. The closest comparison is the AIs that some of the NES chess programs employ and they consume nearly 100% CPU and take a few seconds to respond, like my project from 20 years ago.
tepples
Posts: 22705
Joined: Sun Sep 19, 2004 11:12 pm
Location: NE Indiana, USA (NTSC)
Contact:

Re: Hatris AI

Post by tepples »

Then I guess I'd have to take my question about the very basics of making the CPU opponent in a 2-player falling block game to another topic.
User avatar
zeroone
Posts: 939
Joined: Mon Dec 29, 2014 1:46 pm
Location: New York, NY
Contact:

Re: Hatris AI

Post by zeroone »

tepples wrote:Then I guess I'd have to take my question about the very basics of making the CPU opponent in a 2-player falling block game to another topic.
The first step would be to create a routine that could generate a subset of all of the possible available moves. A subset of them, because it may not be practical to identify all of them. For example, in Tetris, to fully work out the complete set, which includes sliding pieces under overhangs, requires a breath-first search or a similar spanning algorithm. However, a simple pair of nested loops could rotate the piece into the 4 possible orientations and position it horizontally (dropping it straight down from there); that's a quick way to get a significant subset of the available moves.

Next, you need a routine that simulates the effect of each of those potential moves. This can be done with some sort of apply and undo mechanism. For instance, before dropping a piece into the Tetris playfield, the entire playfield can be copied to a temporary location. After a drop, rows maybe cleared. That completes the simulation of the move. And, it can be undone by copying back.

Finally, you need an evaluation function to identify the best move within subset, applied just before each undo. It would have to be some sort of heuristic that operates in a timely manner of course.

That's the basics anyway.
Post Reply