Jump to content

  • Curse Sites
Become a Premium Member! Help
Latest News Article

Connect 4 with Fully Functional Artificial Opponent

minigame

  • Please log in to reply
23 replies to this topic

#1

Judcraft
    Judcraft

    Tree Puncher

  • Members
  • 37 posts

Posted 24 November 2012 - 04:36 PM

Features:
Extremely complicated artificial opponent. Lots of logic!
Non-gravity based board (with falling animation)
Full win detection for both sides
Automatic scoreboard updating
Reset board after victory

Pictures:
Spoiler:


Video:
Spoiler:

Download: http://www.mediafire...fgigj77bq68o8ou

I am trying to gauge interest in this before going too into detail about the workings of the artificial opponent. If anyone is interested in how it works I will be glad to explain!
Connect Four with Artificial Opponent - http://www.minecraft...icial-opponent/

Register or log in to remove.

#2

MrDenco
    MrDenco

    Void Walker

  • Members
  • 1657 posts
  • Location: Undisclosed Location
  • Minecraft: MrDenco

Posted 25 November 2012 - 05:43 AM

I seriously cannot explain how amazing I am right now.  Seriously, I am just at a loss for words.

That amount of wiring, that amount of intellect...I mean is just astounding.  
I am keen with computers, (CPUs, GPUs, Ram, busses, logic like that, but this, whoo nelly!)  I mean, this is applicable.  Computers, you know, are awesome, but they need a lot of work before being awesome.  This, is..... I am just astounded.
Mr. Judcraft, I think I speak on behalf of all great redstoners when I say, Welcome to the club, my friend.

+1, and incredible applause for you.  I would love to see an explanation on the logic.
I always wanted to argue with a brick wall, I suppose the internet is the second best option.

#3

Hesperus314

Posted 25 November 2012 - 10:32 AM

Fantastic, I often thought of doing something simmilar to this myself, but decided it would be to complex. Great work on making it compact aswell, kind of hard to see what is happening, but it keeps in small (relativley speaking).

It would be good if you could go into the logic of the AI. Is it reactionary, can it set up traps, deterministic, variable thinking time, etc? Come to think of it, a flow chart of the AIs' thinking would be nice.

And what about win detection, do you have a loop to detect wins, or someting more efficient?

I'm a bit busy at the moment, but when I get some time I will have a look at the world save.

And again, amazing work, best thing I have seen on the forums for a while now.

#4

Judcraft
    Judcraft

    Tree Puncher

  • Members
  • 37 posts

Posted 25 November 2012 - 12:54 PM

Thanks for the feedback! First of all let me explain..I have been building this thing off and on for quite a while now. Before this all I had made was a tic tac toe. In the middle of making this I made a QWERTY keyboard with modular display, but after completion on that I found someone else had made a keyboard so I never got around to uploading it.

Incoming wall of text!

The Win Detection was the first complicated thing I did, its nothing special and honestly if I were to do it over again I would design it in a much more efficient way. All it does is match up all the possible win states from Xs and Os and lights up a torch if they go off, that torch sends a signal to the back of the board, telling the game to reset the board and add a number to the scoreboard. If you were to actually look at the mechanism that drives the counting you will probably laugh, I designed it myself a very long time ago and i'm Positive there is a better way to do it.

The Artificial Opponent is designed to go through the following routine. First it will check to see if there are any groups of 3. If yes, it will override any other logic and block or complete (be it Xs or Os) that group. Secondly it will check for groups of 2, in a row or say there are 2 that have a space in the middle. If none of these exist it will attempt to use a column closest to the middle. A couple of things to note: It does have the ability to see when there is an ideal circumstance for setting up a victory or blocking you from setting one up, which is the combination of XX_ and X_X. It will prioritize this combination if the _ is the same for both. Speaking of that, the groups are designed so that the responses are gated through the _ space and the one beneath it. If the space is taken, or the space beneath it isn't, the grouping will be ignored.
There is also something I'd call subtractive logic (not sure what the real term is). This takes into account certain board states and denies the game from using a specific column, even if that would otherwise trip the logic. Its a bit hard to explain, but say if there is a group of 3 and the blank column the logic is gated through has 2 blanks beneath it, the game will understand that if it completes a connect 2 in that area it is setting itself up to be blocked on the group of 3, or allowing the player to complete that next turn.
This subtractive logic, while being very reasonable in the beginning of the game, made for some frustrating times when the game would be close to filled on the board as suddenly the AO wouldn't have a space that it considered valid. After a lot of testing I discovered a way around that involving some XNOR gates attached to the subtractive logic and the last level of logic.

The best thing I did for my sanity while designing this game is putting in a debugging/preview system. This has saved me a Lot of hours of manually rebuilding game states to see where the errors occur.  To be sure the game is Incomplete and there are probably plenty of spots where a single piece of redstone wire is missing, or a block is interfering with a signal it shouldn't, etc. However it will never be totally complete and its logic is very good atm so I can always release a more polished version in the future.

If there are more questions about it, I'd be glad to answer.
Connect Four with Artificial Opponent - http://www.minecraft...icial-opponent/

#5

MrDenco
    MrDenco

    Void Walker

  • Members
  • 1657 posts
  • Location: Undisclosed Location
  • Minecraft: MrDenco

Posted 25 November 2012 - 06:59 PM

Wow that is really well thought out.  I actually understood that, so nice job explaining, and also thanks for doing so.
Have you worked with logic for you occupation, or have learned it in school?  

Quote

there are probably plenty of spots where a single piece of redstone wire is missing, or a block is interfering with a signal it shouldn't
Ahh.  The curse of Redstone.
I always wanted to argue with a brick wall, I suppose the internet is the second best option.

#6

ThunderWolf2100

Posted 25 November 2012 - 07:22 PM

View PostJudcraft, on 25 November 2012 - 12:54 PM, said:

The best thing I did for my sanity while designing this game is putting in a debugging/preview system

Wow! Can you explain how this debug system works, please? It can be very useful for me :D (and for everybody too)

#7

Judcraft
    Judcraft

    Tree Puncher

  • Members
  • 37 posts

Posted 25 November 2012 - 10:42 PM

To explain this demands another wall of text sorry!

As far as my background with logic, I don't have one. In order to figure out that I needed an XNOR gate for the subtractive logic part I actually needed to look up truth tables (I knew i needed 1/1 and 0/0 to produce 1) on wikipedia (luckily I knew about those) to find the actual gate I needed. The whole thing is basically AND, OR and latches. I have absolutely no idea how you'd go about building an actual computer in minecraft haha, not sure how adders work or anything like that. I suppose that's why there are parts of my creation that would probably make more experienced people laugh, but they get the job done.

Debug System:
Alright so there are two parts in this, the Debug for the win detection, and the Preview for the artificial opponent's next move. I'll explain why these are necessary briefly...

for Win Detection
I had noticed after playing the game that sometimes the game would suddenly detect a victory, add a point to the scoreboard and reset... leaving me wondering where exactly the bug was. So I decided I would put in a circuit that when enabled would intercept the reset and scoreboard pulses while displaying that the win was detected. Then it was a simple matter of tracing where that victory was coming from and finding the problem. There is some convoluted circuit that takes care of this for me..Its probably inefficient as its old and my evolution in redstone has come a long way since i designed it.

for Preview
So this is much more elegant than the win detection one, so I'll actually give a few pictures of it. First you need to understand that I have a portion of my logic that takes multiple signals and reduces them to one. I'd say if I were to make this game less predictable to the end user and more difficult this would be the first thing I'd want to redesign.
Here's a picture.
Spoiler:
The two rows of torches on the right side are 1) from the control panel toggling the artificial opponent, and 2) a small circuit that turns the constant result from the gates into a pulse the board will understand as a button press. So what I did to make the Preview is just take that same system and duplicate is below it (reason for the repeaters at the beginning). Shown here:
Spoiler:
So its the same thing except no pulse constrictor at the end and it runs the redstone under the area in front of the board to the indication torches. Other than that it simply hooks into the above constrictor and tells it to turn off until the player hits accept. Reject simply changes the turn back to O and resets the Latch controlling the Preview.

Hope I explained that well enough!
Connect Four with Artificial Opponent - http://www.minecraft...icial-opponent/

#8

AEtherTech

Posted 26 November 2012 - 05:56 AM

This is so utterly goddamned amazing that I can't describe it.

But the AI logic is still a bit faulty, see the following screenshot (# for placement of O's and X's.) O (player ) went first.

The logic didn't detect point (A) as the win for me; and was instead looking to go for point B. I did detect (blue 3) as the location I was attempting to go, and blocked accordingly, which forced me to switch to a "simple" strategy of a line across.

Replicated this win several times. Still, most excellent work and I applaud it greatly.

http://imgur.com/6Ypq0

But I think you need to change the entrance tunnel from black wool, to something more easy to navigate. Can't see anything with default texture pack at max brightness. Had to place torches lol.

http://www.youtube.com/user/aethertech
If you have a redstone question - don't be afraid to ask it. If you are to afraid to ask it on the forums, send me a private message.


#9

callumkhang
  • Minecraft: callumkhang

Posted 26 November 2012 - 07:01 AM

This is pretty dam cool =)
When you do release it, use MCEdit colour wires filter, it's a little headach-y looking at such a thing without knowing where each wire runs where
Youtube is back =) Click for redstone

#10

Judcraft
    Judcraft

    Tree Puncher

  • Members
  • 37 posts

Posted 26 November 2012 - 11:57 AM

Thanks for the feedback!

I was unable to dulicate this glitch AEtherTech! I followed your screenshot numerically and what ended up happening was the red 6 was taken by the AO directly after 4 was placed. I tried duplicating it with a couple other combinations in order to get the board to look like yours but was unable to get to this particular combination. Are you sure you gave the right order in the picture?  I wonder if you didn't have a part of the logic loaded, the chunks that control x_x or o_o are directly behind you when you play, see this image.
Spoiler:

If these chunks are loaded the game won't get to the point that it is in currently. After red-O-4 is placed blue-X-4 will be where you have circled red 6. I have no other explanation for this glitch. On another note, ty for the advice on the black wool. On my next release I will definitely address that for default lighting and textures. Also I'm not exactly happy how the board looks with default torches...Perhaps that can be addressed as well.

Callumkhang, I'm not sure what this filter is that you are talking about but I'll check into it.]

Thanks for the interest!
Connect Four with Artificial Opponent - http://www.minecraft...icial-opponent/

#11

AEtherTech

Posted 26 November 2012 - 03:46 PM

That is an interesting conundrum then, and might be a possible explanation. I have the order right for the moves; so I will go back and make sure the chunks are all loaded, I'll get back to you latter today on it.

http://www.youtube.com/user/aethertech
If you have a redstone question - don't be afraid to ask it. If you are to afraid to ask it on the forums, send me a private message.


#12

Judcraft
    Judcraft

    Tree Puncher

  • Members
  • 37 posts

Posted 26 November 2012 - 04:55 PM

It does seem that when you are playing the game those blocks would be the farthest from you. I always host my own server locally and play with max chunk distance so that may be the problem. Believe me though there are definitely still bugs in the system, it will take a lot more debugging than I have done to fix them all.
Connect Four with Artificial Opponent - http://www.minecraft...icial-opponent/

#13

callumkhang
  • Minecraft: callumkhang

Posted 27 November 2012 - 04:26 AM

Here you go =)


Youtube is back =) Click for redstone

#14

ThunderWolf2100

Posted 27 November 2012 - 05:40 PM

Difinitely, now its time to me to learn binary to use it on redstone for make things like this.

This is one of the better redstone creations what i have seen ever

#15

Mathy
    Mathy

    Matherator

  • Sectional Moderator
  • 3527 posts

Posted 28 November 2012 - 12:53 AM

View PostJudcraft, on 25 November 2012 - 12:54 PM, said:

Thanks for the feedback! First of all let me explain..I have been building this thing off and on for quite a while now. Before this all I had made was a tic tac toe. In the middle of making this I made a QWERTY keyboard with modular display, but after completion on that I found someone else had made a keyboard so I never got around to uploading it.

Incoming wall of text!

The Win Detection was the first complicated thing I did, its nothing special and honestly if I were to do it over again I would design it in a much more efficient way. All it does is match up all the possible win states from Xs and Os and lights up a torch if they go off, that torch sends a signal to the back of the board, telling the game to reset the board and add a number to the scoreboard. If you were to actually look at the mechanism that drives the counting you will probably laugh, I designed it myself a very long time ago and i'm Positive there is a better way to do it.

The Artificial Opponent is designed to go through the following routine. First it will check to see if there are any groups of 3. If yes, it will override any other logic and block or complete (be it Xs or Os) that group. Secondly it will check for groups of 2, in a row or say there are 2 that have a space in the middle. If none of these exist it will attempt to use a column closest to the middle. A couple of things to note: It does have the ability to see when there is an ideal circumstance for setting up a victory or blocking you from setting one up, which is the combination of XX_ and X_X. It will prioritize this combination if the _ is the same for both. Speaking of that, the groups are designed so that the responses are gated through the _ space and the one beneath it. If the space is taken, or the space beneath it isn't, the grouping will be ignored.
There is also something I'd call subtractive logic (not sure what the real term is). This takes into account certain board states and denies the game from using a specific column, even if that would otherwise trip the logic. Its a bit hard to explain, but say if there is a group of 3 and the blank column the logic is gated through has 2 blanks beneath it, the game will understand that if it completes a connect 2 in that area it is setting itself up to be blocked on the group of 3, or allowing the player to complete that next turn.
This subtractive logic, while being very reasonable in the beginning of the game, made for some frustrating times when the game would be close to filled on the board as suddenly the AO wouldn't have a space that it considered valid. After a lot of testing I discovered a way around that involving some XNOR gates attached to the subtractive logic and the last level of logic.

The best thing I did for my sanity while designing this game is putting in a debugging/preview system. This has saved me a Lot of hours of manually rebuilding game states to see where the errors occur.  To be sure the game is Incomplete and there are probably plenty of spots where a single piece of redstone wire is missing, or a block is interfering with a signal it shouldn't, etc. However it will never be totally complete and its logic is very good atm so I can always release a more polished version in the future.

If there are more questions about it, I'd be glad to answer.

You make it look so simple, as if this wasn't really that hard, in the WIn Detection part.

Fermat said:

I have discovered a truly remarkable proof of this, which this margin is too small to contain.


#16

zabh
    zabh

    Tree Puncher

  • Members
  • 26 posts
  • Location: USA
  • Minecraft: ZabH
  • Xbox:ZabH

Posted 28 November 2012 - 01:04 AM

Redstone never seem to get boring to me, people always build something new and insane, I have been working for it some time now and I always learn something new.

One of the most insane things I have seen!!!
Posted Image

#17

Judcraft
    Judcraft

    Tree Puncher

  • Members
  • 37 posts

Posted 28 November 2012 - 01:21 AM

Hey everyone, thanks for the feedback!

Callumkhang- Yeah I found that video, very interesting. Probably not something I would do for the original world it is in but it looks very easy for someone to do if they wanted. Maybe when I release the next version I could have an alternate download for a version that is colored like that.

Thunderwolf- From personal experience the best way to learn how to manipulate redstone is to just start doing it. If you hit a roadblock go online and figure out if you can use a simple circuit to get around it, maybe check if there is someone that has done what you are trying to do..How they did it.

Mathy - Looking back I was very satisfied when I got the win detection working. What I mean to say is that conceptually the win detection isn't very complicated, even if it did take a while to actually implement.

Zabh - Redstone is a great feature of the game! Like most I was intimidated by it at first but as I began to play around with it I started setting new goals. Some were discarded, some were realized. I think that's what is so compelling about redstone..It is a logic puzzle that you create as you solve it. It can get as complicated and obtuse or as simple and elegant as you want it to become. In my opinion the really beautiful constructs are combinations of both.

Thanks for all the positive feedback everyone, you've made me glad that I took to time to create the download and video!
Connect Four with Artificial Opponent - http://www.minecraft...icial-opponent/

#18

jellyw00t
  • Minecraft: jellyw00t

Posted 28 November 2012 - 02:15 AM

Why use torches instead of lamps?

#19

AEtherTech

Posted 28 November 2012 - 03:26 AM

OK, guess it was a chunk not-loaded issue...

Well done sir.

Well done.

http://www.youtube.com/user/aethertech
If you have a redstone question - don't be afraid to ask it. If you are to afraid to ask it on the forums, send me a private message.


#20

Judcraft
    Judcraft

    Tree Puncher

  • Members
  • 37 posts

Posted 28 November 2012 - 01:43 PM

AEtherTech- Glad to hear it! Although there are bugs in the system still, the combination of the two different types of groups of 2 was a piece of logic that I'm very proud of so I'm glad its working on the download.

jellyw00t - The reason I used torches instead of lamps just has to do with when the project was started. When I created my X, O or nothing board Lamps did not exist. Neither did pistons.
However my system does allow for either. You simply put them in front of the torches. I'll make a screenshot:
Spoiler:
All three types of displays have their pros and cons. Since this is not the final release I'll open my thinking up to everyone and maybe someone will have some feedback.

Torches:
Pros: When screen is turned off, they are the hardest to see. They are consistent with the words on the sides of the screen, which would be very ugly if done with blocks or pistons because they aren't directional.

Cons: Default ones are ugly and have wood for the handle, which could make them confusing to look on on the board.

Lamps:
Pros: Easy to differentiate Xs and Os in any video setting, with smooth lighting on or off. A moderately attractive option.

Cons: Rapid blinking (falling animation, reseting the board) can leave light artifacts in the screen, which are detrimental to the feel of the board and quite ugly.

Pistons:
Pros: Easy to differentiate Xs and Os. Attractive.

Cons: Firstly, in order for it to be legible you must use something other than black, which ruins the feel of the board. Also, if you don't use smooth lighting its impossible to make out! This could be due to not bringing the outline torches in line with the pistons. I've never attempted to make a piston screen before so I might have to work on this a bit more.

Thanks for the feedback!
Connect Four with Artificial Opponent - http://www.minecraft...icial-opponent/