It is currently Wed Aug 15, 2018 8:07 am

 All times are UTC - 7 hours

 Page 1 of 1 [ 7 posts ]
 Print view Previous topic | Next topic
Author Message
 Post subject: Hatris AIPosted: Sun Aug 06, 2017 8:49 pm

Joined: Mon Dec 29, 2014 1:46 pm
Posts: 797
Location: New York, NY
I'm back with another AI. This one took a while to crack. It was more difficult than I anticipated.

Top

 Post subject: Re: Hatris AIPosted: Tue Aug 08, 2017 12:40 am

Joined: Wed Dec 28, 2016 7:16 am
Posts: 41

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.

_________________

Top

 Post subject: Re: Hatris AIPosted: Tue Aug 08, 2017 8:20 am

Joined: Mon Dec 29, 2014 1:46 pm
Posts: 797
Location: New York, NY
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.

Top

 Post subject: Re: Hatris AIPosted: Tue Aug 08, 2017 8:46 am

Joined: Sun Sep 19, 2004 11:12 pm
Posts: 20402
Location: NE Indiana, USA (NTSC)
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?

Top

 Post subject: Re: Hatris AIPosted: Tue Aug 08, 2017 9:54 am

Joined: Mon Dec 29, 2014 1:46 pm
Posts: 797
Location: New York, NY
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.

Top

 Post subject: Re: Hatris AIPosted: Tue Aug 08, 2017 9:58 am

Joined: Sun Sep 19, 2004 11:12 pm
Posts: 20402
Location: NE Indiana, USA (NTSC)
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.

Top

 Post subject: Re: Hatris AIPosted: Tue Aug 08, 2017 11:25 am

Joined: Mon Dec 29, 2014 1:46 pm
Posts: 797
Location: New York, NY
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.

Top

 Display posts from previous: All posts1 day7 days2 weeks1 month3 months6 months1 year Sort by AuthorPost timeSubject AscendingDescending
 Page 1 of 1 [ 7 posts ]

 All times are UTC - 7 hours

#### Who is online

Users browsing this forum: glutock and 4 guests

 You cannot post new topics in this forumYou cannot reply to topics in this forumYou cannot edit your posts in this forumYou cannot delete your posts in this forumYou cannot post attachments in this forum

Search for:
 Jump to:  Select a forum ------------------ NES / Famicom    NESdev    NESemdev    NES Graphics    NES Music    Homebrew Projects       2018 NESdev Competition       2017 NESdev Competition       2016 NESdev Competition       2014 NESdev Competition       2011 NESdev Competition    Newbie Help Center    NES Hardware and Flash Equipment       Reproduction    NESdev International       FCdev       NESdev China       NESdev Middle East Other    General Stuff    Membler Industries    Other Retro Dev       SNESdev       GBDev    Test Forum Site Issues    phpBB Issues    Web Issues    nesdevWiki