C++ Game: "Pegged"

[cabal]

Argh. x_x Last year my C++ teacher's wife had a baby and as a result that class was really damn easy. Of course everyone in that class got a 2 or 3 on the AP Exam, so now my teacher thinks he was too easy on them when in fact he was never there to teach. Anyway, this year he's really killing us with programs and quizzes. Life can be so unfair sometimes.. u_u

*ahem* Anyone ever played the game "Pegged?" I think that's what it's called. There are 15 holes in a triangular formation with one hole vacant (all other holes are filled with pegs). Each level has one more hole; 1 hole is on top and 5 holes are on the bottom. You can only jump over a peg into an empty space and the objective is to get rid of all of the pegs in as little turns as possible. Well, being the evil programming freak of nature he is, my teacher wants us to make the computer play itself and find the combination of jumps that would result in the fastest game. All of this just after recursion (which it must use, btw >_<) and before binary trees and all of that complicated stuff. Pure evilness..

I have no idea how to approach this. He suggested using an AP Vector (or built-in array, for those of you that don't use the AP Classes) of booleans to check if the spot is open or not. He also said there was a pattern but of course didn't tell us. If you guys have no idea what I'm talking about with this it's ok. :O

[Ninjaa]

OUCH! That's one god-awful assignment! You are supposed to design some sort of artificial intelligence in a programming class? That's just downright mean.

Sorry, but I haven't ever played the game, so I can't help you. I just offer my sympathy.

[cabal]

lol I know.. it's ridiculous. It is an AP class but still.. we're not even through the damn first semester yet. Some genius kids in that class have the biggest egos I've ever seen. There are two kids that need to be given an A and kicked out of the class because they make it hell for all of us.. for example, one of them got the program done the evening the teacher assigned it! RRRGH talk about making us look bad. He had his stupid program running all night and it supposedly made a 89 megabyte text file of possible moves. These two kids have been writing programs since they were in their cribs. It's sick and demented. :P

[Ninjaa]

Yeah, I know what you are saying. I am in an AP class, and we haven't gotten anything NEARLY that hard. The most difficult thing we have gotten so far is a linked list class.

As for the two kids who make life hell, just beat them at their own game. When you score higher than them, it's the most gratifying thing in the world. I've done it before, and it was one of the greatest things ever to hold my exam mark in front of their face and tell them to suck it. ;)

[ammoQ]

Take it easy ;) with recursion - it would be harder to make it without recursion. Can you become a bit clearer about the rules of the game? Is the only possible move a jump of a peg over another peg into an empty hole? Or can a peg be simply moved from one peg to an adjacent hole? Can a peg be simply moved out at the border? If not, how can you get rid of the last peg?

[RZetlin]

:eek2:

Oh man, that's more evil than trying to program the computer to counteract every player's possible move in tictactoe!

Do you know how many different combinations you have to consider for Pegged?!

[cabal]

I'll start with the most sadistic, evil stuff first. x_x That one kid who had his program done in a day ran it on my teacher's computer during the period today and at the end it had come up with around 6000 combinations. I don't know why the computer didn't run out of memory, heh. If you mean combinations of what slot in the board can jump to what other slot, there's a big table that I don't feel like writing. ^_- I'll explain that later.

Ninja, that's impossible for me. These two kids have computer chips in their brains, I swear. There is no way I can beat them ;P

Ok, here's what the board looks like:

0
1 2
3 4 5
6 7 8 9
10 11 12 13 14

(The board is triangular but the message board won't let me put more than one space before a number)

The empty hole can be anywhere but for purposes of simplicity I'm assuming the empty space is 12. The rules of the game are pretty simple: you have to jump a peg over another one into an empty slot. If you can sucessfully do this, the peg jumped over is removed. Eventually you should have one peg left. The person who can do it in the shortest amount of turns wins.

For example, if 12 is open and all others are closed (have pegs in them), a peg in slot 10, 3, 5, or 14 can jump into slot 12. From there recursion is supposed to create 3 more copies of the matrix and then the game continues playing itself in those different matricies, increasing the number of variants each time a jump is made. Ex. 4 matricies would be created in the first iteration if 12 is the open slot: one with 10 and 11 open and 12 closed, one with 3 and 7 open and 12 closed, etc. Argh x_x; I dunno how easy this is to understand but I'm teaching it and I pretty much don't get it, lol.

btw my teacher said he was suprised we didn't complete the program today.. -_-

btwbtw (o_O) I've got a question for those of you that use C++. When you compile and build and execute and all of that good stuff, and you get to the DOS window, is there any way to force the text size to a certain amount, say 7x12? It keeps resetting to "Auto" everytime I close and re-open.

[RZetlin]

Originally posted by cabal
I'll start with the most sadistic, evil stuff first. x_x That one kid who had his program done in a day ran it on my teacher's computer during the period today and at the end it had come up with around 6000 combinations.

:eek2:

That kid is making the rest of you guys look bad!

[ammoQ]

I don't understand why you say "shortest amount of turns". When you start with 14 pegs and have to remove 13 of them, and all allowed moves remove 1 peg, you will be at the end after exactly after 13 moves (if you are successfull).

But anyway, I can tell you how you could make it - and it will be so m*f* fast nobody will believe it ;) I made it in C, since I'm not fit in C++, but you can change this. Fast means: first result in 0.004 sec, all results in 3.3 secs on a Duron 1100.
The key to make it fast is to code it all in binary operations; the board itself is represented in a int where each bit represents one field of the board (bits 15-31 are not used). There are 36 moves that can be possible, depending on the sitation on the board. To check if a move is possible, the board is compared with a mask called "filled" using & (bitwise and), and with another mask called "empty" using | (bitwise or).
If the tests are sucessfull, the result is created using "^" (bitwise exclusive or).

Using int instead of a complex data type make many operations much faster and easier to realize, since you have no need to create and destroy objects etc.

Check out the source available at http://members.chello.at/erich.kitzmueller/ammoq/pegged.c

P.S.
<tt>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;0
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;1&nbsp;&nbsp;&nbsp;2
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;3&nbsp;&nbsp;&nbsp;4&nbsp;&nbsp;&nbsp;5
&nbsp;&nbsp;&nbsp;6&nbsp;&nbsp;&nbsp;7&nbsp;&nbsp;&nbsp;8&nbsp;&nbsp;&nbsp;9
10&nbsp;&nbsp;11&nbsp;&nbsp;12&nbsp;&nbsp;13&nbsp;&nbsp;&nbsp;14
</tt>

[ammoQ]

Optimized the mask operations, so it's a bit faster now (and also a bit shorter).

Download at http://members.chello.at/erich.kitzmueller/ammoq/pegged2.c

[Ninjaa]

heh. Good job ammoq. You are now my favorite person on these forums. ;)

time to show up those two suck ups I think. ;)

[cabal]

holy crap! e_e;;; I agree with Ninja.. you're the man! ^_^ Ok, lemme see if I can understand this. There's a chapter in my C++ book about bitwise stuff. :O I'll prolly have lots of questions so check back, heh.

edit: Ok, no sense in double-posting. I think get what's going on. Geez.. you're a genius ^_^ A few questions, though.

In the main function when you say that you checked whatever number of boards, is that the amount of 13 move sequences that work? I ran it starting at 0 and it was different so I'm a little confused. The program needs to tell the user how many different 13-move sequences are possible.

What's all of the stuff in your output_board function? It's prolly bitwise stuff but I have a terrible grasp of that, heh.

Please explain what the pegged() function does. I see it uses bitwise things everywhere... x_x

What's the ~ for in this line?
pegged(~(1<<firstempty), 0);'

Ok.. lemme see if I can figure out what's going on with the bitwise stuff.

[ammoQ]

"count" is the total number of boards checked (this may include the same board many times when it can be reached by different combination of moves; to get the total number of successfull combinations found, move the "count++;" line to the part marked //Sucess.

output_board(): (1<<3) is 1 shifted 3 bits to the left, so it's the same as 8. Could have written the constants (like 256,512,1024,2048 etc.) but this would be even harder to understand.

pegged(): given one board, it tests which moves are possible; for each possible move, it calls itself with the board which results after the move.
& is "bitwise and", used to focus on a few bits; ^ is "bitwise exclusive or", used to create the new board (it should be easy to recognize that for the 3 fields involved in a move, each of them flips it status - the two filled fields are afterwards empty and the empty field is filled then - this can be expressed as an "exclusive or"-operation.

pegged(~(1<<firstempty), 0);

This starts the search for combinations.
~ is "bitwise not", 1<<firstempty is a 1 moved to position "firstempty" (shifted firstempty bits to the left), so ~(1<<firstempty) is a completely full field except one 0 at bit #firstempty.

[cabal]

I pretty much get everything except for the pegged() function (figures -_-)... is there any way to make this fast and not use bitwise stuff? I'm not asking you to code a whole nother program, you've done more than enough already; it's just that bitwise stuff is confusing.

I'm trying to convert some of this into a program that uses arrays and things like that because we have to be able to explain how we coded the program to the whole class. x_x;;

[ammoQ]

Of course you can do it with arrays and strings, but it will be much slower... And I doubt it would be easier to understand.

It's better to replace the misleading variable name "result" by "mask"; I changed the program this way (second download).

Let's have a look at the bitwise operations, this is the stuff you would have to do with strings:

001010110101101 "board"
000000111000000 "mask"
000000110000000 "board &amp; mask"
000000110000000 "filled"

since "board &amp; mask" is equal to "filled", the move is possible; it is calculated by using ^:

001010110101101 "board"
000000111000000 "mask"
001010001101101 "board ^ mask"

The same again, now all bits not tampered replaced by x:

xxxxxx110xxxxxx "board"
000000111000000 "mask"
000000110000000 "board &amp; mask"
000000110000000 "filled"
xxxxxx001xxxxxx "board ^ mask"

[Zapages]

Good thing I didn't that AP this year...

Sorry to hear that your AP class like hell... I had it last year, couple of guys who used to make everyones life miserable in class and then at home they would finish the program in one day and play games all day during the rest of the classes...

As for the window... I don't remember exactly but I think its like this (name of the file).windowsize(x1,y1,x2,y2) or something close to it...

[cabal]

What are the 3 numbers you're using in that example? I just need to be walked through one iteration and I should be ok. Is there an easier way to determine what a number is in bitwise really easily? When you say 1 << firstempty, you mean shift the value in 1 (0001) 12 to the left, right? What is the purpose of mask and filled? How does this work logically? i.e. How did you know to use a mask and filled and all of that stuff? One more.. x_x ok, I can do most of the bitwise stuff, but I'm getting confused here:

1 << 12 is
1000000000000

so shouldn't ~(1 << 12) be
0111111111111

it says the number is -4097.. how do you get a negative binary number? o_o

[ammoQ]

Well, you are right about 1&lt;&lt;12. it's 1000000000000 in binary representation, which is actually 4096 if you output it in decimal. But better don't think about it as a number, simpliy keep in mind its 32 bits, where 15 represent the board and 17 are not used.

~4096 equals to -4097, that's because of how negative numbers are represented. But you better ignore that because we don't care at all what this word (32 bits) mean as a number. Think of it as an array of bits.

"mask" is used to cut out the 3 bits that are relevant to determine whether or not a move is possible. "filled" is the required values of these 3 bits so that the move is possible. In "mask", there are always 3 bits set; in "filled", it's always 2 bits. When "mask" is applied to "board", all bits are reset to 0 except those 3 bits which are 1 in "mask"; these 3 bits keep the original value from "board"; so it's possible to compare it with "filled". (Obviously, all bits that are 0 in "mask" must also be 0 in "filled").

[cabal]

Well, I finally get what's going on, and I must say.. you're a genius ^__^! Wehehe I can't wait to show those two suckers how much their programs suck compared to this one. I was getting confused by the binary number values, if you were wondering. I see how it works now, with "bit arrays." Very clever. I am not worthy of your l33t pr0g skillz. Thanks again! :D

[Ninjaa]

Ammoq, you are truly the programming god. I always steer far clear of all those nasty bitwise operations, as I just can't follow them...

cabal, I can't wait to hear from you again so you can tell us what those two jackasses had to say about this. ;)

[Nezzar]

Originally posted by cabal

1 << 12 is
1000000000000
OK, here's a newb-question: When 1 << 12 is 1000000000000 is 1 << 11 == 0100000000000
(Sorry, for such a question but I never really needed bitwise operators for the things I'm doing)

[ammoQ]

Glad I could help, and calm down with titles like "genius" or "programming god", you make me blush ;)

[ammoQ]

&lt;&lt; is bitwise shifting, so 1&lt;&lt;11 is
00000000000000000000100000000000
when you look at all the bits of a word.
Likewise, 5<<5 is
00000000000000000000000010100000
(in binary) or 160 in decimal
since 5 is represented by
00000000000000000000000000000101

No need to say that &gt;&gt; shifts in the other direction.

(I assume you alreay know how numbers are represented in binary)

[cabal]

Unfortunately I didn't have time to present and explain it since the whole class had to do it. Tomorrow we have a huge test and the rest of the week off, so I guess I'll present next week. One of the genius kids said his program took 7 minutes. Haha I can't describe his face when I said mine took 3 seconds. :D It was classic! Thanks again ammoQ!

I just noticed I can finally use a custom avatar with one more post, lol.

[AtomicFeline]

Bitwise operations? I never needed to know that in my AP class... What college level course would teach you that stuff? Sounds useful...

[Ninjaa]

Heh. I didn't learn bitwise operations in my AP class either. I learned them on my own... sort of. I don't have a firm grasp of them, but I understand the concept. I cannot trace a program that uses them though.

[cabal]

I dunno what college course would teach bitwise operations but from the look of things in my book I don't think it's that widely implemented. The bitwise chapter is only 4 pages long. It was probably used a lot in C.

[ammoQ]

Bitwise operations are often used in things like device drivers and similar.

[AtomicFeline]

Makes sense. Drivers need to be fast.

[ammoQ]

It's not only a matter of speed, but a question of what has to be done. In many cases such a program has to deal with data where e.g. one word contains something in bit 0-3 and something else in bit 4-7.