Print

Please login or register.
1 Hour 1 Day 1 Week 1 Month Forever
Login with username, password and session length

[i2amroy]

12 million ticks, thats only like 29 dwarf years! Combine that with the fact that a lot of them will fail in less ticks than that and you cut the time down greatly. Hey, with a little luck the time will actually spread it out that you never will really have to stop testing, since about the time you run out of goblins to test you will catch some more in an ambush or siege! It's easily possible!

Anyways, this thread menaces with spikes of +win+

[katana]

Couldn't you just use demons to path since they apparently seem to always have 0 speed?

[Berserkenstein]

Couldn't you just use demons to path since they apparently seem to always have 0 speed?

Demons don't set off traps or pressure plates, so no.

[peskyninja]

brain deaad......

[Nil Eyeglazed]

Of course it wouldn't really take 12 million ticks   You can see from the movie that most invaders fail within 20 steps.  Even a 10.01 goblin is more likely to fail than not before his 2nd time around the main loop.  Evaluation of invaders is limited by number of invaders, not by loop time.

There are actually a number of reasons not to use clowns-- hard to get, don't set off plates, building destroyers, fly over hatch spaces, don't path predictably.  Also, they don't have 0 speed.  All of the ones in my game right now (just checked world.dat) have default speed (900) but high attributes that make them faster than normal speed 900 critters.  Essentially, they're the worst possible clock generators.  At least FBs path predictably.  It's too bad, because it would be pretty cool to use one.

Goblin-based binary memory

This is my first-generation goblin memory cell.



If you followed the counter construction, this should be pretty obvious.  Plate/hatch combos at either end block access to escape and block return to position.  Doors on left and right allow one-way motion when opened.

You can do a few things with this cell.  You can evaluate for state (say, true or false, or 0 or 1, or north or south, however you want to think about it) via linking the bottom and top pressure plates to things like doors and hatches.  You can set the state of the memory to north or south by opening one door or the other.

There's also something a little weird you can do that's not necessary for most memory: you can send a toggle signal.  You do this by sending an open-close, as you'd get with a creature walking over a pressure plate, to the hatches in the middle.  The close signal will override the open signal sent by the goblin standing on the pressure plate, and he'll cross to the other side, no matter where he's standing.  Toggles are nice for increments-- you don't have to evaluate the memory cell in question to decide where to set it.

If you think about it, this cell has some problems.  You have to close a door before you open the next one.  That's easy enough with pressure plates, but look at the signals the goblin in this pic is sending-- he's sending an open to someplace, with no close scheduled.  That could be a problem if you want to chain a few of these together.  (Depending on what kind of effect you're going for.)  You could get around this, now that you have a clock-- limit signal propagation to certain frequencies, send resets every-other step-- but gawd, that sounds complicated.

What about if you just made it 1 tile taller and put a pressure plate in the middle?  That would be okay, because at least you could send an on-off, but the goblin would trigger it regardless of whether he was moving north or south.  You'd need to AND that signal with the state status of the memory cell to get a useful signal.  Inelegant.

Enter memory cell 2.0:



You might feel this is a little bit big for a binary memory cell.  It is.  It's designed to do everything we would ever want to do with a memory cell.  It'd be easy to reduce size if you were willing to settle for reduced functionality.

Right now, goblin is at north end-- let's call this 1, and south end 0.

We can set state = 0 by opening the eastern door, or set state = 1 by opening the western door.

We can toggle in a number of ways.  Preferred method is to send an open-close to the hatches to the east and west of the doors, because this moves the goblin in a predictable loop (clockwise).

We can evaluate for state by looking at the northeast or southwest pressure plate.

We can also send state changes by the northwest and southeast pressure plates.  These state changes are nice because they're predictable-- anytime goblin changes state from 0->1 he triggers NW, anytime from 1->0 he triggers the SE.  They're also nice because they make this system repeatable.  We can use the NW or SE to send on-off signals, which is the form we want a system like this to accept-- in other words, the output is in the same language as the input.

If we want to do a left-side or right-side toggle, we can do that easy enough too, although I can't imagine a reason you'd want to do that.

EDIT: Remember the 6-count and the 25-count?  Sometimes it's nice to be able to think in different number sets.  Decimal is very intuitive to us; base-12 is nice for something like counting months.  But binary is efficient.  Each of these memory cells is essentially a resettable 2-count.  Put goblins in the south (0) position of, say, 7 of these memory cells.  Link one pressure plate in our main QA loop to toggle the first memory cell.  Link the SE pressure plate of each memory cell to toggle the next memory cell in line.  With just that, you have a binary incrementation system that counts from 0 to (2^7)-1 -- 127, higher than we were counting before, for less work (fewer hatches and doors).

[Nil Eyeglazed]

When I said memory 2.0 could do everything we wanted, I wasn't totally correct.

If we're ever going to build a computer. we need addressable memory.  That means that we want to be able to read any of a number of memory cells (specifying the cell, of course!) and do some operations on the info that memory contains.

Addressable Memory

So I think a lot of people think dwarven computing means XOR and NOT and stuff.  Those are fine, and if I can maintain interest, we'll get to them eventually.  But central to the idea of programmable computers is addressable memory, and I haven't seen anybody talk about it.

Now, eventually, we'll have to do a bunch of operations on our memory.  But we don't want to have to build that functionality into every memory cell!  So what we're going to do is assign minimum functionality to each memory cell that we have.  We're going to allow it to write to a register or read from a register.  That's all.  We're also going to specify exactly which memory cell we want to write to or read from.  When it gets to the register, we can do all sorts of operations on it there.  It's easier that way.



That's a big picture for a single bit of data.  Unfortunately, I think addressable memory is going to be expensive, space-wise.

Still, it's not like everything in that picture needs to be multiplied.  Each memory cell needs an addressing section, but we only need one register and one of each of the three address memories (well, more than that really, if we ever want to have more than 8 memory addresses).  We'll need at least one read/write toggle, but not one for every memory cell.

There are a few other things in that picture.  There are two levers.  One is a toggle for our register for testing purposes.  The other is a clock signal.

So what we want is to either write to memory from the register or write to the register from the memory.  We want it to be a specific memory cell.  And we want the whole system to return to normal when it's done.

The simplest part of this is the actual addressing.



Each signal contributes to what's called an AND, and also contributes to what's called an OR.  Each address refers to x, y, or z position, to make things easier for us to keep track of-- that's why it's three bit, but it's easily extensible to any number of bits you need.  In this case, we're pretending our cell is at position 1,1,1.  If all three address bits are in the right position for any given piece of memory, a path exists north, through a pressure plate that will read or write.  Otherwise, a path exists south-- that's just to bring our system to reset.  You'll see.  Note that both paths can't exist at the same time!  Only one path at a time for our poor goblins.

So let's pretend that our cell is being addressed.  Our goblin has four options, each guarded by two doors.  The leftmost paths both write to the register from memory; the higher doors specify that function, as determined by the state of our read/write cell.  The lower doors are set by the status of memory: if memory is true, we write true to the register.

Obv, the rightmost paths read from the register, and write to memory.

Again, notice that only one of the four paths can ever be open at once.

Notice what happens when the goblin is done writing whatever needs to be written: he runs to his original position.  We can use that pressure plate to evaluate whether all writes have been completed.

But for right now, that wouldn't make any sense, because there's only one write occurring.  So I've introduced a clock signal.  Every time I hit that lever, it's going to trigger the pressure plates leading from the goblin's position through both the AND and the OR gates.  Doing so will get the goblin to write, if he's in the chosen cell; otherwise, he'll run through the OR, basically, just to undo the hatch reset introduced by the clock signal.

This is a working design-- I've just tested it.  There's one problem, which is that the goblin running through the OR arm makes it through too quickly-- it takes a while before he has a path back through his reset position, and sometimes he goes through reset before it actually can be reset, dragging it our further.  So you want a longer OR arm if you're going to make this.

What if you don't want a 1 bit processor?  It's not complicated.  For each extra bit you want, you have another iteration of your memory-- all of your memory, uggh-- and another instance of your register bit.  The addressing memories, however, don't have to be duplicated.  Each addressing memory should instance every addressing section, regardless of bit location.

What if you want to address more than 8 (2^3) bits?  Do you need more doors?  No, you just need a translation service for each multi-bit chunk of memory.  With 6 bit addressing, you can do the same thing, just with 12 different goblins keeping track of column, row, and level.  The choice of three addressing doors (and three addressing bits for the demo) was totally arbitrary.

Here's a movie:

http://mkv25.net/dfma/movie-2365-creaturelogicaddressablememory

BTW-- not a computer dude, just figuring it out as I go along, please excuse any terms I'm using incorrectly.  EDIT: In fact, it's not an OR, it's a NAND gate.  If it was doors instead of hatches, it'd be an OR.  Kind of the opposite of an OR, kind of the opposite of an AND.

[Saint]

This gives me an idea for a very complex use for immigrants.

[EddyP]

tl;dr

[Graebeard]

Well done, sir.

[dei]

Holy crap.

Mind = Blown. I'd try this but I don't think I can even grasp it, let alone comprehend it.

[GreatWyrmGold]

This...is...amazing. I would use something like this if I wanted a megaclock project. Two things, though.

1. While this DOES make it less dwarfy, it is easier to get 400+ cats or tame birds than goblins. To make up for it, drop failing cats/birds to give the clock a nice red coat.
2. Speed is measured in hundredths of a step between moves. To my knowledge, a creature cannot have a fractional speed.

[Jelle]

I don't know what to say. I tried figuring out what it is that you've done, but I keep getting distracted by the thought of to what end.
But then I guess in some cases science isn't about why, but why not! 

[darkflagrance]

Never stop! You are truly one of the pioneers advancing understanding of the underlying computing power of Dwarf Fortress!

Having watched the video, I have a question:

Why is it that you can forbid the doors even after goblin prisoners pass through them without the doors becoming claimed by the enemy and thus uncontrollable? Is it because the goblins are trying to escape rather than attack?

[Nil Eyeglazed]

I'd try this but I don't think I can even grasp it, let alone comprehend it.

I'm happy to explain anything.  The fun in this for me is totally in figuring it out, and I think just a little bit of understanding can get the creative juices really flowing.  Basically, anything is possible.

One thing I don't mention very much is the basic layout of controlling goblin movement.  It's totally based on Fenwah's goblin grinder designs described at

http://www.bay12forums.com/smf/index.php?topic=62798.0

and I totally owe Fenwah a shout-out.  I think a lot of people missed the fact that Fenwah's real innovation wasn't the goblin grinder trap, but the high speed switches he (she?) designed.  I straight up ripped off one of those switch designs are my basic memory cell.  (I didn't even realize that until I just looked at the thread again).

1. While this DOES make it less dwarfy, it is easier to get 400+ cats or tame birds than goblins. To make up for it, drop failing cats/birds to give the clock a nice red coat.

Isn't there a breeding limit?  And it's hard to kill off cats to get a new test set.  In the meantime, the goblins send me about fifty invaders once or twice a year.

And they don't die of old age, don't have babies, don't eat or drink, don't sleep, don't go berserk or melancholy.  Flightless birds might be okay, but they still die of old age.

Mostly, I'm just not too familiar with domestic pathing, and by now I'm really confident about invader pathing.  Like, aren't cats trapimmune?  And what if they start pathing to some vermin in the same cell as the cat?  Plus, building these pressure plates with citizens trigger would mean build hell-- think of all those stuck dwarves.

2. Speed is measured in hundredths of a step between moves. To my knowledge, a creature cannot have a fractional speed.

You notice that I talk about delay, not speed.  That's because delay is something that I can observe, whereas speed is not-- although you can express either as a function of the other.  When I say that a creature has a 9.99 delay, one way to think about that is that it's a creature with 899 speed.  That means a 99% chance of moving at delay 10 with any given move, and a 1% chance of moving at delay 9.  The probabilistic nature of movement is one reason that I have to run creatures through the loop so many times, and even then, I can't have full, 100% confidence that they're actually delay 10.

Delay should be (speed+100)/100.  But attributes modify speed, and don't do so in integer based increments-- a creature with 900 speed and high agility, for instance, might function as if it had a speed of 850, so what would high agility do to a creature with base speed 100?  Same modifier would lead to fractional modified speed unless Toady rounds it, and he doesn't have to round it to the nearest whole number.  There are other modifiers too, ones that I don't understand.  But the overall picture is that I'm not going to work under the assumption that delay*100 is an integer.  Well, at least, I don't have full confidence in that assumption, even if I do believe it.  (Notice that I have been working under the assumption that some multiplier of delay is an integer.  Otherwise, there is no way that I can ever have any level of confidence in my delay 10 goblin.)  (Heavily edited this section because I got it wrong the first time-- so if you're saying, "Wait, you were wrong and you changed it!" you're correct.)

On preview:

Having watched the video, I have a question:

Why is it that you can forbid the doors even after goblin prisoners pass through them without the doors becoming claimed by the enemy and thus uncontrollable? Is it because the goblins are trying to escape rather than attack?

Wow.  That's a good question.  I've never even stopped to think about that.  I guess it must be because they're all captured and in flee mode.  (Just in case it's not clear, those are just manual switches that allow me to set memory values before my whole computer is finished.  They can be easily automated, as demonstrated by the memory and register cells.)

Okay, excuse my tangents, and permit me a new one.

I've just been making components so far, but it's time for the big picture.  I've got to figure out exactly how my processor is going to function.  There's got to be a flowchart:

1) Read 6-bit value from memory address pointed at by 3-bit next_instruction_address register into buffer (I was calling this a register before, but now I'm going to call it a buffer)

2) Increment next_instruction_address register

3) Copy first 3 bits of buffer to 3-bit next_instruction register

4) Copy last 3 bits of buffer to 3-bit instruction_target_address register

5) Evaluate next_instruction:

 a. 000: Jump: Set next_instruction_address equal to instruction_target_address
 b. 001: Read to register 1.  Write 6-bit value pointed at by instruction_target_address into buffer.  Copy buffer into 6-bit register_1.
 c. 010: Read to register 2.  Write 6-bit value pointed at by instruction_target_address into buffer.  Copy buffer into 6-bit register_2.
 d. 011: Write from register 1.  Copy 6 bit register_1 value into the memory cell pointed at by instruction_target__address
 e. 100: Increment register 1.  Add 1 to the 6-bit register_1 value.
 f. 101: Compare registers.  If register_1 is equal to register_2 then set next_instruction_address equal to instruction_target_address; otherwise, don't do anything

6) Repeat.

So to make this I'm going to need:
 a 6-bit buffer (writes to and reads from any memory; writes to and reads from register 1; writes to register 2, instruction register, and instruction_target register)
 a 6-bit register (write to or read from buffer; increments; compares to register 2)
 another 6-bit register (read from buffer; compares to register 1)
 a 3-bit next_instruction_address register (increments; reads from instruction_target register; addresses memory)
 a 3-bit instruction_target register (reads from buffer; writes to next_instruction_address; addresses memory)
 a 3 bit current instruction register (evaluate to determine instruction)

We know how to build increments.  We know how to build memory.  We know how to read and write.  We know how to address memory.  In fact, the only thing we need that we haven't already built is a compare function.  (We'd be better off using an add rather than an increment for instruction 100-- we can always store a 000001 someplace in memory.  Hell, we could design an add that outputs to register 2, store a 000000 in memory, and then we could free up instruction 010 also, although if we did so we'd probably want a write from register 2 instruction.  But increment's good enough for now.  After all, with a loop, we can add anything anyways.)

And with that, I'll have a programmable computer.  Of course, the only thing it'll really be able to do is run a FOR loop.  I've got space for two more instructions.  Any suggestions?

[Nil Eyeglazed]

Comparison

So I said the only thing we haven't demonstrated is a compare function.  We want to look at two values and see if they're the same value.  Note that doing this for a 6 bit value is just the same as doing individually for 6 one-bit values-- if they all match up, we have identity.  If any of them don't, we don't.

This is really simple stuff-- it's what all that XOR NOR XERXES crap is.  I'm going to pretend they use that jargon just to make it look more complicated than it is



So let's see what we have here.  We have two memory cells.  We have a comparison jiggeroo.  We have output memory.  If the values of our first two memory cells are equal, we're going to set output memory to 1; else, we're going to set it to 0.



Since there are 4 possible values of the contents of 2 bits, we've (once again) got four pathways for the goblin (erm, elf) to take, and only one is going to be open at any given time:

If neither are true, the hatches on the NW permit motion, and he goes up that way.  This is a NOR.  He triggers a pressure plate that sets output = 1.

If both are true, the doors in the SW permit motion, and he goes down that way.  This is an AND.  In conjunction with our previous NOR, this is an XNOR.  He triggers a pressure plate that sets output = 1.

If one is true and the other is false, one of the paths to east is open.  These two paths in conjunction are an XOR.  He triggers a plate that sets output = 0.

When he's all done, he returns to start and waits to receive the signal to do it again.

I built this to return true if values are equal, but you can see we can make any kind of comparison of two values with just hatches and doors.

Since we need to only return true if all 6 bits are true, we can make a special kind of memory cell that sees between bits.  It's just an elongated memory cell with 6 doors in the middle, each door linked to the state of the comparison (we don't actually need our little output elf that I showed here).  When all values are true, the goblin can move.  Otherwise, he can't.

Movie at http://mkv25.net/dfma/movie-2366-creaturelogicidentitycomparison

And there is every single tool we need to build a programmable computer without using any power-- without using anything but rock and dwarves and a lot of invaders.

I don't think I'm going to do it though.  No real point.